Ich habe über eine Erweiterung des Shortest Hamiltonian Path (SHP) -Problems nachgedacht und konnte keine Lösung finden. Ich weiß, dass es NP-komplett ist, aber ich dachte, ich würde hier nach Ideen fragen, da ich das Problem nicht einfach nur brutal erzwingen will.
Die Erweiterung ist ziemlich einfach: Wenn Sie einen ungerichteten, vollständigen, gewichteten Graphen mit n Scheitelpunkten erhalten, suchen Sie den kürzesten Hamilton-Pfad mit den Endscheitelpunkten v und u .
Bruteforce würde also immer noch die Zeit O ( n !) nehmen, da die verbleibenden n -2 Ecken in n zu sehen sind -2)! Wege. Ich habe versucht, einen Weg zu finden, um dieses etwas schneller zu lösen. Meine Bemühungen, einen Weg zu finden, dieses Problem auf eine nützliche Weise zu lösen, waren bisher fruchtlos.
Würde jemand eine Idee haben, wie man das Wissen der Endvertices ausnutzt? Vorzugsweise erklärt neben einigen Pseudocode. Es ist erforderlich, dass die gefundene Lösung optimal ist.
Ich denke, es könnte durch Integer-Programmierung gelöst werden, da das Wissen der Endknoten ziemlich begrenzt ist und es leicht macht, Zyklen zu vermeiden, aber es würde die Zusammensetzung des Problems nicht wirklich ausnutzen.
Wenn Sie den kürzesten Pfad zum Verbinden aller Knoten finden möchten, sollten Sie sich die Algorithmen des reisenden Verkäufers ansehen. Ich sehe nicht genau, warum Sie es als HSP angehen. Der einzige Grund, an den ich denken kann, ist, dass Sie Ihre Ausgangsstädte spezifizieren möchten, aber es sollte leicht sein, das zu beheben (wenn Sie das brauchen, kann ich es veröffentlichen), indem Sie Ihr Diagramm ein wenig ändern.
edit: Hinzufügen, wie Sie Ihr Diagramm optimieren
Füge einen Knoten hinzu (nenne ihn E) und verbinde ihn nur mit deinem Start- und Endknoten. Ein TSP berechnet eine Lösung für Ihr Problem, indem er alle Ihre Knoten verbindet. Da E nur erreichbar ist, indem man von Anfang zu E geht und dann endet, enthält die Lösung (ein Zyklus ja) Start - E - Ende. Dann entfernen Sie die 2 Kanten von und nach E und Sie haben die optimale Lösung. Innerhalb des TSP ist der Pfad von Anfang bis Ende optimal.
Sie können einen metaheuristischen Algorithmus verwenden. Es gibt viele Arten von ihnen (Lokale Suche, konstruktive Suche, etc.). Eine davon könnte auf folgenden basieren:
Für jedes x, das zu der Menge der Knoten X gehört:
- Finden Sie die Menge der nächstgelegenen Vertices zu x C.
- Filtern Sie die Menge C, um eine davon in den Pfad P aufzunehmen.
Wiederholen Sie dies, bis alle Scheitelpunkte von X im Pfad P enthalten sind.
Ende.
Tags und Links pseudocode graph shortest-path np-complete