Kürzeste Route Algorithmus - alle Knoten mit bekannten Start- und Ziel

-1

Ich versuche, einen Algorithmus, um herauszufinden, dass die kürzeste Route erzeugen kann, die folgenden Regeln unter BerücksichtigungKürzeste Route Algorithmus - alle Knoten mit bekannten Start- und Ziel

Die Start- und Endpunkte sind bekannt und fest
Besuchen Sie alle nur einmal Knoten ohne Wiederholung

zum Beispiel here

angebracht finden Sie ist jeder Algorithmus gibt es das kann verwendet werden, anstatt einfach die Summe aller möglichen Kombinationen zu berechnen und den niedrigsten Wert auszuwählen? Das ist ziemlich nutzlos, wenn Sie große Zahlen haben.

Grüße,

Quelle

2017-04-23 lightworks

Mögliches Duplikat von [Optimierte TSP-Algorithmen] (http: // stac koverflow.com/questions/7159259/optimized-tsp-algorithms) –

Das Problem ist im Wesentlichen TSP. Obwohl TSP den Verkäufer am selben Knoten starten und enden lässt, können Sie Ihr Problem in diesen transformieren - fügen Sie einen zusätzlichen Knoten hinzu und weisen Sie seinen Abstand von Anfang und Ende als klein und den Abstand zu jedem anderen Knoten als unendlich an. Dann ist jede optimale TSP-Route, die von dem zusätzlichen Knoten startet und endet, eine Lösung (oder die Umkehrung einer Lösung) für Ihr Problem. Es ist ein extrem schwieriges Problem zu lösen. –

-1

Graph in Problem erwähnt gerichtet ist, also Sie einen Blick auf Travelling Salesman Problem

zur detaillierten Erläuterung und Implementierung Besuch geeksforgeeks

Diese Lösung ist jedoch nicht durchführbar, dh NP-Hard haben sollte Daher können Sie auch einen Blick auf 2-approximation using MST werfen, der Ihnen eine Annäherung in der Antwort geben könnte

Quelle

2017-04-23 11:31:50 Ani

Der Dijkstra-Algorithmus wird verwendet, um den kürzesten Weg von Punkt A nach Z zu finden. In diesem Fall und unter Bezugnahme auf die genannten Regeln müssen jedoch alle Knoten zwischen Start- und Endpunkt Teil der Route sein. – lightworks

Die von Ihnen angegebene Verbindung ist eine 2-Annäherung an TSP, die eine MST verwendet. Das ist interessant, aber ich denke nicht, dass es die Frage wie geschrieben beantwortet. Es wäre auch besser, wenn Sie erwähnen, dass es eine Annäherung in der Antwort ist. –

Der erste Teil dieser Antwort sieht nicht gut aus. Betrachten wir zuerst die Bedingungen: Es gibt Start, Endknoten und alle Knoten müssen durchlaufen werden. Jetzt mit Prims Algo erhalten Sie einen Baum, der niedrigste Randkosten hat und Sie erhalten notwendigerweise eine lineare Art des Baums mit dem Anfangs- und Endknoten, der Blatt ist. Mit TSP ist die Lösung hier –

Kürzeste Route Algorithmus - alle Knoten mit bekannten Start- und Ziel

Antwort

Verwandte Themen