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

16

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 wierzchołkami i nieujemnej funkcji długości . Dla dowolnych wierzchołków i oraz dowolnego podzbioru wierzchołków, który wyklucza i , niech oznacza długość najkrótszej ścieżki hamiltonowskiej od 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\}]$

L (s, X, t) = {\begin{cases} ℓ (s, t) & if X = \emptyset_{} \\ min_{v \in X} (L (s, X ∖ {v}, v) + ℓ (v, t)) & otherwise \end{cases}

$L(s,X,t) = \begin{cases} \ell(s,t) & \text{if $X = \varnothing_{\strut} $} \\ \min_{v\in X}~ \big(L(s, X\setminus\lbrace v\rbrace, v) + \ell(v,t)\big) & \text{otherwise} \end{cases}$

Dla każdego wierzchołka , długością optymalną trasę podróży sprzedawca jest . Ponieważ pierwszy parametr jest stały we wszystkich wywołaniach rekurencyjnych, istnieje różnych podproblemów, a każdy podproblem zależy od co najwyżej innych. Zatem algorytm programowania dynamicznego działa w czasie . $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 , dla każdego , aby uzyskać dostęp do tabeli zapamiętywania. Jeśli podzbiory są reprezentowane przez liczby całkowite, liczby te wymagają 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?

ds.algorithms machine-models computing-over-reals

— Jeffε
źródło

Twój link „dziwnych rzeczy” jest zepsuty.

— Tyson Williams,

Naprawiłem link.

— Jeffε

12

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.

— David Eppstein
źródło

Przyzwyczaiłem się do tego, że model maszyny powinien zależeć od wielkości wejściowej

, ale jest trochę nieporadne w pozwoleniu, aby model maszyny zależał od algorytmu. Czy naprawdę chcesz, aby Twoja maszyna rozwiązała jakikolwiek problem w PSPACE w stałym czasie, o ile korzystasz już z przestrzeni wykładniczej?

n

$n$

— Jeffε

3

Dla mnie nie chodzi o to, czy model różni się w zależności od algorytmu, a bardziej o to, że model jest naprawiony, ale nie jest w stanie uruchomić wszystkich algorytmów (ponieważ zabrakło miejsca). Dla mnie to nie różni się tak bardzo od prawdziwych komputerów.

— David Eppstein,

1

Odpowiedź Davida nie przekonuje mnie. Istnieją tutaj dwa problemy. Jeden jest teoretyczny, drugi praktyczny. W ustawieniach teoretycznych bardziej naturalne jest precyzyjne określenie modelu i odpowiednia analiza czasu pracy. W praktyce nie jest łatwo stwierdzić, czy rzeczywiście zabraknie pamięci w konkretnym przypadku ze względu na różne optymalizacje, które można wykonać (i wykonać częściowe zapamiętywanie itp.), Jednak przy implementacji algorytmu będziemy musieli poradzić sobie z jak przechowujemy zestawy i indeksujemy w nich. Powyższy model nie pomaga w tym zakresie.

— Chandra Chekuri,

8

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 jeśli ): $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)$

— Oleksandr Bondarenko
źródło

1

Unikają więc problemu, ukrywając czynnik wielomianowy. Chcę wiedzieć, jaki jest czynnik wielomianowy!

— Jeffε

3

Zakładają, że współczynnik wielomianu jest

n^{2}

$n^2$ (patrz link w moim komentarzu).

— Oleksandr Bondarenko,