Hamiltonpfad Finder

Pseudocode

Es ist kein polynomieller Algorithmus bekannt, die ehrliche Formulierung ist also Backtracking mit Pruning. Erst das Pruning macht ihn überhaupt brauchbar.

Hamiltonweg(graph):
    für jeden Startknoten s:
        wenn backtrack([s], {s}): gib den Weg zurück
    gib keinen zurück

backtrack(weg, besucht):
    wenn besucht alle Knoten enthält: gib wahr zurück

    u = weg.letzter
    für jeden unbesuchten Nachbarn v von u:
        // Pruning, das sich selbst bezahlt macht:
        //  - ein unbesuchter Knoten jetzt unerreichbar -> scheitern
        //  - zwei oder mehr unbesuchte Knoten mit Grad 1
        //    im Restgraphen -> scheitern
        besucht.hinzufügen(v)
        wenn backtrack(weg + [v], besucht): gib wahr zurück
        besucht.entfernen(v)    // rückgängig, nächsten probieren

    gib falsch zurück

Das Erreichbarkeits-Pruning ist das wichtigste. Nach der Wahl eines Teilwegs führe einen schnellen Durchlauf über die unbesuchten Knoten aus; ist einer davon vom aktuellen Endpunkt abgeschnitten, ist der Zweig tot und kann sofort verworfen werden, statt erst nach dem Durchsuchen eines ganzen Teilbaums. Auf dünnen Graphen verwandelt das eine unlösbare Suche in eine schnelle, auch wenn der schlechteste Fall exponentiell bleibt.

Durchgerechnetes Beispiel, Schritt für Schritt

Suche einen Hamiltonweg von A auf einem Graphen mit fünf Knoten und sieh, warum derselbe Graph keinen Hamiltonkreis besitzt.

Beispielgraph: Ungerichtete Kanten A-B, B-C, C-D, D-E, dazu die beiden Sehnen A-C und B-D.

1. Zuerst die Grade. A hat Grad 2 (B und C), B hat 3 (A, C, D), C hat 3 (A, B, D), D hat 3 (B, C, E), und E hat Grad 1 mit D als einzigem Nachbarn. Ein Knoten vom Grad 1 muss Endpunkt jedes Hamiltonwegs sein, womit bereits feststeht, dass E ein Ende ist.
2. Zuerst A nach B probieren. Von A aus nimm B, von B aus C, von C aus ist der einzige unbesuchte Nachbar D, und von D aus der einzige unbesuchte E. Damit ist A-B-C-D-E vollständig und deckt alle fünf Knoten ab.
3. Es gibt eine zweite Lösung. Backtracking von A über den anderen Zweig liefert A-C-B-D-E, ebenfalls gültig. Hamiltonwege sind häufig nicht eindeutig, und ein Algorithmus, der den erstbesten zurückgibt, beantwortet eine Existenzfrage, keine Zählfrage.
4. Nun nach einem Kreis fragen. Ein Hamiltonkreis müsste vom letzten Knoten zu A zurückführen. Beide Wege enden in E, und E hat Grad 1 mit seiner einzigen Kante zu D. Eine Kante E-A existiert nicht, es gibt also keinen Hamiltonkreis.

Es existieren zwei Hamiltonwege, A-B-C-D-E und A-C-B-D-E, aber kein Hamiltonkreis. Der Knoten E vom Grad 1 klärt beide Fragen beinahe im Alleingang: er zwingt sich selbst zum Wegendpunkt und schließt jeden Kreis aus, da ein Kreis von jedem Knoten mindestens Grad 2 verlangt. Die Grade vor der Suche zu prüfen ist billig und oft entscheidend.

Komplexität und woher sie kommt

Zeit: O(V!) naiv, O(V^2·2^V) mit DP · Speicher: O(V·2^V) mit DP

Naives Backtracking durchsucht Permutationen und ist im schlechtesten Fall O(V Fakultät), was jenseits von etwa 12 Knoten aussichtslos ist. Held-Karp-Dynamikprogrammierung über Teilmengen schneidet weit besser ab: der Zustand ist eine Teilmenge besuchter Knoten zusammen mit dem aktuellen Endpunkt, was 2 hoch V mal V Zustände ergibt, und jeder Übergang kostet O(V), insgesamt also O(V hoch 2 mal 2 hoch V) Zeit und O(V mal 2 hoch V) Speicher. Das ist bis etwa 20 Knoten praktikabel, wo 2 hoch 20 mal 20 rund 20 Millionen Zustände sind. Das Problem ist NP-vollständig, ein polynomieller Algorithmus wird also nicht erwartet; gepruntes Backtracking endet auf realen dünnen Graphen dennoch oft rasch.

Wann Hamiltonscher Pfad passt und wann nicht

Kläre, welches Problem du wirklich hast, bevor du zu exponentieller Maschinerie greifst, denn zwei davon sind leicht.

Häufige Fehler

• Ihn mit dem Eulerproblem verwechseln. Die Namen klingen ähnlich, die Probleme unterscheiden sich enorm. Eulersch deckt Kanten ab und ist linear; hamiltonsch deckt Knoten ab und ist NP-vollständig. Das falsche zu lösen ist der teuerste Fehler, der hier möglich ist.
• Ohne Pruning suchen. Reines Backtracking ohne Erreichbarkeitsprüfung durchsucht riesige tote Teilbäume. Zu prüfen, ob alle unbesuchten Knoten vom aktuellen Endpunkt aus erreichbar bleiben und ob höchstens zwei von ihnen im Restgraphen Grad 1 haben, verkleinert die Suche typischerweise um Größenordnungen.
• Annehmen, ein Weg impliziere einen Kreis. Ein Hamiltonweg kann existieren, während kein Hamiltonkreis existiert, genau wie im Beispiel oben. Der Kreis verlangt zusätzlich eine Kante vom letzten Knoten zurück zum ersten, und jeder Knoten vom Grad 1 schließt ihn vollständig aus.
• Diracs Bedingung umgekehrt anwenden. Dirac besagt, dass ein Hamiltonkreis existiert, wenn jeder Knoten mindestens Grad V/2 hat. Die Umkehrung ist falsch: viele Graphen mit niedrigen Graden besitzen Hamiltonkreise, das Scheitern der Bedingung beweist also nichts.
• Erwarten, dass es skaliert. Jenseits von etwa 20 bis 25 Knoten kann eine exakte Antwort schlicht außer Reichweite liegen. Ist das eigentliche Ziel eine gute Route und kein Beweis, modelliere es als TSP und nutze Heuristiken.

Häufig gestellte Fragen

Was ist ein Hamiltonweg?

Ein Hamiltonweg ist ein Weg, der jeden Knoten eines Graphen genau einmal besucht. Kehrt er zusätzlich zum Startknoten zurück, ist es ein Hamiltonkreis. Anders als ein Eulerweg muss er nicht jede Kante benutzen, und er darf keinen Knoten erneut besuchen.

Warum ist das Finden eines Hamiltonwegs schwer?

Weil sich die Eigenschaft nicht lokal prüfen lässt. Eulerwege sind leicht, weil eine einfache Gradzählung an jedem Knoten die Existenz klärt, doch für das einmalige Besuchen jedes Knotens gibt es keinen vergleichbaren lokalen Test. Das Problem ist NP-vollständig, ein polynomieller Algorithmus ist nicht bekannt, und einen zu finden würde P gegen NP entscheiden.

Was ist der Unterschied zwischen Hamilton- und Eulerwegen?

Ein Hamiltonweg besucht jeden Knoten genau einmal und darf Kanten ignorieren. Ein Eulerweg benutzt jede Kante genau einmal und darf Knoten wiederbesuchen. Die eulersche Existenz ist in O(V + E) entscheidbar, indem man Knoten ungeraden Grades zählt; die hamiltonsche ist NP-vollständig.

Wie findet man einen Hamiltonweg?

Bei kleinen Graphen durch Backtracking von jedem möglichen Start mit starkem Pruning: brich einen Zweig ab, sobald ein unbesuchter Knoten unerreichbar wird oder sobald zwei oder mehr unbesuchte Knoten im Restgraphen Grad 1 haben. Bis etwa 20 Knoten liefert Held-Karp-Dynamikprogrammierung über Teilmengen in O(V hoch 2 mal 2 hoch V) eine definitive Antwort.

Wie hängen Hamiltonwege mit dem TSP zusammen?

Das Problem des Handlungsreisenden ist die gewichtete Optimierungsvariante: statt zu fragen, ob eine Tour über alle Knoten existiert, sucht es die billigste in einem vollständigen gewichteten Graphen. Die Entscheidung über die Existenz eines Hamiltonkreises lässt sich auf TSP reduzieren, weshalb TSP ebenfalls NP-schwer ist.