Mit Solver Reisen Salesman Hamilton-Pfad zu entscheiden,

Question

Dies ist für ein Projekt, wo ich gefragt werde, eine Heuristik für das Handlungsreisende Optimierungsproblem und auch das Hamilton-Pfad oder Zyklus Entscheidungsproblem zu implementieren. Ich brauche keine Hilfe bei der Umsetzung selbst, sondern habe eine Frage nach der Richtung, in Ich gehe.

Ich habe bereits eine TSP-Heuristik auf einem genetischen Algorithmus basiert: Es nimmt einen vollständigen Graphen, beginnt mit einem Satz von Zufall Lösungen als eine Population, und arbeitet, um die Bevölkerung für eine Reihe von Generationen zu verbessern. Kann ich es auch die Hamilton-Pfad oder Zyklus Probleme zu lösen? Anstatt zu optimieren, den kürzesten Weg zu bekommen, möchte ich nur prüfen, ob es einen Weg.

Nun kann jeder vollständiger Graph einen Hamilton-Pfad in ihm hat, so dass die TSP-Heuristik auf jedes Graphen erweitert werden müßte. Dies könnte, indem die Kanten etwas unendlich Wert durchgeführt werden, wenn es kein Weg zwischen zwei Städten ist, und Zurückführen des ersten Weges, der ein gültiger Hamilton-Pfad ist.

Ist das der richtige Weg, es zu nähern? Oder sollte ich eine andere Heuristik für Hamilton-Pfad? Meine größte Sorge ist, ob es ein gangbarer Weg ist, da ich etwas sicher sein kann, dass TSP-Optimierung funktioniert (weil Sie mit Lösungen beginnen und verbessern), aber nicht, wenn ein Hamilton-Pfad decider jeden Pfad in einer festen Anzahl von Generationen finden würde.

Ich nehme an, der beste Ansatz, es selbst zu testen sei, aber ich bin durch die Zeit eingeschränkt und dachte, dass ich, bevor sie hinunter diesen Weg fragen würde ... (ich eine andere Heuristik für Hamilton-Pfad finden könnte stattdessen)

Answer 1

Sie wissen nicht, ob Sie jemals eine Antwort auf diese Frage bekam. Der einfache Trick ist, einen Dummy-Punkt hinzuzufügen, die einen Abstand von Null auf alle anderen Punkte haben. Lösen Sie das TSP und loszuwerden, die Dummy-Punkt - was bleibt, ist der Hamilton-Pfad. Einfach!

Answer 2

Beide sind NP vollständige Probleme, so definitions Sie die Eingabe umwandeln und den gleichen Algorithmus verwenden; -)

Aber die Grundidee sollte funktionieren. Natürlich müssen Sie die Generierung neuer Wege und die Erfolgskriterien ändern.

EDIT: BTW: Es gibt einen Vorschlag für einen randomisierten Algorithmus: http://en.wikipedia.org/wiki/Hamiltonian_path_problem