Was ist die dynamische Programmierung Algorithmus für die Suche nach einem Hamilton-Zyklus in einem Graphen?

Question

Was ist die dynamische Programmierung Algorithmus für die Suche nach einem Hamilton-Zyklus in einem ungerichteten Graphen?Ich habe irgendwo gesehen, dass es existiert ein Algorithmus mit O(n.2^n) Zeit Komplexität.

Answer 1

Es ist in der Tat eine O(n2ⁿ) dynamic-programming-Algorithmus für die Suche nach Hamiltonian cycles.Die Idee, das ist eine Allgemeine, die verringern kann viele O(n!) backtracking Ansätze zu O(n²2ⁿ) oder O(n2ⁿ) (auf Kosten von mehr Speicher), ist zu prüfen, Teilprobleme, die Sätze mit angegebenen "endpoints".

Hier, da Sie einen Zyklus starten können Sie an jeder Ecke.So beheben, rufen Sie es x.Die Teilprobleme werden würde:“Für eine gegebene Menge S und eines vertex v in S, gibt es einen Weg ab x und gehen durch alle Eckpunkte des S, und endet am v?" Dieses, nennen, sagen, poss[S][v].

Wie bei den meisten dynamische Programmierung Probleme, sobald Sie definieren die Teilprobleme der rest liegt auf der Hand:Schleife über alle 2ⁿ sets S of vertices in jeder "Erhöhung" um, und für jedes v in jedes solche S, Sie können berechnen poss[S][v] wie:

poss[S][v] = (es gibt einige u in S poss[S−{v}][u] Wahr ist, und eine Kante u->v vorhanden ist)

Schließlich gibt es einen Hamilton-Zyklus iff es ist ein vertex v so, dass eine Kante v->x existiert und poss[S][v] Wahr ist, wo S ist die Menge aller Scheitelpunkte (andere als x, je nachdem , wie man es definiert).

Wenn Sie wollen die tatsächlichen Hamiltonian cycle, anstatt nur zu entscheiden, ob man existiert oder nicht, machen Sie poss[S][v] speichern der tatsächlichen u das machte es möglich anstelle von nur True oder False;so können Sie verfolgen, wieder einen Weg an das Ende.

Answer 2

Das kann ich nicht bestimmten Algorithmus ausreißen, aber es gibt mehr über Hamilton-Zyklen auf Die Hamilton-Seite , als Sie wahrscheinlich jemals brauchen werden. :)

  

Diese Seite beabsichtigt, eine sein   umfassende Auflistung der Papiere,   Quellcode, Vordrucke, technische   Berichte, etc., auf dem   Internet über den Hamilton-Zyklus   und Hamilton-Pfad Probleme auch   wie einige Probleme im Zusammenhang.

( Original-URL, die derzeit 404 ), (< a href = "http://web.archive.org/web/20100324030526/http://alife.ccp14.ac.uk/memetic/~moscato/Hamilton.html" rel = "nofollow noreferrer"> Internet Archive )