Algorytm Helda-Karpa

Algorytm Helda – Karpa , zwany także algorytmem Bellmana – Helda – Karpa , to algorytm programowania dynamicznego zaproponowany w 1962 roku niezależnie przez Bellmana oraz Helda i Karpa w celu rozwiązania problemu komiwojażera (TSP), w którym dane wejściowe to macierz odległości między zbiór miast, a celem jest znalezienie trasy o minimalnej długości, która odwiedza każde miasto dokładnie raz przed powrotem do punktu początkowego. Znajduje dokładne rozwiązanie tego problemu i kilku powiązanych problemów, w tym problemu cyklu Hamiltona , w czas wykładniczy .

Opis algorytmu i motywacja

Ponumeruj miasta ${\ Displaystyle 1,2, \ ldots, n}$ $,$ z wyznaczonym jako miasto „początkowe” (ponieważ rozwiązaniem TSP jest cykl, wybór miasto startowe nie ma znaczenia). Algorytm Helda-Karpa zaczyna się od obliczenia dla każdego zestawu miast i każdego miasta ${\ Displaystyle S \ subseteq \ {2, \ ldots, n \}}$ ${\ Displaystyle e \ neq 1}$ nie zawarte w najkrótszej jednokierunkowej ścieżce od do $\ displaystyle e}$ $,$ $która przechodzi$ każde miasto w ${\ displaystyle S}$ w jakiejś kolejności (ale nie przez inne miasta). Oznacz tę odległość ${\ Displaystyle g (S, e)}$ i napisz ${\ Displaystyle d (u, v)}$ dla długości bezpośredniej krawędzi od do ${ \$ $v}$ . Obliczymy $zaczynając$ $_$ najmniejszych zestawów

Kiedy ma dwa $lub mniej$ $elementów$ obliczenie na jedną lub dwie Na przykład ${\ Displaystyle g (\ pusty zestaw, e)}$ jest po prostu ${\ Displaystyle d (1, e)}$ i ${\ Displaystyle g (\ {2 \}, 3)}$ to tylko długość ${\ Displaystyle 1 \ rightarrow 2 \ rightarrow 3}$ . Podobnie sol $\ Displaystyle g (\ {2,3 \}, 4)}$ jest długością ${\ Displaystyle 1 \ rightarrow 2 \ rightarrow 3 \rightarrow 4}$ lub ${\ Displaystyle 1 \ rightarrow 3 \ rightarrow 2 \ rightarrow 4}$ , cokolwiek jest krótsze.

Gdy zawiera trzy lub więcej miast, liczba ścieżek prowadzących przez $displaystyle$ $S}$ szybko rośnie, ale wystarczy zbadać tylko kilka takich ścieżek, aby znaleźć najkrótszą Na przykład, jeśli jest $rightarrow 3 \$ 1 $Displaystyle 1 \ rightarrow 2 \$ wtedy ${\ Displaystyle 1 \ rightarrow 2 \ rightarrow 3 \ rightarrow 4 \ rightarrow 5}$ musi być krótszy niż ${\ Displaystyle 1 \ rightarrow 3 \ rightarrow 2 \ rightarrow 4 \ rightarrow 5}$ , a długość ${\ Displaystyle 1 \ rightarrow 3 \ rightarrow 2 \ rightarrow 4 \ rightarrow 5}$ nie jest możliwą wartością ${\ Displaystyle g (\ {2,3,4 \}, 5)}$ . Podobnie $Displaystyle$ ${\ Displaystyle 1 \ strzałka w prawo 4 \ strzałka w prawo 3 \ strzałka w prawo 2 \ strzałka w prawo 5}$ najkrótsza $}$ \ $→$ przez , a najkrótsza ścieżka od ${\ Displaystyle 1}$ przez ${\ Displaystyle \ {2,3,4,5 \}}$ do ${\ Displaystyle 6}$ kończy się krawędzią ${\ Displaystyle 5 \ rightarrow 6}$ , wtedy cała ścieżka od ${\ Displaystyle 1}$ do ${\ Displaystyle 6}$ musi wynosić ${\ Displaystyle 1 \ rightarrow 4 \ rightarrow 3 \ rightarrow 2 \ rightarrow 5 \ rightarrow 6}$ , a nie żadna z pozostałych pięciu ścieżek utworzonych przez odwiedzenie ${\ Displaystyle \ {2,3 ,4\}}$ w innej kolejności.

$_$ ogólnie _ $_$ _ Dla każdej liczby całkowitej ${\ Displaystyle 1 \ równoważnik i \ równoważnik k}$ , napisz $\}}$ ${\ Displaystyle S_ {i} = S \ setminus \ {s_ {i} \} = \ {s_ {1}, \ ldots, s_ {i-1}, s_ {i + 1}, \ ldots, s_ {k$ ${\ displaystyle$ dla zestawu utworzonego przez usunięcie z $s_ {i}}$ . Następnie, jeśli najkrótsza ścieżka od ${\ displaystyle 1}$ przez ${\ displaystyle S}$ do ${\ displaystyle e}$ ma Displaystyle $s_ {i}}$ jako jego przedostatnie miasto, a następnie usunięcie ostatniej krawędzi z tej ścieżki musi dać najkrótszą ścieżkę od ${\ Displaystyle 1}$ do $s_ {i}}$ ${\ Displaystyle S_ {i}}$ . Oznacza to $e}$ że są tylko $.$ $displaystyle$ ścieżki od do ${ \$ przez , po jednej dla każdego możliwego przedostatniego miasta ${\ Displaystyle s_ {i}}$ o długości sol $\ Displaystyle g (S_ {i}, s_ {i}) + d (s_ {i} ,e)}$ i ${\ Displaystyle g (S, e) = \ min _ {1 \ równoważnik ja \ równoważnik k} g (S_ {i}, s_ {i}) + d (s_ {i}, e)}$ .

Ten etap algorytmu kończy się, gdy ${\ Displaystyle g (\ {2, \ ldots, i-1, i + 1, \ ldots, n \}, i)}$ jest znany dla każdej liczby całkowitej $\ Displaystyle 2 \ równoważnik i \ równoważnik n}$ , co daje najkrótszą odległość od miasta do miasta ${\ displaystyle 1}$ ${\ displaystyle i}$ , który przechodzi przez każde inne miasto. Znacznie $etap$ $a$ długości krawędzi, możliwe następnie znajduje najkrótszy

Ostatecznie samą najkrótszą ścieżkę (a nie tylko jej długość) można zrekonstruować, przechowując obok etykiety przedostatniego miasta na ścieżce od ${\ Displaystyle g (S, e)}$ ${\ displaystyle 1}$ do $e }$ ${\ displaystyle$ do , podnosząc wymagania dotyczące tylko o stały współczynnik.

Złożoność algorytmiczna

Algorytm Helda-Karpa ma wykładniczą złożoność czasową $Theta (n!)}$ $n$ wydajność ${$ algorytmu brutalnej siły. $Jednak Held$ Karp wymaga funkcji ${\ Displaystyle g (S, e)}$ $miejsca$ siła potrzebuje tylko do przechowywania samego wykresu

Czas

sol ${\ Displaystyle g (S, e)}$ dla -elementowego podzbioru ${\ Displaystyle K}$ ${\ Displaystyle S}$ z ${\ Displaystyle \ { 2, \ ldots, n \}}$ wymaga znalezienia najkrótszej z $ścieżek$ , z których każda została znaleziona przez dodanie znanej wartości ${\ displaystyle g}$ i długość krawędzi z oryginalnego wykresu; to znaczy wymaga czasu proporcjonalnego do ${\ displaystyle k}$ . Istnieją ${\ textstyle {\ binom {n-1} {k}}}$ ${\ displaystyle k}$ -elementowe podzbiory ${\ Displaystyle \ {2, \ ldots ,n\}}$ ; a każdy podzbiór daje możliwe wartości ${\ displaystyle nk-1}$ ${\ displaystyle e}$ . Obliczanie wszystkich wartości gdzie ${\ Displaystyle g (S, e)$ ${\ Displaystyle | S | = k}$ wymaga więc czasu ${\ textstyle k (nk-1) {\ binom {n-1} {k}} = (n-1) (n-2) {\ binom {n-3} {k-1} }}$ , przez całkowity czas we wszystkich rozmiarach podzbioru ${\ textstyle (n-1) (n-2) \ suma _ {k = 1} ^ {n-2} {\ binom {n-3} {k-1} }=(n-1)(n-2)2^{n-3}=\Theta (n^{2}2^{n})}$ . Drugi $etap$ algorytmu, znalezienie pełnego cyklu spośród $zajmuje$ czas na wydajność

W $przypadku$ grafów można ${\ textstyle g (S, e) + g (S ^ {c} \ setminus \ {1, e \}, e)}$ minimum dla każdego ${\ textstyle \ {(S, e):| S | = \ lfloor {\ Frac {n-1} {2}} \ rfloor, mi \in S^{c}\setminus \{1\}\}}$ , gdzie ${\textstyle S^{c}}$ jest zbiorem dopełnień ${\textstyle S}$ . Jest to analogiczne do wyszukiwania dwukierunkowego rozpoczynającego się od ${\ textstyle 1}$ i spotkanie w punkcie środkowym ${\ textstyle e}$ . Jest to jednak stała poprawa czynnika i nie wpływa na wydajność asymptotyczną.

Przestrzeń

Przechowywanie wszystkich wartości ${\ Displaystyle g (S, e)}$ dla podzbiorów o $rozmiarze$ zachowania ${\ textstyle (nk-1) {\ binom {n-1} {k}} = (n-1) {\ binom {n-2} {k}}} wartości$ . Kompletna tabela wartości ${\ Displaystyle g (S, e)}$ zatem miejsca ${\textstyle \sum _{k=0}^{n-2}(n-1){\binom {n-2}{k}}=(n-1)2^{n}=\Theta ( n2^{n})}$ . To zakłada, że $\$ $textstyle n}$ jest wystarczająco mały, aby można go przechowywać jako maskę bitową stałej wielokrotności słów maszynowych , a nie jawną k-krotkę.

$}$ nie sam cykl, to złożoność przestrzeni można nieco poprawić, zauważając, że obliczenie dla $g (S, e)}$ $Displaystyle$ o rozmiarze $k$ tylko wartości dla $Displaystyle$ o rozmiarze $k-1}$ . Zachowując tylko ${\ textstyle (n-1) \ lewo [{\ binom {n-2} {k-1}} + {\ binom {n-2} k}} \ prawej]}$ wartości ${\ Displaystyle g (S, e)}$ gdzie ${\ Displaystyle S}$ ma rozmiar albo ${\ Displaystyle k-1}$ lub ${\ Displaystyle k}$ zmniejsza maksymalne wymagania algorytmu dotyczące miejsca, osiągane, gdy ${\ textstyle k = \ lewo \ lfloor {\ Frac {n} {2}} \ prawo \ rfloor}$ , do ${\ Displaystyle \Theta ({\sqrt {n}}2^{n})}$ .

Przykład

Macierz odległości:

= {\ początek {pmatrix} 0 i 2 i 9 i 10 \\ 1 i 0 i 6 i 4 \\ 15 i 7 i 0 i 8 \\ 6 i 3 i 12 i 0 \ koniec {pmatrix}}}

Opis funkcji:

g(x, S) - zaczynając od 1, path min cost kończy się na wierzchołku x, przechodząc przez wierzchołki w zbiorze S dokładnie raz
c _xy - koszt krawędzi kończy się na x od y
p(x, S) - przedostatni wierzchołek do x ze zbioru S. Używany do konstruowania ścieżki TSP z powrotem na końcu.

k = 0, zbiór zerowy:

Zestaw ∅:

 g(2, ∅) = do ₂₁ = 1 g(3, ∅) = do ₃₁ = 15 g(4, ∅) = do ₄₁ = 6

k = 1, rozważ zestawy po 1 elemencie:

zestaw {2}:

 g(3,{2}) = do ₃₂ + g(2, ∅ ) = do ₃₂ + do ₂₁ = 7 + 1 = 8 p(3,{2}) = 2 g(4,{2}) = do ₄₂ + g(2, ∅ ) = do ₄₂ + do ₂₁ = 3 + 1 = 4 p(4,{2}) = 2

zestaw {3}:

 g(2,{3}) = do ₂₃ + g(3, ∅ ) = do ₂₃ + do ₃₁ = 6 + 15 = 21 p(2,{3}) = 3 g(4,{3}) = do ₄₃ + g(3, ∅ ) = do ₄₃ + do ₃₁ = 12 + 15 = 27 p(4,{3}) = 3

zestaw {4}:

 g(2,{4}) = do ₂₄ + g(4, ∅ ) = do ₂₄ + do ₄₁ = 4 + 6 = 10 p(2,{4}) = 4 g(3,{4}) = do ₃₄ + g(4, ∅ ) = do ₃₄ + do ₄₁ = 8 + 6 = 14 p(3,{4}) = 4

k = 2, rozważmy zestawy 2 elementów:

Zestaw {2,3}:

 g(4,{2,3}) = min {c ₄₂ + g(2,{3}), c ₄₃ + g(3,{2})} = min {3+21, 12+8}= min {24, 20}= 20 p(4,{2,3}) = 3

Zestaw {2,4}:

 g(3,{2,4}) = min {c ₃₂ + g(2,{4}), c ₃₄ + g(4,{2})} = min {7+10, 8+4}= min {17, 12} = 12 p(3,{2,4}) = 4

Zestaw {3,4}:

 g(2,{3,4}) = min {c ₂₃ + g(3,{4}), do ₂₄ + g(4,{3})} = min {6+14, 4+27}= min {20, 31}= 20 p(2,{3,4}) = 3

Długość optymalnej wycieczki:

 f = g(1,{2,3,4}) = min { do ₁₂ + g(2,{3,4}), do ₁₃ + g(3,{2,4}), do ₁₄ + g( 4,{2,3}) } = min. {2 + 20, 9 + 12, 10 + 20} = min. {22, 21, 30} = 21

Poprzednik węzła 1: p(1,{2,3,4}) = 3

Poprzednik węzła 3: p(3, {2,4}) = 4

Poprzednik węzła 4: p(4, {2}) = 2

Poprzednik węzła 2: p(2, {}) = 1

Stąd optymalna trasa TSP jest dana przez 1 → 2 → 4 → 3 → 1.

Pseudo kod

    

    
        
            
        
     funkcji  TSP (G, n)  jest  dla  k := 2 do n  do  g({k}, k) := d(1, k)  koniec dla  dla  s := 2  do  n−1  do  dla wszystkich  S ⊆ { 2, ..., n}, |S| = s   do  dla wszystkich  k ∈ S  do  g(S, k) := min _m≠k,m∈S [g(S\{k}, m) + d(m, k)]  koniec za  koniec za  koniec dla  opt := min _k≠1 [g({2, 3, ..., n}, k) + d(k, 1)]  return  (opt)  funkcja końcowa

Powiązane algorytmy

Dokładne algorytmy rozwiązywania TSP

Poza programowaniem dynamicznym, programowanie liniowe oraz rozgałęzianie i wiązanie są również wzorcami projektowymi używanymi do dokładnych rozwiązań TSP. Programowanie liniowe wykorzystuje metodę płaszczyzny cięcia w programowaniu całkowitym , tj. rozwiązywanie LP utworzonego przez dwa ograniczenia w modelu, a następnie szukanie płaszczyzny cięcia poprzez dodawanie ograniczeń nierówności, aby stopniowo zbiegać się do optymalnego rozwiązania. Kiedy ludzie stosują tę metodę, aby znaleźć płaszczyznę cięcia, często polegają na doświadczeniu, więc ta metoda jest rzadko stosowana jako metoda ogólna.

Termin oddział i związany został po raz pierwszy użyty w 1963 roku w artykule opublikowanym przez Little i in. na TSP, opisujący technikę łączenia mniejszych przestrzeni poszukiwań i ustalania dolnych granic w celu rozszerzenia praktycznego zakresu zastosowania dokładnego rozwiązania. Technika ta jest przydatna do zwiększania liczby miast, które można rozpatrywać obliczeniowo, ale nadal dzieli się na zbiory danych na dużą skalę.

Kontroluje proces wyszukiwania poprzez zastosowanie restrykcyjnych granic, umożliwiając poszukiwanie optymalnej gałęzi rozwiązania z drzewa stanów przestrzeni w celu jak najszybszego znalezienia optymalnego rozwiązania. Kluczowym elementem tego algorytmu jest wybór ograniczającej granicy. Różne ograniczające granice mogą tworzyć różne algorytmy związane z gałęziami.

Przybliżone algorytmy rozwiązywania TSP

Ponieważ zastosowanie precyzyjnego algorytmu do rozwiązania problemu jest bardzo ograniczone, często stosujemy algorytm przybliżony lub algorytm heurystyczny. Wynik algorytmu można ocenić za pomocą C / C* ≤ ε . C to całkowita odległość do pokonania wygenerowana z przybliżonego algorytmu; C* to optymalna odległość przejazdu; ε jest górną granicą stosunku całkowitej odległości przebytej przez rozwiązanie przybliżone do rozwiązania optymalnego w najgorszych warunkach. Wartość ε >1,0. Im bardziej zbliża się do 1,0, tym lepszy jest algorytm. Algorytmy te obejmują: Algorytm interpolacji, Algorytm najbliższego sąsiada , algorytm Clarka i Wrighta, algorytm podwójnego drzewa rozpinającego, algorytm Christofidesa , algorytm hybrydowy, algorytm probabilistyczny (taki jak symulowane wyżarzanie ).