Finden Sie den kürzesten Weg in einem Graphen, die bestimmte Knoten besucht

StackOverflow https://stackoverflow.com/questions/222413

  •  03-07-2019
  •  | 
  •  

Frage

Ich habe einen ungerichteten Graphen mit etwa 100 Knoten und etwa 200 Kanten. Ein Knoten ist ‚Start‘ bezeichnet, ist ein ‚Ende‘, und es gibt etwa ein Dutzend der Bezeichnung ‚mustpass‘.

Ich brauche den kürzesten Weg durch diesen Graphen zu finden, die auf ‚Start‘ beginnt, endet am ‚Ende‘, und geht durch alle ‚mustpass‘ Knoten (in beliebiger Reihenfolge).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt ist die grafische Darstellung in Frage - es ist ein Maislabyrinth in Lancaster, PA)

steht für
War es hilfreich?

Lösung

Alle anderen vergleichen dies dem Reiseproblem wahrscheinlich Ihre Frage nicht sorgfältig gelesen hat. In TSP, das Ziel ist es, den kürzesten Zyklus zu finden, die zu Besuch alle die Ecken (a Hamilton-Zyklus) - es entspricht mit alle Knoten Bezeichnung 'mustpass'

In Ihrem Fall, da Sie nur etwa ein Dutzend der Bezeichnung ‚mustpass‘ haben, und da 12! eher klein ist (479001600), können Sie einfach alle Permutationen von nur versuchen, den Knoten ‚mustpass‘ und von ‚Start‘ bis ‚Ende‘, die die ‚mustpass‘ Knoten in dieser Reihenfolge besucht auf dem kürzesten Weg finden - es wird einfach sein, die Verkettung der kürzesten Wege zwischen jeweils zwei aufeinanderfolgenden Knoten in dieser Liste.

Mit anderen Worten, findet zunächst den kürzesten Abstand zwischen jedem Paar von Scheitelpunkten (Sie Dijkstra-Algorithmus oder andere, aber mit diesen kleinen Zahlen (100 Knoten) verwenden können, auch die einfachste-to-Code Floyd-Warshall-Algorithmus in der Zeit ausgeführt wird). Dann, wenn Sie diese in einer Tabelle haben, versuchen alle Permutationen Ihrer ‚mustpass‘ Knoten, und den Rest.

So etwas wie folgt aus: 

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Natürlich ist das nicht wirklich Code ist, und wenn Sie den tatsächlichen Pfad möchten, müssen Sie im Auge behalten müssen, um deren Permutation den kürzesten Abstand gibt, und was auch alle Paare kürzesten Wege sind, aber Sie bekommen die Idee. )

Es wird höchstens ein paar Sekunden auf jeder angemessene Sprache läuft in :)
[Wenn Sie n Knoten und k 'mustpass' Knoten, seine Laufzeit ist O (n 3 ) für den Floyd-Warshall seits und O (k! N) für die alle Permutationen Teil haben, und 100 ^ 3 + (12!) (100) praktisch Erdnüsse, wenn Sie einige wirklich restriktive Einschränkungen haben.]

Andere Tipps

Djikstra-Algorithmus die kürzesten Wege zwischen all den kritischen Knoten finden (Start, Ende und muss Pass), dann ein depth-first Traversal sollte Ihnen den kürzesten Weg durch die resultierenden Subgraphen sagt, dass alle Knoten berührt beginnen ... mustpasses ... end

Eigentlich ist das Problem, das Sie geschrieben ähnlich der Handlungsreisende, aber ich denke, näher an einem einfachen Wegfindung Problem. Anstatt um jeden einzelnen Knoten zu besuchen, müssen Sie einfach einen bestimmten Satz von Knoten in kürzester Zeit (Entfernung) möglich besuchen.

Der Grund dafür ist, dass, anders als bei dem Reiseproblem, ein Maislabyrinth wird nicht zulassen, dass direkt von einem Punkt zu einem anderen Punkt auf der Karte reisen, ohne durch andere Knoten passieren dorthin zu gelangen.

Ich würde A * Wegfindung als eine Technik zu betrachten tatsächlich empfehlen. Sie setzen diese mit der Entscheidung auf die zu denen der Zugang direkt anderen Knoten haben die Knoten, und was die „Kosten“ von jedem Sprung von einem bestimmten Knoten ist. In diesem Fall sieht es aus wie jeder „Hop“ von gleich Kosten sein könnte, da die Knoten relativ eng beieinander liegenden scheinen. A * Anhand dieser Informationen können den kostengünstigsten Pfad zwischen zwei beliebigen Punkten finden. Da Sie von Punkt A erhalten müssen nach Punkt B und etwa 12 dazwischen, auch einen Brute-Force-Ansatz Wegfindung würde nicht schaden.

besuchen

Nur eine Alternative zu betrachten. Es sieht bemerkenswert wie das Reiseproblem, und das ist gute Papiere bis auf lesen, aber näher betrachten und Sie werden feststellen, dass seine einzigen overcomplicating Dinge zu sehen. Diese ^ _ ^ kommt aus dem Geist eines Videospiels Programmierer, bevor mit dieser Art von Dingen behandelt wird.

Dies ist zwei Probleme ... Steven Lowe dies wies darauf hin, aber nicht genug, um in Bezug auf die zweite Hälfte des Problems geben.

Sie sollten zuerst die kürzesten Wege zwischen allen Ihren kritischen Knoten (Start, Ende, mustpass) entdecken. Sobald diese Wege entdeckt werden, kann man ein vereinfachtes Diagramm, konstruiert, wobei jede Kante in dem Graphen ein neuen Pfad von einem kritischen Knoten zu einem anderen in dem ursprünglichen Graphen ist. Es gibt viele Wegfindung Algorithmen, die Sie den kürzesten Weg nutzen können hier zu finden.

Wenn Sie diese neuen Graphen haben, aber Sie haben genau die reisenden Handelsvertreters Problem (na ja, fast ... Keine Notwendigkeit, zum Ausgangspunkt zurückzukehren). Jede der Beiträge über diese, wie oben erwähnt, gilt.

Andrew Top hat die richtige Idee:

1) Djikstra-Algorithmus 2) Einige TSP-Heuristik.

Ich empfehle die Lin-Kernighan Heuristik: es ist eines der bekanntesten für jedes NP vollständiges Problem. Die einzige andere Sache zu erinnern ist, dass, nachdem Sie das Diagramm wieder nach Schritt 2 erweitert heraus, Sie Loops in Ihrem erweiterten Pfad haben, so sollten Sie gehen um Kurzschließen diejenigen (Blick auf den Grad der Scheitelpunkte auf Ihrem Weg).

Ich bin eigentlich nicht sicher, wie gut diese Lösung für die optimale relative sein wird. Es gibt wahrscheinlich einige pathologische Fälle mit Kurzschluss zu tun. Schließlich sieht dieses Problem viel wie Steiner Baum: http://en.wikipedia.org/wiki/Steiner_tree und man kann definitiv nicht annähernd Steiner Tree von nur Ihre Diagramm Vertrag und läuft Kruskals zum Beispiel.

Dies ist nicht ein TSP Problem und nicht NP-schwer, weil die ursprüngliche Frage erfordert nicht, dass muss Pass Knoten nur einmal besucht werden. Dies macht die Antwort viel, viel einfacher, nur Brute-Force nach einer Liste von kürzesten Wege zwischen allen muss Pass Knoten über Dijkstra-Algorithmus zu kompilieren. Es kann ein besserer Weg zu gehen, aber ein einfacher wäre, einfach rückwärts einen binären Baum zu arbeiten. Stellen Sie sich eine Liste der Knoten [beginnen, a, b, c, Ende]. Addieren Sie die einfachen Abstände [Start-> a-> b-> c-> Ende] Dies ist Ihre neue Zieldistanz zu schlagen. Versuchen Sie nun [Start-> a-> c-> b-> Ende] und wenn das besser eingestellt, dass als Ziel (und denken Sie daran, dass es von diesem Muster des Knoten kam). Arbeiten nach hinten über die Permutationen:

  • [Start-> a-> b-> c-> end]
  • [Start-> a-> c-> b-> end]
  • [Start-> b-> a-> c-> end]
  • [Start-> b-> c-> a-> end]
  • [Start-> c-> a-> b-> end]
  • [Start-> c-> b-> a-> end]

Einer von denen wird am kürzesten.

(wo die ‚besuchte mehrere Male‘ Knoten, wenn überhaupt? Sie sind einfach in der kürzesten Pfad Initialisierungsschritt versteckt. Der kürzeste Weg zwischen a und b c oder sogar den Endpunkt enthalten. Sie tun nicht brauchen Pflege)

In Anbetracht der Menge von Knoten und Kanten relativ begrenzt ist, können Sie wahrscheinlich jeden möglichen Weg berechnen und die kürzeste nehmen.

diese im Allgemeinen als das Reiseproblem bekannt und hat eine nicht-deterministisch Polynom Laufzeit, egal, was die Algorithmus Sie verwenden.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Wie wäre es brutaler Gewalt auf dem Dutzend mit ‚besuchen müssen‘ Knoten. Sie können ganz einfach genug, um alle möglichen Kombinationen von 12 Knoten abdecken, und dies läßt Dich mit einer optimalen Schaltung Sie folgen können, um sie zu decken.

Nun, Ihr Problem zu einem der Suche nach optimalen Routen vom Startknoten zu der Schaltung vereinfacht wird, die Sie dann um folgen, bis Sie sie behandelt haben, und dann die Strecke bis zum Ende aus, dass finden.

Schlusspfad besteht aus:

Start -> Pfad zur Schaltung * -> Schaltung von Knoten besuchen müssen -> Pfad zu beenden * -> Ende

Sie finden die Wege I mit * wie folgt gekennzeichnet

Sie ein A * Suche vom Startknoten zu jedem Punkt auf der Rennstrecke für jedes von dieser ein tun A * Suche von dem nächsten und vorherigen Knoten auf der Schaltung bis zum Ende (weil man der Schaltung rund in beiden Richtungen folgen kann) Was Sie am Ende mit ist eine Menge Suchpfade, und Sie können die mit den niedrigsten Kosten wählen.

Es gibt viel Platz für die Optimierung durch die Durchsuchungen Cachen, aber ich denke, das gute Lösungen generieren.

Es geht nicht irgendwo in der Nähe für eine optimale Lösung, aber, weil das bedeuten könnte den Most Besuch Schaltung innerhalb der Suche zu verlassen.

Eine Sache, die nicht überall erwähnt wird, ist, ob es in Ordnung ist für den gleichen Scheitelpunkt im Weg mehr als einmal besucht werden. Die meisten Antworten hier davon aus, dass es die gleiche Kante mehrmals zu besuchen, aber mein nehmen angesichts der Frage (ein Pfad sollte nicht besuchen die gleiche Vertex mehr als einmal!) Ist in Ordnung, dass es nicht ok den gleichen Scheitelpunkt besuchen zweimal.

So ein Brute-Force-Ansatz würde immer noch gelten, aber man müßte Ecken entfernen, bereits verwendet, wenn Sie jede Teilmenge des Pfades zu berechnen versuchen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top