Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).
Załóżmy, że mamy graf liczący n wierzchołków ponumerowanych 1, 2, …, n. Wierzchołek 1 niech będzie wierzchołkiem początkowym. Jako di,j oznaczmy odległość między wierzchołkami i oraz j (są to dane wejściowe).
Oznaczmy jako D(S, p) optymalną długość ścieżki wychodzącej z punktu 1 i przechodzącej przez wszystkie punkty zbioru S tak, aby zakończyć się w punkcie p (p musi należeć do S). Przykładowo, zapis D({2, 5, 6}, 5) to optymalna długość ścieżki wychodzącej z punktu 1, przechodzącej przez punkty 2 i 6, kończącej się w punkcie 5. Liczbę punktów w zbiorze S oznaczmy jako s.
Wartość D(S, p) wyznaczamy następująco:
Mówiąc obrazowo, musimy za każdym razem ustalać, który punkt powinien być przedostatni na trasie (który punkt ma poprzedzać punkt p).
Na końcu wyznacza się rozwiązanie całego problemu. W tym celu należy znaleźć poprzednika punktu 1 korzystając ze wzoru: minx∈{2, …, n}( D({2, …, n}, x) + dx,1).
Dany jest graf zawierający cztery wierzchołki (taki, jak na ilustracji). Odległości między wierzchołkami są następujące:
Na początku wyznaczamy wartości D(S, p) dla jednoelementowych zbiorów S (s=1). Są to przypadki trywialne.
Następnie wyznaczamy wartości D(S, p) dla dwuelementowych zbiorów S (s=2). W nawiasie kwadratowym zapisaliśmy numer przedostatniego węzła na ścieżce (węzła x dla optymalnego rozwiązania podproblemu). W tych przypadkach co prawda wybór jest oczywisty, gdyż zbiór S−{p} jest jednoelementowy, jednak już teraz pilnujmy notacji.
W kolejnych krokach wyznaczamy wartości D(S, p) dla trójelementowych zbiorów S (s=3).
Trójelementowy zbiór S jest dla tego zadania największym z możliwych, gdyż nie licząc wierzchołka początkowego mamy trzy wierzchołki. Możemy więc już teraz wyznaczyć rozwiązanie całego zadania:
Znamy już długość optymalnej trasy. Samą trasę możemy odtworzyć wykorzystując indeksy z kwadratowych nawiasów. Trasa to 1–3–2–4–1.
Obliczmy, ile razy wyznaczana jest wartość D(S, p). Dla s=1 wartość tę wyznacza się n−1 razy. Dla każdego s z przedziału od 2 do n−1 rozważamy wszystkie s-elementowe kombinacje ze zbioru n−1-elementowego, przy czym dla każdej kombinacji rozważamy s wariantów punktu końcowego. Łącznie liczba wyznaczanych wartości D(S, p) wynosi zatem: $$(n-1)+∑↙{s=2}↖{n-1}s{(n-1)!}/{s!(n-1-s)!}$$ Korzystając z własności symbolu Newtona można przekształcić ten wzór do postaci: $$(n-1)2^{n-2}$$ Wartość D(S, p) wyznacza się w czasie liniowym (zakładając, że mamy bezpośredni dostęp do każdej zapamiętanej wartości, co można zapewnić prawidłowym indeksowaniem). Łącznie złożoność czasowa algorytmu wynosi więc O(n22n). Każdą wartość D(S, p) należy zapamiętać, zatem złożoność pamięciowa algorytmu to O(n2n).
Dodano: 7 sierpnia 2017 11:19, ostatnia edycja: 8 listopada 2017 16:03.
Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.
W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.
Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.
Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).
Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.