Algorytm Helda-Karpa

Graf, 4 wierzchołki (1) Graf użyty w przykładzie wykonania algorytmu
REKLAMA Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
19,90 zł
Unix i Linux. Przewodnik administratora systemów. Wydanie V
179,00 zł
ASP.NET Core 2.0. Wprowadzenie
−30%48,30 zł
Uczenie maszynowe z użyciem Scikit-Learn i TensorFlow
89,00 zł

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!)).

Działanie algorytmu

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:

  • Jeśli s=1, to D(S, p) = d1,p,
  • Jeśli s>1, to D(S, p) = minx∈(S-{p})( D(S−{p}, x) + dx,p).

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).

Przykład

Dany jest graf zawierający cztery wierzchołki (taki, jak na ilustracji). Odległości między wierzchołkami są następujące:

  • d1,2 = d2,1 = 30
  • d1,3 = d3,1 = 36
  • d1,4 = d4,1 = 40
  • d2,3 = d3,2 = 20
  • d2,4 = d4,2 = 50
  • d3,4 = d4,3 = 67

Na początku wyznaczamy wartości D(S, p) dla jednoelementowych zbiorów S (s=1). Są to przypadki trywialne.

  • D({2}, 2) = d1,2 = 30
  • D({3}, 3) = d1,3 = 36
  • D({4}, 4) = d1,4 = 40

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.

  • D({2, 3}, 2) = min( D({3}, 3) + d3,2 ) = min(36 + 20) = min(56) = 56 [3]
  • D({2, 3}, 3) = min( D({2}, 2) + d2,3 ) = min(30 + 20) = min(50) = 50 [2]
  • D({2, 4}, 2) = min( D({4}, 4) + d4,2 ) = min(40 + 50) = min(90) = 90 [4]
  • D({2, 4}, 4) = min( D({2}, 2) + d2,4 ) = min(30 + 50) = min(80) = 80 [2]
  • D({3, 4}, 3) = min( D({4}, 4) + d4,3 ) = min(40 + 67) = min(80) = 107 [4]
  • D({3, 4}, 4) = min( D({3}, 3) + d3,4 ) = min(36 + 67) = min(80) = 103 [3]

W kolejnych krokach wyznaczamy wartości D(S, p) dla trójelementowych zbiorów S (s=3).

  • D({2, 3, 4}, 2) = min( D({3, 4}, 3) + d3,2, D({3, 4}, 4) + d4,2 ) = min(107 + 20, 103 + 50) = min(127, 153) = 127 [3]
  • D({2, 3, 4}, 3) = min( D({2, 4}, 2) + d2,3, D({2, 4}, 4) + d4,3 ) = min(90 + 20, 80 + 67) = min(110, 147) = 110 [2]
  • D({2, 3, 4}, 4) = min( D({2, 3}, 2) + d2,4, D({2, 3}, 3) + d3,4 ) = min(56 + 50, 50 + 67) = min(106, 117) = 106 [2]

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:

  • min( D({2, 3, 4}, 2) + d2,1, D({2, 3, 4}, 3) + d3,1, D({2, 3, 4}, 4) + d4,1,) = min(127 + 30, 110 + 36, 106 + 40) = min(157, 146, 146) = 146 [3]

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.

Złożoność obliczeniowa

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).

Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 7 sierpnia 2017 11:19, ostatnia edycja: 8 listopada 2017 16:03.

REKLAMA

Zobacz też

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość
Polityka prywatnościKontakt