Zeitkomplexität des Bellman-Held-Karp-Algorithmus für TSP, Take 2

In einer aktuellen Frage wurde der heute klassische dynamische Programmieralgorithmus für TSP erörtert, der unabhängig von Bellman und Held-Karp entwickelt wurde . Es wird allgemein berichtet, dass der Algorithmus in $O(2^n n^2)$ -Zeit ausgeführt wird. Wie einer meiner Studenten kürzlich betonte, erfordert diese Laufzeit möglicherweise ein unangemessen leistungsfähiges Rechenmodell.

Hier ist eine kurze Beschreibung des Algorithmus. Die Eingabe besteht aus einem gerichteten Graphen $G=(V,E)$ mit $n$ Eckpunkten und einer nicht negativen Längenfunktion $\ell\colon E\to\mathbb{R}^+$ . Für alle Scheitelpunkte $s$ und $t$ und jede Teilmenge $X$ von Scheitelpunkten, die $s$ und $t$ , bezeichnen $L(s,X,t)$ die Länge des kürzesten Hamilton-Pfades von $s$ nach $t$im induzierten Teilgraphen $G[X\cup\{s,t\}]$ . Der Bellman-Held-Karp-Algorithmus basiert auf der folgenden Wiederholung (oder, wie Ökonomen und Kontrolltheoretiker es gerne nennen, „Bellman-Gleichung“):

Für jeden Scheitelpunkt ist die Länge des optimalen Verkäufer Tour reisen . Da der erste Parameter in allen rekursiven Aufrufen konstant ist, gibt es verschiedene Unterprobleme, und jedes Unterproblem hängt von höchstens anderen ab. Somit läuft der dynamische Programmieralgorithmus in der Zeit .L ( s , V ∖ { s } , s ) s Θ ( 2 n n ) n O ( 2 n n 2$s$$L(s,V\setminus\{s\}, s)$$s$$\Theta(2^n n)$$n$$O(2^n n^2)$

Oder doch ?!

Das standardmäßige Ganzzahl-RAM-Modell ermöglicht die zeitkonstante Manipulation von Ganzzahlen mit -Bits. Zumindest für arithmetische und logische Operationen müssen jedoch größere Ganzzahlen in wortgroße Blöcke aufgeteilt werden. (Andernfalls können seltsame Dinge passieren.) Gilt dies nicht auch für den Zugriff auf längere Speicheradressen? Wenn ein Algorithmus Superpolynomraum verwendet, ist es vernünftig anzunehmen, dass Speicherzugriffe nur konstante Zeit erfordern?$O(\log n)$

Insbesondere für den Bellman-Held-Karp-Algorithmus muss der Algorithmus die Beschreibung der Teilmenge in die Beschreibung der Teilmenge für jedes umwandeln , um auf die Notizentabelle zuzugreifen. Wenn die Teilmengen durch Ganzzahlen dargestellt werden, benötigen diese Ganzzahlen Bits und können daher nicht in konstanter Zeit bearbeitet werden. Wenn sie nicht durch ganze Zahlen dargestellt werden, kann ihre Darstellung nicht direkt als Index in der Memoization-Tabelle verwendet werden.X ∖ { v } v $X$$X\setminus\{v\}$$v$$n$

Also: Was ist die tatsächliche asymptotische Laufzeit des Bellman-Held-Karp-Algorithmus?

Dies ist weniger eine mathematische als eine philosophische Antwort, aber ich ziehe ein RAM-Modell vor, das eine zeitlich konstante Manipulation von Ganzzahlen mit einer Anzahl B von Bits ermöglicht, die unbekannt, aber mindestens so groß wie , wobei S ist ist die Menge an Speicherplatz, die der Algorithmus benötigt. Denn wenn die ganzen Zahlen nicht so groß wären, wie könnten Sie dann überhaupt Ihr Gedächtnis ansprechen? Für polynomielle Zeit- und Raumalgorithmen ist es dasselbe wie für O (log n) Bits, aber für exponentielle Raumalgorithmen vermeidet es das Problem.$\log_2 S$

Wenn S die tatsächlich vorhandene Speicherkapazität überschreitet, wird Ihr Algorithmus natürlich überhaupt nicht ausgeführt. Oder es wird ausgeführt, indem Informationen in und aus dem Speicher ausgelagert werden, und Sie sollten ein Speicherhierarchiemodell anstelle des RAM-Modells verwenden.

In dem kürzlich erschienenen Buch von Fedor V. Fomin und Dieter Kratsch " Exakte Exponentialalgorithmen ", in dem sie die Laufzeit im Stückkosten-RAM-Modell und im Protokollkosten-RAM-Modell ( - die maximale Entfernung) angeben, wird dieses Problem diskutiert zwischen den Städten und wenn ):f ( n ) = O * ( g ( n ) ) 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))$

2 n logW n O ( 1 ) 2 n logW n O ( 1 ) ∉ O * ( 2 n$\mathcal{O}^{\ast}(2^n)$ und (Anmerkung, ).$2^n\log Wn^{\mathcal{O}(1)}$$2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$