Ich habe kürzlich erfahren, dass der A * Algorithmus auf das Problem des reisenden Verkäufers angewendet werden kann. Bot, wie genau definieren wir hier den Start und das Ziel und wie wenden wir Gewichte auf Knoten an (was ist die Heuristik)?
Würde mir jemand erklären, wie A * hier angewendet werden kann?
A * ist ein Derivat von Dijsktra, von dem ich denke, dass es auf diese Weise nicht verwendet werden kann. Zuerst startet der TSP im Allgemeinen von jedem Knoten. Noch wichtiger ist jedoch, dass diese Algorithmen versuchen, den kürzesten Weg zwischen zwei Punkten zu finden, unabhängig von der Anzahl der besuchten Knoten. Tatsächlich hängen sie von der Tatsache ab, dass der kürzeste Weg von S nach T über einen Knoten A, der Pfad von S nach A, irrelevant ist, wenn es die gleichen Kosten sind.
Ich sehe diese Funktion nur, wenn Sie ein neues Diagramm für die besuchten Knoten erstellt haben. In Ihrer Prioritätswarteschlange würden Sie beispielsweise die Gruppe der besuchten Knoten und den aktuellen Knoten platzieren. Dies würde dazu führen, dass möglicherweise $ n2 ^ n $ -Knoten untersucht werden (was nicht koindientlich die Laufzeit der dynamischen Programmierlösung für den TSP ist Ссылка ). Bis jetzt, nicht großartig, aber wenn Sie A * anstelle von Dijsktra verwenden, können Sie möglicherweise eine Heuristik finden, die in einer angemessenen Zeit läuft.
Um dies zu implementieren, wäre Ihr Startknoten (1, {}) und Ihr Endknoten wäre (1, {1..n}). Sie würden die Kantengewichte des ursprünglichen Graphen nachahmen. Wie für Vorschläge auf die Heuristik, du bist auf eigene Faust ..
A * kann hier angewendet werden, obwohl es möglicherweise nicht der beste Algorithmus ist.
Sie müssen von der Grafik der Städte und Straßen zwischen ihnen wegtreten. Definieren Sie stattdessen einen gerichteten Graphen, in dem Teilwege die Knoten sind und zwei Knoten x und y verbunden sind, wenn y aus konstruiert werden kann x durch Hinzufügen eines einzelnen "Schritts" im ursprünglichen Städte-Diagramm. Der Startknoten ist ein leerer Pfad. Der Zielknoten ist ein Pfad durch den alle Städte besucht werden. (Die Optimalität dieses Pfades wird durch die Eigenschaften der Heuristik und des A * -Algorithmus selbst gewährleistet.)
[ BEARBEITEN : Zuerst dachte ich, dass ein Pfad eine geordnete Liste von Städten sein sollte, aber jetzt glaube ich, dass der Vorschlag von @ spinning_plate, den Pfad durch ein Paar (Länge, Menge von Städten) darzustellen, ausreicht .]
Die Pfadkosten sind die gesamte zurückgelegte Strecke. Die Heuristik müsste eine zulässige Schätzung (normalerweise eine Unterschätzung) der gesamten minimalen Reisedauer sein.
Ein guter Kandidat für eine solche Schätzung könnte eine schnelle Annäherung der TSP (die Lösung eines entspannten Problems ) sein. Sie würden den Approximationsalgorithmus für jeden Knoten (Teilroute) auf der Menge der noch nicht abgedeckten Städte ausführen. Das gibt dem Algorithmus die notwendige Obergrenze für die Entfernung, die der Verkäufer noch gehen muss.
Wenn ich einen Hammer habe ( A * search ), ist jedes Problem ( TSP ) ein Nagel ( Wegfindung ).
>
Ja, theoretisch ist es möglich, das TSP-Problem in ein viel größeres Diagramm zu transformieren und A * search darauf zu verwenden. Aber bedauerlicherweise ist es nutzlos, weil es nicht skaliert (siehe Kommentar von spinning_plate). Selbst kleine Instanzen können Jahre brauchen, um auf moderne Hardware zu kommen.
TSP ist NP-vollständig , Wegfindung nicht.
Wenn es eine Schraube ist ( NP complete problem ), verwenden Sie einen Schraubenzieher ( metaheurtics, ... ).
Verwenden Sie Algorithmen wie Metaheuristiken ( Tabu-Suche , genetische Algorithmen, Simulated Annealing, ...). Für Software-Beispiele siehe Drools-Planer , openTS, jgap, cpsolver, ...
A * ist eine Erweiterung des Dijkstra-Algorithmus, bei dem die optimale Lösung zum Durchlaufen eines gerichteten Graphen berücksichtigt wird. Ich bin mir nicht sicher, dass dies für das TSP-Problem gilt.
Das TSP-Problem besagt, dass Sie die Reisedistanz minimieren möchten, während Sie jedes Ziel genau einmal besuchen. Der A * -Algorithmus benötigt eine Heuristik, um den Weg dorthin zu weisen, wo die optimale Lösung bekannt ist, eine gerade Linie zu sein (Sie müssen vorsichtig mit der A * Heuristik sein, um die Entfernung zum Ziel nicht zu überschätzen). Diese Dosis gilt nicht für das TSP-Problem.
Diese Frage enthält auch Informationen über den A * -Algorithmus und TSP-Problem.
Tags und Links algorithm a-star traveling-salesman