Der Dijsktra-Algorithmus wurde auf das Problem des Handlungsreisenden angewendet

Ich bin ein Anfänger (totaler Neuling in der Theorie der rechnerischen Komplexität) und ich habe eine Frage.

Nehmen wir an, wir haben das Problem des Handlungsreisenden. Wird die folgende Anwendung der Dijkstra-Algorithmen es lösen?

Ausgehend von einem Startpunkt berechnen wir den kürzesten Abstand zwischen zwei Punkten. Wir gehen zum Punkt. Wir löschen den Quellpunkt. Dann berechnen wir den nächstkürzeren Abstandspunkt vom aktuellen Punkt und so weiter ...

Mit jedem Schritt verkleinern wir den Graphen, während wir den nächsten verfügbaren kürzesten Abstandspunkt verschieben. Bis wir alle Punkte besuchen.

Wird dies das Problem des Handlungsreisenden lösen?

Der Dijkstra-Algorithmus gibt einen Baum mit dem kürzesten Pfad von einem Startscheitelpunkt zu einem anderen Scheitelpunkt zurück, jedoch nicht unbedingt den kürzesten Pfad zwischen den anderen Scheitelpunkten oder eine kürzeste Route, die alle Scheitelpunkte aufruft.

Hier ist ein Gegenbeispiel, in dem der von Ihnen beschriebene gierige Algorithmus nicht funktioniert:

$a$$[a,b,c,d,a]$$a$$[a,b,d,c,a]$$a,b,c,d$$d,a$ in die Ausgangsstadt zurückkehren.

Wie sich bereits in den anderen Antworten herausgestellt hat, löst Ihr Vorschlag das Problem des Handlungsreisenden nicht effektiv. Lassen Sie mich bitte den besten Weg angeben, der auf dem Gebiet der heuristischen Suche bekannt ist (da ich Dijkstras Algorithmus in gewissem Zusammenhang mit diesem Gebiet der künstlichen Intelligenz sehe). .

$(u,v)$$(v,u)$ ), kann jedoch problemlos an die Alternative angepasst werden Bei der asymmetrischen Version.

Der beste Ansatz (ich bin mir dessen bewusst) besteht aus einer laufenden Depth-First - Branch-and-Bound heuristischen Suchalgorithmus , wo die Heuristik ist die Kosten für die Mindest Spanning Tree (MST). Da der MST in Polynomialzeit entweder mit dem Prim-Algorithmus oder mit dem berechnet werden kann Kruskal-Algorithmus , ist zu erwarten, dass Lösungen in angemessener Zeit zurückgegeben werden. Für eine wunderbare Diskussion dieser beiden Algorithmen empfehle ich Ihnen dringend, einen Blick darauf zu werfen das Algorithm Design Manual

Lassen Sie mich in der Tat betonen, dass seit der Annahme dieses Ansatzes auf dem Gebiet der Ableitung optimaler Grenzen dieses Problems keine großen Fortschritte zu verzeichnen waren, so dass ich es für eine heiße Frage auf dem Gebiet der kombinatorischen Suche halte.

Hoffe das hilft,

Ich habe keine Ahnung, wie jemand hier nicht bemerkt hat, dass die Anwendung des Dijkstra-Algorithmus in diesem Fall völlig unnötig wäre. Sie können diesen Greedy-Algorithmus implementieren, indem Sie einfach den nächstgelegenen Knoten auswählen, der apriori bekannt ist. Der Dijkstra-Algorithmus wird zum Erkennen von Pfaden verwendet, Sie machen jedoch jedes Mal nur einen Schritt. Dies findet offensichtlich nicht die optimale Lösung für den TSP, aber viele sehr gute Ansätze finden es auch nicht. Alle optimalen Lösungsfinder für TSP sind sehr rechenintensiv.

Die Antwort ist nein, das ist kein guter Weg, um das TSP-Problem zu lösen. Ein gutes Gegenbeispiel ist, wenn sich alle Punkte auf einer Linie befinden, wie zum Beispiel:

--5 ------------------ 3 ----- 1--0 --- 2 ---------- 4

Mit dem Dijsktra-Algorithmus würde der arme Verkäufer ab Punkt 0 zuerst zu 1, dann zu 2 und dann zu 3 ect wechseln. das ist nicht das optimale.

Ich hoffe, das hilft. Werfen Sie einen Blick auf das erste Kapitel in Steven S. Skienas exzellentem Buch "The Algorithm Design", in dem dieses Beispiel genauer erklärt wird.

Das TSP-Problem besteht nicht darin, den kürzesten Weg zwischen zwei Punkten zu finden, sondern eine Route zwischen allen Punkten zu erstellen, die optimal sind. Wenn Sie die optimale Route haben, können Sie mit Dijsktra den kürzesten Weg zwischen den einzelnen Punkten der Route ermitteln.