Hamilton-Pfad-Problem

Es gibt n! verschiedene Sequenzen von Scheitelpunkten, die Hamilton-Pfade in einem gegebenen n-Vertex-Graphen sein könnten (und in einem vollständigen Graphen sind), so dass ein Brute-Force-Suchalgorithmus, der alle möglichen Sequenzen testet, sehr langsam wäre.Ein früher exakter Algorithmus zum Finden eines Hamilton-Zyklus auf einem gerichteten Graphen war der enumerative Algorithmus von Martello. Ein Suchverfahren von Frank Rubin teilt die Kanten des Graphen in drei Klassen ein: diejenigen, die im Pfad sein müssen, diejenigen, die nicht im Pfad sein können, und unentschieden. Während die Suche fortschreitet, klassifiziert ein Satz von Entscheidungsregeln die unentschiedenen Kanten und bestimmt, ob die Suche angehalten oder fortgesetzt werden soll. Der Algorithmus unterteilt den Graphen in Komponenten, die separat gelöst werden können. Außerdem kann ein dynamischer Programmieralgorithmus von Bellman, Held und Karp verwendet werden, um das Problem in der Zeit O(n2 2n) zu lösen. Bei dieser Methode bestimmt man für jede Menge S von Knoten und jeden Knoten v in S, ob es einen Pfad gibt, der genau die Knoten in S abdeckt und bei v endet. Für jede Wahl von S und v existiert ein Pfad für (S,v) dann und nur dann, wenn v einen solchen Nachbarn w hat, dass ein Pfad für (S – v,w) existiert, der aus bereits berechneten Informationen im dynamischen Programm nachgeschlagen werden kann.

Andreas Björklund lieferte einen alternativen Ansatz, der das Einschluss-Ausschluss-Prinzip verwendet, um das Problem des Zählens der Anzahl der Hamilton-Zyklen auf ein einfacheres Zählproblem zu reduzieren, nämlich das Zählen von Zyklusabdeckungen, das durch die Berechnung bestimmter Matrix-Determinanten gelöst werden kann. Mit dieser Methode zeigte er, wie man das Hamilton-Zyklus-Problem in beliebigen n-Vertex-Graphen durch einen Monte-Carlo-Algorithmus in der Zeit O(1.657n) lösen kann; für bipartite Graphen kann dieser Algorithmus weiter auf die Zeit o(1.415n) verbessert werden.

Für Graphen von maximalem Grad drei kann eine sorgfältige Backtracking-Suche einen Hamilton-Zyklus (falls einer existiert) in der Zeit O(1.251n) finden.

Hamiltonsche Pfade und Zyklen können mit einem SAT-Solver gefunden werden.

Aufgrund der Schwierigkeit, die Hamiltonschen Pfad- und Zyklenprobleme auf konventionellen Computern zu lösen, wurden sie auch in unkonventionellen Modellen des Rechnens untersucht. Leonard Adleman zeigte zum Beispiel, dass das Hamilton-Pfad-Problem mit einem DNA-Computer gelöst werden kann. Unter Ausnutzung der Parallelität, die chemischen Reaktionen innewohnt, kann das Problem mit einer Anzahl von chemischen Reaktionsschritten gelöst werden, die linear zur Anzahl der Eckpunkte des Graphen ist; allerdings ist eine faktorielle Anzahl von DNA-Molekülen erforderlich, um an der Reaktion teilzunehmen.

Eine optische Lösung für das Hamilton-Problem wurde ebenfalls bereits vorgeschlagen. Die Idee ist, eine graphähnliche Struktur aus optischen Kabeln und Strahlteilern zu schaffen, die von Licht durchquert wird, um eine Lösung für das Problem zu konstruieren. Der Schwachpunkt dieses Ansatzes ist die benötigte Energiemenge, die exponentiell mit der Anzahl der Knoten ist.