Polynomialzeitalgorithmus einen Hamilton-Weg in einem Graphen für die Suche nach [geschlossen]

Question

Gibt es eine Polynomialzeitalgorithmus einen Hamilton-Weg in einem Graphen für die Suche?

Mein Algorithmus ist N faktorielles und ist sehr langsam.

Answer 1

Sie fragte nur die rel="noreferrer">. einen Hamilton-Pfad zu finden, ist ein NP-vollständiges Problem. Einige NP-schwere Probleme in Polynomialzeit mit dynamischer Programmierung gelöst werden, aber (meines Wissens) ist dies nicht einer von ihnen.

Answer 2

Im Allgemeinen, wie die (Entscheidungsversion des) Hamilton-Pfad Problem NP-vollständig ist, können Sie kein Polynomialzeit-Algorithmus für die Suche nach Hamilton-Pfade zu erhalten hoffen. Sie können es leicht mit den üblichen N beschleunigen! → N ² 2 ^N dynamische Programmierung Trick (compute hp [v] [w] [S] = „Gibt es einen Weg, die Endpunkte v und w, und deren Scheitelpunkte hat, sind die Teilmenge S“für jede Teilmenge S und alle zwei Ecken v und w in es mit DP), aber das ist immer noch exponentiell.

Allerdings gibt es viele spezielle Arten von Graphen für die Hamilton-Pfade wird es immer geben, und sie können leicht (siehe Arbeit von Posa, Dirac, Erz, etc.) Zu finden

Zum Beispiel gilt Folgendes: Wenn jeder Knoten des Graphen Grad mindestens n / 2 , dann der Graph hat einen Hamilton-Pfad. Sie können in der Tat eine in O finden (n ² ) oder IIRC auch O (n log n), wenn Sie es geschickt machen.
[Grobe Skizze: Zuerst schließen Sie einfach alle Ecken in einigen „Hamilton-Zyklus“, macht nichts, wenn die Ränder tatsächlich im Graphen sind. Jetzt für jede Kante (v, w) des Zyklus, die nicht wirklich in der grafischen Darstellung ist, sollten Sie den Rest des Zyklus: v ... w. Als deg (v) + deg (w)> = n ist, gibt es aufeinanderfolgende x, y in der Liste (in dieser Reihenfolge), so daß w ein Nachbar von x und v ist ein Nachbar von y ist. [Beweis: Betrachten Sie {die Menge aller Nachbarn von w} und {die Menge aller Nachfolger in der Liste der Nachbarn von v}; sie müssen sich schneiden.] Jetzt Zyklus ändern [v ... xy ... wv] bis [vy ... wx ... v] stattdessen hat sie mindestens eine weniger ungültige Kante, so dass Sie am meisten brauchen, n Iterationen einen wahren Hamilton-Zyklus zu erhalten. Weitere Details hier .]

BTW: wenn das, was Sie suchen, ist nur ein Weg, der alle Rand enthält einmal, es ist eine Eulersche zu Fuß und für Graphen genannt, die es haben (Anzahl der Ecken ungeraden Grades 0 oder 2 ) kann man ganz leicht in Polynomialzeit gefunden werden (schnell).

Answer 3

Es ist NP vollständig. Aber wenn Sie es schaffen, eine gute Methode zu finden, lassen Sie mich wissen und ich werde Ihnen zeigen, wie reich werden.

Answer 4

Die Suche nach einem besseren Algorithmus für die kürzeste ist unwahrscheinlich, da es NP schwer ist. Aber es gibt einige Heuristiken, die Sie könnten versuchen, und vielleicht möchten Sie vielleicht Ihre Skriptum für diejenigen konsultieren;)

.

Für weniger Komplexität könnten Sie einen kurzen finden (ish) zu Fuß des Greedy-Algorithmus verwendet wird.

Answer 5

Hmmm .. Dies hängt davon ab, was Ihre Definitionen sind. Ein hamiltonsch Weg ist sicherlich NP-vollständig. Jedoch ist ein Hamilton-Operator zu Fuß, die Kanten besuchen und die Scheitelpunkte mehr als einmal (ja es ist immer noch genannt hamiltonsch so lange, wie Sie den Weg Bit am Ende hinzufügen) in O (p ^ 2logp) oder O (max (c ^ 2plogp berechnet werden , | E |)) so lange, wie Ihr Diagramm, das eine bestimmte Bedingung erfüllt, die Dirac ersten gemutmaßt und die Takamizawa bewährt. Siehe Takamizawa (1980) „Ein Algorithmus einen kurzen geschlossen Spanning zu Fuß in einem Diagramm für die Suche nach“.

Paul

Answer 6

Je nachdem, wie die Grafiken, die Sie mit arbeiten erzeugt Sie gierig Pfaderweiterung, indem Sie und dann eine zufällige Kante Swap Polynomzeit gegen eine zufällige Instanz erhalten erwarten könnte in der Lage sein, wenn das klemmt.

Das funktioniert gut gegen zufällig generierten relativ spärliche Graphen garantierten einen Hamilton-Operator zu Fuß haben.

Answer 7

Meine Frage: Zeigen Sie, dass ein Suchproblem RHAM für einen Hamilton-Zyklus in der grafischen Darstellung der Suche nach G Selbst reduzierbar Ein Suchproblem R ist selbst reduzierbar, wenn es Koch-reduzierbar auf ein Entscheidungsproblem ist
SR={ x : R(x) ≠ ∅ }