Stellen Sie sich aus konzeptioneller Sicht vor, einen Stein in einen Teich fallen zu lassen und die Wellen zu beobachten. Die Routen würden den Teich und den Stein Ihre Ausgangsposition darstellen.
Natürlich würde der Algorithmus haben einen gewissen Anteil an n^2 Wege, wenn der Abstand zunimmt n suchen. Sie würden Ihre Startposition einnehmen und alle verfügbaren Pfade von diesem Punkt aus überprüfen. Rufen Sie dann rekursiv die Punkte am Ende dieser Pfade auf und so weiter.
Sie können die Leistung erhöhen, indem Sie nicht auf einem Pfad doppelspurig verfahren, indem Sie die Routen an einem Punkt, an dem sie bereits abgedeckt wurden, nicht erneut prüfen und Pfade, die zu lange dauern, aufgeben. Ein alternativer Weg ist der Ameise-Pheromon-Ansatz, bei dem Ameisen willkürlich von einem Startpunkt aus krabbeln und eine Duftspur hinterlassen, die mehr Ameisen auf einem bestimmten Pfad aufbaut. Wenn Sie (genügend) Ameisen sowohl vom Anfangspunkt als auch von den Endpunkten senden, wird der Pfad mit dem stärksten Geruch schließlich der kürzeste sein. Dies liegt daran, dass der kürzeste Weg in einem bestimmten Zeitraum öfter besucht wurde, da die Ameisen in einem gleichmäßigen Tempo gehen.
EDIT @ Spikie
Als weitere Erklärung, wie der Teich Algorithmus zu implementieren - Strukturen Potential Daten benötigt werden hervorgehoben:
Sie benötigen die Karte als Netzwerk zu speichern. Dies ist einfach ein Satz von nodes
und edges
zwischen ihnen. Ein Satz von nodes
bildet einen route
. Eine Kante verbindet zwei Knoten (möglicherweise beide den gleichen Knoten) und hat eine cost
wie distance
oder time
zugeordnet, um die Kante zu durchlaufen. Eine Kante kann entweder bidirektional oder unidirektional sein. Wahrscheinlich am einfachsten, nur unidirektionale Einsen zu haben und für eine Zweiwegefahrt zwischen Knoten zu verdoppeln (d. H. Eine Kante von A nach B und eine andere von B nach A).
Als Beispiel vorstellen, drei Bahnhöfe in einem Dreieck nach oben zeigend angeordnet. Es gibt auch noch drei weitere Stationen auf halbem Weg zwischen ihnen. Kanten verbinden alle benachbarten Stationen zusammen, das endgültige Diagramm wird ein umgekehrtes Dreieck haben, das innerhalb des größeren Dreiecks sitzt.
Label-Knoten von unten links beginnend, nach rechts und nach links und nach oben, wie A, B, C, D, E, F (F an der Spitze).
Es sei angenommen, die Kanten in beiden Richtungen durchlaufen werden kann. Jede Kante kostet 1 km.
Ok, so wollen wir von unten nach Route links A bis zur Bergstation F. Es gibt viele mögliche Routen, einschließlich derer, die auf sich selbst zurückgehen, zum Beispiel ABCEBDEF.
Wir haben eine Routine sagen, NextNode
, die eine node
akzeptiert und eine cost
und ruft sich selbst für jeden Knoten, den es reisen kann.
Klar, wenn wir diese Routine laufen lassen es alle Routen schließlich entdecken werden, einschließlich solcher, die in der Länge potentiell unendlich sind (zB ABABABAB usw.). Wir stoppen dies durch Überprüfung gegen die cost
. Immer wenn wir einen Knoten besuchen, der vorher nicht besucht wurde, setzen wir sowohl die Kosten als auch den Knoten, von dem wir gekommen sind, gegen diesen Knoten. Wenn ein Knoten besucht wurde, bevor wir die vorhandenen Kosten überprüfen, und wenn wir billiger sind, aktualisieren wir den Knoten und machen weiter (rekursiv). Wenn wir teurer sind, überspringen wir den Knoten. Wenn alle Knoten übersprungen sind, verlassen wir die Routine.
Wenn wir unseren Zielknoten treffen, verlassen wir auch die Routine.
So werden alle brauchbaren Routen überprüft, aber entscheidend sind nur die mit den geringsten Kosten. Am Ende des Prozesses hat jeder Knoten die niedrigsten Kosten, um zu diesem Knoten zu gelangen, einschließlich unseres Zielknotens.
Um die Route zu bekommen, arbeiten wir rückwärts von unserem Zielknoten. Da wir den Knoten, aus dem wir gekommen sind, zusammen mit den Kosten gespeichert haben, springen wir einfach rückwärts und bauen die Route auf. (Total) Kosten 0 - - Von Knoten Keine
Node B - Kosten 1 - von Knoten A
Knoten C - Kosten 2 - Vom Knoten B
Knoten A: Für unser Beispiel würden wir mit so etwas wie am Ende Knoten D - Kosten 1 - Von Knoten A
Knoten E - Kosten 2 - Von Knoten D/Kosten 2 - Von Knoten B (dies ist eine Ausnahme, da die Kosten gleich sind)
Knoten F - Kosten 2 - Von Knoten D
So ist der kürzeste Weg ADF.
Karten sind in der Regel zu groß, um Standard-Algorithmen für den kürzesten Pfad zuzulassen. Sie müssen einige Heuristiken erstellen, um einen Untergraphen auszuwählen. Außerdem können Sie völlig unterschiedliche, heuristische Ansätze (z. B. Autobahnen zuerst, ..) verwenden, um eine Route zu finden. –