Algorithmus - Optimierung-Die Kürzeste Route Zwischen Mehreren Punkten

Problem: ich habe eine große Sammlung von Punkten. Jeder dieser Punkte hat eine Liste mit Referenzen auf andere Punkte mit dem Abstand zwischen Ihnen bereits berechnet und gespeichert. Ich brauche, um zu bestimmen, die kürzeste route beginnt von einem Ursprung und verläuft durch eine bestimmte Anzahl von Punkten an jedes Ziel.

Ex: ich bin im Urlaub und ich bin hier in einer bestimmten Stadt. Ich mache ein ONE-WAY-trip sehen die vier Städte und ich Reisen wollen die wenigsten Abstand möglich. Ich kann nicht unter der gleichen Stadt, mehr als einmal.

Aktuelle Lösung: im Moment bin ich gerade Durchlaufen jede Möglichkeit manuell und speichern Sie den kürzesten Weg. Dies funktioniert, fühlt sich aber ineffizient. Auch dieses problem wird schließlich erweitert, um auch eine Suche über mehrere origin-Punkte, um mehrere Ziel-Punkte, so dass ich denke, dass könnte explodieren der Suche.

Was ist der bessere Weg, um die Suche nach der kürzesten route?

  • Ist das ein direktionalen oder bidirektionalen Graphen? Kann ich nicht sagen.
  • Einige der Antworten hier (TSP, Floyd-Warshall, Zuerst der Breite, Branch-and-Bound) sind abgeleitet von Wild inkonsistente und sich widersprechende Interpretationen zu dieser Frage, so bin ich geneigt zu denken, dass die Frage hier nicht so formuliert, sehr gut.
  • Lassen Sie mich kurz formulieren: ein Beispiel ist, nehme ich einen Urlaub und ich bin ein Aufenthalt in einer Stadt. Ich möchte, um zu sehen, ALLE VIER Städte ab von mir und ich Reisen wollen die wenigsten Abstand möglich. Ich kann nicht unter der gleichen Stadt, mehr als einmal.
  • Ihre letzten editieren völlig verändert die Art und Weise interpretierte ich Ihre Frage.
  • Oh mein Gott. Das invalidiert Floyd-Warshall-basierte Lösung so schwer ist, dass Sie sehen sogar ziemlich lächerlich 🙂
  • Sorry! Es ist mein erstes mal hier veröffentlichen... 🙁

InformationsquelleAutor Chris Douglass | 2009-10-02
  1. 7

    Beantwortung der aktualisierten post, Ihre Lösung zu überprüfen, jede Möglichkeit ist optimal (zumindest niemand entdeckt hat bessere algorithmen so weit). Ja, das ist ein Handlungsreisender, dessen Essenz nicht berühren jeder Stadt, aber berühren jeden Stadt einmal. Wenn Sie nicht wollen, um die Suche für die besten Lösung möglich sein, können Sie es nützlich finden, verwenden Heuristiken, die das arbeiten schneller, erlauben jedoch begrenzte Abweichungen von ideal-Lösung.

    Für zukünftige Beantworter: Floyd-Warshall-Algorithmus und alle Floyd-ähnliche Variationen sind hier nicht anwendbar.

    • Fun fact: O(N^5) > O(N!) bis zu N = 8 🙂
    • Danke. Ich habe optimiert es etwas, durch das finden der sofortige Lösung zu finden, den kürzesten einzelnen Routen, die alle der Weg nach unten, dann bewegt sich auf einer Ebene suchen, dann verschieben auf eine andere Ebene (etc.) Ich denke, das ist eine Tiefe-zuerst-Suche?
    • Genannt werden kann, depth-first traversal, nicht Suche. Suche zielt darauf ab, jeder Besuch - Knoten, während Ihr Algorithmus zielt darauf ab, jeder Besuch Pfad und ist daher teurer.
    • Es ist nicht bekannt, Polynom-Zeit-Algorithmus. Allerdings bedeutet dies nicht, dass die überprüfung aller Möglichkeiten ist optimal. Es gibt durchaus algorithmen für das traveling salesman problem und Verwandte Probleme, die es ermöglichen, zu lösen große Probleme mit e.g tausenden von Städten
    • Pavel ist der Begriff optimal in dem Sinne, dass es die beste Lösung finden (unabhängig von der Laufzeit-Komplexität), auf beliebigen Daten-set.
    InformationsquelleAutor P Shved
  2. 3

    In der Regel sollten Sie einer strengen schlechten Varianten...
    Ich glaube, Sie sollten einige Variationen von Branch_and_bound Methode
    http://en.wikipedia.org/wiki/Branch_and_bound

    • ++ Ja. Dies ist ein tree-search-optimization-problem, also das branch-and-bound betrifft. Es kann entweder zuerst der Breite oder Tiefe-zuerst.
    InformationsquelleAutor Max
  3. 2

    Entweder bredth ersten Suche als norheim.se sagte oder Der Dijkstra-Algorithmus wäre mein Vorschlag als gut.

    InformationsquelleAutor
  4. 1

    Klingt Handelsreisenden-esque? Eine Lösung ist die Verwendung eine Optimierung der Technik, wie ein evolutionärer Algorithmus. Derzeit sind Sie dabei, eine erschöpfende Suche, die sehr langsam sehr schnell. Aber ich denke, das ist ziemlich viel, einen Handelsreisenden-problem und es wurde in Angriff genommen, die für mehrere Jahrzehnte, wenn nicht Jahrhunderte, und solche gibt es mehrere mögliche Weise anzugreifen. Google ist dein Freund.

    • seinen keine TSP da kann man Durchlaufen, in der gleichen Stelle mehr als einmal.
    • Ich dachte, die TDL beteiligten wissen, jeden Punkt, musste berührt werden? In meinem Fall gibt es keine spezifischen Punkte, die enthalten sein müssen, nur irgendwelche Punkte, die den kürzesten Weg von einem Ursprung.
    • es gibt viele Varianten von TSP, auch solche, die es einem Benutzer erlauben, zu besuchen die gleiche vertex mehrere Male.
    InformationsquelleAutor zenna
  5. 1

    Vielleicht ist das, was das ursprüngliche Plakat mit "Durchlaufen hat jeder die Möglichkeit manuell und speichern Sie den kürzesten Weg", aber ich dachte, ich möchte explizit zu machen, was zu sein scheint eine geplante Lösung.

    Nehme an, Sie haben bereits eine zwei-Punkt-shortest-path-Algorithmus-dies hat die klassische Lösungen für verschiedene Arten von Graphen. Angenommen, alle Entfernungen sind nicht-negative und d(A->B->C) = d(A->B) + d(B->C).

    Die essentials sind, dass der Pfad beginnt bei S geht durch eine dazwischenliegende Städte "abcd" und endet mit E:

    z.B. SabcdE, SacbdE, etc...

    Mit nur 4 intermediate Städte, Sie alle aufzuzählen, 24 Permutationen. Für jede permutation verwenden Sie Ihre kürzeste zwei-Punkt-Algorithmus zu berechnen, den Weg vom Kopf bis zum Schwanz, und seine Gesamt-Distanz.

    Dann die start-und Endpunkt gibt es 12 Möglichkeiten der Befestigung an einem von abcd und für jeden zwei Möglichkeiten für den Innenraum. Sie haben berechnet diese Abstände bereits, so dass Sie hinzufügen, auf die Distanz von S zu den Kopf und den Schwanz zu E. Wählen Sie mindestens. Also, wenn Sie haben die vorausberechnete mittlerer Entfernung für eine Feste Gruppe von inneren Städte, die Sie tun müssen, 12 zwei-Punkt-kürzeste-Pfad-Probleme für jedes paar von start-und end-Punkte.

    Diese offensichtlich skaliert schlecht mit Zunehmender Anzahl von Zwischenschritten Städte. Es ist mir nicht klar, dass es noch besser hätte machen können, es sei denn, Sie verhängen, größere Einschränkungen auf die graph-Struktur (ist das in einem physischen Euclidenan Raum? Dreiecksungleichung?).

    Meine Gedanken Beispiel: angenommen, alle zwischen Strecken zwischen den Städten sind O(1). Ohne Einschränkung auf dem Graphen, dann ist der Abstand von S zu jedem intermediate-Stadt 1000, mit Ausnahme eines 1. Gleiche für das Heck. So können Sie erzwingen, dass die erste Stadt, die besucht werden, um alles sein. Gehen Sie nun eine Ebene nach unten, nehmen Sie die erste Stadt, die sich als "start-Punkt". Gilt das gleiche argument: Sie können die beste Weg, gehen Sie zu jeder der folgenden Städte durch die Manipulation der Abstände im Diagramm.

    So scheint es, dass die Komplexität nicht geholfen werden kann, ohne zusätzliche Annahmen.

    InformationsquelleAutor Matt Kennel
  6. 1

    Dies ist der sehr Häufig und Echtzeit-situation kann man im Herbst.Google map user-interface zeigt Euch den Weg in der gleichen Reihenfolge, die Sie hinzufügen, in der Liste Ziel aus. es nicht geben Ihnen den optimalen Weg, obwohl Ihre eigenen Google maps API-Lösung bieten.

    Google maps API bietet die Lösung für dieses. In der Anfrage, um herauszufinden, den Pfad musst du die flag " optimizeWaypoints: true,'. Die Anfrage wird scheinen wie diese.

    var request = {
            origin: start,
            destination: end,
            waypoints: waypts,
            optimizeWaypoints: true,
            travelMode: google.maps.TravelMode.DRIVING
        };

    und Sie können sehen ganze code von dem Programm in den Quelltext anzeigen als komplettes Dienstprogramm entwickelt, die in javascript und HTML.

    Ich hoffe, es wird helfen.

    • Ihre website ist down buddy, so ist der link
    InformationsquelleAutor Abhishek Gahlout
  7. -2

    Scheint es, dass die Kanten des Graphen sind bidirektional. In diesem Fall wird der Algorithmus, den Sie suchen, ist Der Dijkstra-Algorithmus.

    InformationsquelleAutor James Jones
Schreibe einen Kommentar