Złożoność czasowa algorytmu Held-Karp dla TSP

Kiedy przejrzałem „ Dynamiczne podejście programistyczne do problemów z sekwencjonowaniem ” autorstwa Michaela Helda i Richarda M. Karpa, wpadłem na następujące pytanie: dlaczego złożoność ich algorytmu dla TSP jest (s. 199), mam na myśli skąd biorą współczynnik ? Jeśli dobrze zrozumiałem, oznacza liczbę dodatków dla każdego podzbioru miast. To dlaczego każda operacja dodawania jest połączony z nieznanych mi operacje? Przypuszczam, że wiąże się to w jakiś sposób z przyjmowaniem minimum, ale obliczanie minimum nie wymaga tak wielu operacji. $(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ $k$ $k-1$ $k$

Algorytm programowania dynamicznego Helda i Karpa i niezależnie Bellman działa w następujący sposób: dla każdej pary , co oznacza ścieżkę przechodzącą przez , wszystkie elementy i kończące się w obliczane $(S,c_i)$ $c_1$ $S$ $c_i$

$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$

gdzie oznacza odległość między miastami i . Następnie w mieszance z papieru oznacza wielkość . $d(c_j,c_i)$ $c_j$ $c_i$ $k$ $S$

ds.algorithms tsp exp-time-algorithms

— Oleksandr Bondarenko
źródło

Odpowiedzi:

Dodatek do poniżej wyjaśniający warunki : $k(k-1)$

Tak więc, jeśli przeanalizujesz terminy w wyrażeniu, możesz wyobrazić sobie (analogicznie), że termin jest wyliczeniem wszystkich ciągów binarnych zawierających 1, które mają 1 w pierwszej pozycji. Innymi słowy, pozwalamy każdej pozycji w łańcuchu binarnym reprezentować wybór, czy dane z jednego z miast w problemie znajduje się w dokładnie podzbiorze, który rozważamy w tym czasie. Zatem dla 5 miast 10101 odpowiada podzestawowi {1,3,5}. $n-1 \choose k$ $k$ $n$

Zatem, aby obliczyć wszystkie podzbiory {1, ..., }, po prostu zliczamy każdy podzbiór binarny (tj. Liczymy przez ciągi binarne) o rozmiarze = 2 (tj. Ciągi binarne o rozmiarze które zawierają dwa 1), rozmiar = 3, następnie rozmiar = 4, ... następnie rozmiar = n. (Zauważ, że podzbiór size = 1 musi zawierać tylko pierwsze miasto, a zatem obliczenie jego częściowej odległości nie ma znaczenia, ponieważ odległość od 1 -> wszystkich innych miast w podzbiorze -> 1 wynosi dokładnie 0). $n$ $n$

W każdym podzbiorze miastami musimy rozważyć do kandydatów optymalnych, częściowych ścieżek. W szczególności optymalna, całkowita ścieżka mogłaby przejść przez dany podzbiór i skończyć w jednym z miast , z wyłączeniem pierwszego miasta. Następnie dla każdej takiej kandydującej podścieżki obliczamy optymalną trasę do tego punktu jako minimum dowolnej z poprzednich podścieżek size = plus odległość od miasta końcowego dla tej podścieżki do miasto końcowe dla bieżącej ścieżki podrzędnej kandydata. To daje takie porównania, które musimy wykonać. Rozbieżność między moim terminem a $k$ $k-1$ $k-1$ $k-1$ $(k-1)(k-2)$ $(k-1)(k-2)$ $k(k-1)$ termin w powiązanej analizie jest różnicą notacyjną (sumowałbym w innym zakresie, biorąc pod uwagę moją definicję niż oni). Przynajmniej powinien on jednak ilustrować złożoność kwadratową tego terminu. $k$

Co ciekawe - właśnie skończyłem kodowanie tego dokładnego algorytmu w C ++ kilka minut temu. (Więc wybacz styczną od czystej teorii do małej praktycznej dyskusji. :))

Kosztuje czas i przestrzeń - przynajmniej pod moją implementacją. Praktycznie rzecz biorąc, gdy Twoje wymagania przestrzenne rosną tak szybko, stają się o wiele bardziej bolesne niż wymagania czasowe. Na przykład na moim komputerze (z 4 GB pamięci RAM) mogę rozwiązywać instancje z maksymalnie 24 miastami - nawet więcej, i brakuje mi pamięci. $O(2^n n^2)$ $O(2^n n)$

Oczywiście, mógłbym być po prostu złym programistą, a może będziesz w stanie radzić sobie lepiej ode mnie w praktyce. :)

Edycja: Trochę więcej szczegółów na temat jednego szczegółu pytania: Pojęcie wynika z faktu, że w najgorszym przypadku musisz obliczyć częściową, optymalną odległość od poprzednich podzbiorów (najwyżej z nich; zwróć uwagę, że jest sumowane przez w analizie, którą połączyłeś) z bieżącą. Wymaga to, ponownie w najgorszym przypadku, porównań z podzbiorami wielkości dla sumy . $k(k-1)$ $n$ $k$ $n$ $O(k)$ $k-1$ $O(k^2)$

Ponadto, jeśli moje wyjaśnienie nie było wystarczająco jasne, oto kilka miłych notatek z wykładów Vazirani ( PDF ). Przewiń w dół do P. 188, aby omówić TSP, w tym analizę Held-Karp.

— Daniel Apon
źródło

Och, oczywiście! Głupio myślę o tym teraz; Zaktualizuję moją odpowiedź. Właściwie słyszałem już dokładnie ten komentarz i po prostu przekazałem go bez zastanowienia. I tak - zapis do pliku / odczyt z pliku pozwoli ci skutecznie przejść arbitralnie wysoko w wielu miastach. ... to również ból, o który nie warto się martwić, chyba że próbujesz rozwiązać instancje TSP w prawdziwym celu. Mój zdecydowanie nie był praktyczny. ;)

— Daniel Apon,

Czas na implementację algorytmu Bjorklund :)

— Suresh Venkat

@Suresh: Dobry pomysł!

— Daniel Apon,

@Daniel Apon Czy mógłby Pan wyjaśnić, dlaczego potrzebujemy porównań przy obliczaniu „częściowej, optymalnej odległości”?

— Oleksandr Bondarenko,

@Oleksandr: Jasne, dodam to na początku mojej odpowiedzi.

— Daniel Apon,

Uwaga główna

Ważne jest, aby pamiętać, że obliczenia i sklep nie
„odległość optymalnej ścieżki dla combination of k cities”
ale
„odległości optymalnej ścieżki dla combination of k cities I za end-point city from this combination”.
Zrozumienie tego pomoże w znaczeniu pierwszych dwóch mnożników w następującej formule.

Pierwsza faza

Liczba operacji w pierwszej fazie wynosi:

\sum_{k >= 2} \underset{\begin{matrix} choose city combination \\ of size = k - 1 \end{matrix}}{\underset{⏟}{(\binom{n - 1}{k - 1})}} \cdot \underset{\begin{matrix} choose city to be the last \\ from k - 1 cities \\ in chosen combination \end{matrix}}{\underset{⏟}{(k - 1)}} \cdot \underset{\begin{matrix} choose city \\ that is not in chosen combination \\ to add to path \end{matrix}}{\underset{⏟}{((n - 1) - (k - 1))}}

$\displaystyle \sum_{k>=2} \underbrace{ \binom{n-1}{k-1} }_{\substack{ \text{choose city combination} \\ \text{of size = $k-1$}}} \cdot \underbrace{ (k-1) }_{\substack{ \text{choose city to be the last} \\ \text{from $k-1$ cities} \\ \text{in chosen combination} } } \cdot \underbrace{ ((n-1)-(k-1)) }_{ \substack{ \text{choose city} \\ \text{that is not in chosen combination} \\ \text{to add to path} } }$

Brakujący indeks górny w sumie oznacza for all k>=2 that is valid for binomial coefficient. Tak więc ostatni poprawny, nie zerowy termin sumy będzie dla Oznacza to, że nasza suma nie przechwytuje ostatnich wyborów miasta, aby połączyć się z pierwszym miastem. Istnieje miast, które połączą się z pierwszym miastem. W końcu dodamy ten termin do sumy. $k=n-1$

(\binom{n - 1}{n - 2}) \cdot (n - 2) \cdot 1

$\binom{n-1}{n-2} \cdot (n-2) \cdot 1$

n - 1

$n-1$

Pozwól przekształcić formułę w formułę, którą podajesz, która jest również na stronie Wikipedii Held-Karp .

\sum_{k > = 2)} (\binom{n - 1}{k - 1}) \cdot (k - 1) \cdot ((n - 1) - (k - 1)) = \sum_{k > = 2)} \frac{(n - 1)!}{(k - 1)! (n - k)!} \cdot (k - 1) \cdot (n - k) = \sum_{k > = 2)} \frac{(n - 1)!}{k! (n - 1 - k)!} \cdot k \cdot (k - 1) = \sum_{k > = 2)} (\binom{n - 1}{k}) \cdot k \cdot (k - 1)

$\displaystyle \sum_{k>=2} \binom{n-1}{k-1} \cdot (k-1) \cdot ((n-1)-(k-1))= \sum_{k>=2} \frac{(n-1)!}{(k-1)!(n-k)!} \cdot (k-1) \cdot (n-k)= \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1)= \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1)$ Manipulowanie współczynnikami dwumianowymi prowadzi do: Tak więc liczba operacji w pierwszym faza to

\sum_{k >= 2} (\binom{n - 1}{k}) \cdot k \cdot (k - 1) = \sum_{k >= 2} \frac{(n - 1)!}{k! (n - 1 - k)!} \cdot k \cdot (k - 1) = \sum_{k >= 2} \frac{(n - 3)!}{(k - 2)! (n - 3 - (k - 2))!} \cdot (n - 1) \cdot (n - 2) = (n - 1) \cdot (n - 2) \sum_{k >= 2} (\binom{n - 3}{k - 2}) = (n - 1) \cdot (n - 2) \cdot 2^{n - 3}

$\displaystyle \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-3)!}{(k-2)!(n-3-(k-2))!} \cdot (n-1) \cdot (n-2)= (n-1) \cdot (n-2)\sum_{k>=2} \binom{n-3}{k-2}=(n-1) \cdot (n-2) \cdot 2^{n-3}$

(n - 1) \cdot (n - 2) \cdot 2^{n - 3} + (n - 1)

$(n-1) \cdot (n-2) \cdot 2^{n-3}+(n-1)$

Druga faza

Druga faza przywraca optymalną ścieżkę dzięki znakom, które zrobiliśmy w pierwszej fazie jednocześnie z odległościami obliczeniowymi.

Dla każdej optymalnej ścieżki „dla combination of k cities AND dla end-point city from this combination” uratowaliśmy miasto od ostatniego do ostatniego.

Aby prześledzić optymalną ścieżkę, musimy poprosić o pewną strukturę danych, aby zwrócić miasto od „do ostatniego” „dla combination of k cities AND dla end-point city from this combination”. Więc ta struktura danych musi być podobna
Map<combination of k cities, Map<last city, second-to-last city>>. Jako indeks combination of k citiesmożemy na przykład użyć binary_string[city id]=1 if city id is in combination. Musimy więc spojrzeć na wszystkie elementy, combination of k citiesaby zidentyfikować kombinację i zindeksować naszą strukturę danych. To daje nam liczbę operacji dla drugiej fazy:

\sum_{k >= 2}^{n - 1} k = \frac{(n) (n - 1)}{2} - 1

$\displaystyle \sum_{k>=2}^{n-1} k = \frac{(n)(n-1)}{2} - 1$

— dimathe47
źródło