Złożoność czasowa algorytmu Bellmana-Helda-Karpa dla TSP, weź 2

Ostatnie pytanie dotyczyło teraz klasycznego algorytmu programowania dynamicznego dla TSP, niezależnie od Bellmana i Held-Karpa . Algorytm jest powszechnie zgłaszany do działania w czasie . Jednak, jak niedawno zauważył jeden z moich studentów, ten czas działania może wymagać nieracjonalnie silnego modelu obliczeń.$O(2^n n^2)$

Oto krótki opis algorytmu. Dane wejściowe składają się z ukierunkowanego wykresu z n wierzchołkami i nieujemnej funkcji długości ℓ : E → R + . Dla dowolnych wierzchołków s i t oraz dowolnego podzbioru X wierzchołków, który wyklucza s i t , niech L ( s , X , t ) oznacza długość najkrótszej ścieżki hamiltonowskiej od s do $G=(V,E)$$n$$\ell\colon E\to\mathbb{R}^+$$s$$t$$X$$s$$t$$L(s,X,t)$$s$$t$ w indukowanym podrozdziale . Algorytm Bellmana-Helda-Karpa opiera się na następującej powtarzalności (lub, jak nazywają to ekonomiści i teoretycy kontroli, „równanie Bellmana”):$G[X\cup\{s,t\}]$

Dla każdego wierzchołka , długością optymalną trasę podróży sprzedawca jest l ( s , V ∖ { s } , s ) . Ponieważ pierwszy parametr s jest stały we wszystkich wywołaniach rekurencyjnych, istnieje Θ ( 2 n n ) różnych podproblemów, a każdy podproblem zależy od co najwyżej n innych. Zatem algorytm programowania dynamicznego działa w czasie O ( 2 n n 2 ) .$s$$L(s,V\setminus\{s\}, s)$$s$$\Theta(2^n n)$$n$$O(2^n n^2)$

A może to ?!

Standardowy model liczb całkowitych RAM umożliwia ciągłe manipulowanie liczbami całkowitymi za pomocą bitów , ale przynajmniej w przypadku operacji arytmetycznych i logicznych większe liczby całkowite muszą być podzielone na fragmenty wielkości słowa. (W przeciwnym razie mogą się zdarzyć dziwne rzeczy .) Czy nie dotyczy to również dostępu do dłuższych adresów pamięci? Jeśli algorytm wykorzystuje przestrzeń wielobiegunową, czy uzasadnione jest założenie, że dostęp do pamięci wymaga tylko stałego czasu?$O(\log n)$

W szczególności w przypadku algorytmu Bellmana-Helda-Karpa algorytm musi przekształcić opis podzestawu w opis podzestawu X ∖ { v } , dla każdego v , aby uzyskać dostęp do tabeli zapamiętywania. Jeśli podzbiory są reprezentowane przez liczby całkowite, liczby te wymagają n bitów i dlatego nie można nimi manipulować w stałym czasie; jeśli nie są reprezentowane przez liczby całkowite, ich reprezentacja nie może być użyta bezpośrednio jako indeks w tabeli zapamiętywania.$X$$X\setminus\{v\}$$v$$n$

Tak więc: jaki jest rzeczywisty asymptotyczny czas działania algorytmu Bellmana-Helda-Karpa?

Jest to mniej matematyczna odpowiedź niż filozoficzna, ale wolę myśleć o modelu pamięci RAM, który pozwala na ciągłe manipulowanie liczbami całkowitymi za pomocą pewnej liczby B bitów, która jest nieznana, ale co najmniej tak duża jak , gdzie S jest ilością miejsca wymaganą przez algorytm. Ponieważ jeśli liczby całkowite nie były tak duże, jak mógłbyś w ogóle zająć się pamięcią? W przypadku wielomianowych algorytmów czasu i przestrzeni jest on taki sam, jak w bitach O (log n), ale w przypadku algorytmów przestrzeni wykładniczej pozwala to uniknąć problemu.$\log_2 S$

Oczywiście, jeśli S przekroczy ilość pamięci, którą faktycznie masz, algorytm w ogóle się nie uruchomi. Lub będzie działał przez stronicowanie informacji do iz pamięci i powinieneś używać modelu hierarchii pamięci zamiast modelu RAM.

Dyskusja na ten temat znajduje się w najnowszej książce Fedora V. Fomina i Dietera Kratscha „ Dokładne algorytmy wykładnicze ”, w których określają czas działania w modelu pamięci RAM o koszcie jednostkowym i modelu pamięci RAM o koszcie logarytmicznym ( - maksymalna odległość między miastami i f ( n ) = O ∗ ( g ( n ) ), jeśli f ( n ) = O ( g ( n ) p o l y ( n ) ) ):$W$$f(n)=\mathcal{O}^{\ast}(g(n))$$f(n)=\mathcal{O}(g(n)poly(n))$

$\mathcal{O}^{\ast}(2^n)$$2^n\log Wn^{\mathcal{O}(1)}$$2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$