Problem: Ich habe eine große Sammlung von Punkten. Jeder dieser Punkte hat eine Liste mit Referenzen zu anderen Punkten, deren Abstand bereits berechnet und gespeichert wurde. Ich muss die kürzeste Route bestimmen, die von einem Ausgangspunkt beginnt und eine bestimmte Anzahl von Punkten an ein beliebiges Ziel durchläuft.
Beispiel: Ich bin im Urlaub und bleibe in einer bestimmten Stadt. Ich mache einen EINFACHEN Ausflug, um ALLE vier Städte zu sehen, und ich möchte die geringste mögliche Entfernung reisen. Ich kann die Stadt nicht mehr als einmal besuchen.
Aktuelle Lösung: Im Moment durchsuche ich jede Möglichkeit manuell und speichere den kürzesten Weg. Das funktioniert, fühlt sich aber ineffizient an. Außerdem wird dieses Problem möglicherweise erweitert, um die Suche von mehreren Ursprungspunkten zu mehreren Zielpunkten zu berücksichtigen, sodass der Suchraum möglicherweise explodiert.
Was ist der beste Weg, nach der kürzesten Route zu suchen?
Wenn Sie auf den aktualisierten Post antworten, ist Ihre Lösung, jede Möglichkeit zu prüfen, optimal (zumindest hat noch niemand bessere Algorithmen gefunden). Ja, das ist ein reisender Verkäufer, der nicht jede Stadt berührt, sondern jede Stadt einmal berührt. Wenn Sie nicht nach der bestmöglichen Lösung suchen möchten, ist es möglicherweise hilfreich, Heuristiken zu verwenden, die schneller funktionieren, aber eine begrenzte Diskrepanz von der idealen Lösung zulassen.
Für zukünftige Antworten: Floyd-Warshall-Algorithmus und alle Floyd-ähnlichen Variationen sind hier nicht anwendbar .
Entweder gibt es eine erste Suche wie norheim.se oder Dijkstras Algorithmus wäre auch mein Vorschlag.
Dies ist die gängige Situation in Echtzeit, in die jeder hineinfallen kann.Auf der Benutzeroberfläche von Google Maps erhalten Sie den Pfad in derselben Reihenfolge, den Sie in der Zielliste hinzufügen. Es bietet Ihnen nicht den optimalen Weg, obwohl die eigene Google Maps API die Lösung bietet.
Google Maps API bietet die Lösung dafür. In der Anforderung, den Pfad zu finden, müssen Sie das Flag 'optimizeWaypoints: true' angeben. Die Anfrage wird so aussehen.
%Vor%und Sie können den gesamten Code des Dienstprogramms in der Ansichtsquelle sehen, da das vollständige Dienstprogramm in JavaScript und HTML entwickelt wird.
Ich hoffe, es wird helfen.
Das klingt fahrtverkäuferisch? Eine Lösung besteht darin, eine Optimierungstechnik wie einen evolutionären Algorithmus zu verwenden. Momentan machen Sie eine erschöpfende Suche, die sehr schnell sehr langsam wird. Aber ich denke, das ist so etwas wie das Problem eines reisenden Verkäufers, und es wird seit mehreren Jahrzehnten, wenn nicht gar Jahrhunderten, angegangen, und es gibt verschiedene Angriffsmöglichkeiten. Google ist dein Freund.
Vielleicht bedeutet das ursprüngliche Poster, dass man "jede Möglichkeit manuell durchläuft und den kürzesten Pfad speichert", aber ich dachte, ich möchte explizit eine grundlegende Lösung machen.
Nehmen Sie an, Sie haben bereits einen Zwei-Punkt-Algorithmus für den kürzesten Pfad - dies hat klassische Lösungen für verschiedene Arten von Graphen. Angenommen, alle Abstände sind nichtnegativ und d (A - & gt; B- & gt; C) = d (A - & gt; B) + d (B & ndash; & gt; C).
Das Wesentliche ist, dass der Pfad bei S beginnt, durch eine der Zwischenstädte "abcd" geht und mit E endet:
z.B. SabcdE, SacbdE, etc ...
Mit nur 4 Zwischenstädten listen Sie alle 24 Permutationen auf. Für jede Permutation verwenden Sie Ihren kürzesten Zwei-Punkt-Algorithmus, um den Weg von Kopf bis Fuß und seine Gesamtdistanz zu berechnen.
Dann gibt es bei gegebenem Anfangs- und Endpunkt 12 Möglichkeiten, die zu einem von abcd und für jede zwei Möglichkeiten für das Innere gehören. Du hast diese Abstände bereits berechnet, also addierst du den Abstand von S zum Kopf und den Schwanz zu E. Wähle Minimum. Wenn Sie also die Zwischenabstände für einen festen Satz von Innenstädten vorberechnet haben, müssen Sie 12 Probleme mit dem zweitkleinsten Pfad für jedes Paar von Start- und Endpunkten machen.
Bei der steigenden Anzahl von Zwischenstädten ist das offensichtlich schlecht. Es ist mir nicht klar, dass es besser funktionieren könnte, wenn man die Graphenstruktur nicht stärker einschränkt (ist dies in einem physikalischen euklidischen Raum? Dreiecksungleichheit?).
Mein Gedankenbeispiel: Angenommen, alle Zwischenabstände zwischen Städten sind O (1). Ohne Beschränkung auf den Graphen kann der Abstand von S zu irgendeiner Zwischenstadt 1000 sein, außer dass 1 gleich ist. Gleiches gilt für den Schwanz. So können Sie die erste Stadt, die besucht wird, zwingen, alles zu sein. Gehen Sie nun eine Ebene nach unten, nehmen Sie die erste Stadt als "Startpunkt". Wenden Sie das gleiche Argument an: Sie können den besten Pfad zu einer der folgenden Städte machen, indem Sie die Entfernungen im Diagramm manipulieren.
Es scheint also, dass der Komplexität ohne zusätzliche Annahmen nicht geholfen werden kann.
Es scheint, dass die Kanten Ihres Diagramms bidirektional sind. In diesem Fall ist der von Ihnen gesuchte Algorithmus Dijkstras Algorithmus .
Tags und Links algorithm search mathematical-optimization routes