webentwicklung-frage-antwort-db.com.de

Finden Sie den kürzesten Pfad in einer Grafik, die bestimmte Knoten besucht

Ich habe einen ungerichteten Graphen mit ungefähr 100 Knoten und ungefähr 200 Kanten. Ein Knoten trägt die Bezeichnung "Start", einer die Bezeichnung "Ende" und ein Dutzend die Bezeichnung "Mustpass".

Ich muss den kürzesten Weg durch diesen Graphen finden, der bei 'Start' beginnt, bei 'Ende' endet und alle 'Mustpass'-Knoten durchläuft (in beliebiger Reihenfolge).

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

72
dmd

Alle anderen, die dies mit dem Problem des Handlungsreisenden vergleichen, haben Ihre Frage wahrscheinlich nicht sorgfältig gelesen. In TSP besteht das Ziel darin, den kürzesten Zyklus zu finden, der all die Eckpunkte besucht (ein Hamilton-Zyklus) - dies entspricht einem Knoten mit der Bezeichnung every mustpass '.

In Ihrem Fall, vorausgesetzt, Sie haben nur etwa ein Dutzend als "Mustpass" gekennzeichnet, und vorausgesetzt, dass 12! ist eher klein (479001600), können Sie einfach alle Permutationen nur der 'Mustpass'-Knoten ausprobieren und den kürzesten Pfad von' Start 'bis' Ende 'suchen, der die' Mustpass'-Knoten in dieser Reihenfolge aufruft ist die Verkettung der kürzesten Pfade zwischen jeweils zwei aufeinander folgenden Knoten in dieser Liste.

Mit anderen Worten, finden Sie zuerst den kürzesten Abstand zwischen jedem Knotenpaar (Sie können den Dijkstra-Algorithmus oder andere verwenden, aber mit diesen kleinen Zahlen (100 Knoten) auch den am einfachsten zu codierenden Floyd-Warshall-Algorithmus = wird rechtzeitig ausgeführt). Versuchen Sie dann, sobald Sie dies in einer Tabelle haben, alle Permutationen Ihrer 'Mustpass'-Knoten und den Rest.

Etwas wie das:

//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 kein echter Code, und wenn Sie den tatsächlichen Pfad wollen, müssen Sie verfolgen, welche Permutation die kürzeste Entfernung ergibt und welche die kürzesten Pfade für alle Paare sind, aber Sie haben die Idee.)

Es wird in höchstens ein paar Sekunden in jeder vernünftigen Sprache laufen :)
[Wenn Sie n Knoten und k 'Mustpass'-Knoten haben, ist die Laufzeit O (n3) für den Floyd-Warshall-Teil und O (k! n) für den All-Permutations-Teil und 100 ^ 3 + (12!) (100) sind praktisch Erdnüsse, es sei denn, Sie haben einige wirklich einschränkende Einschränkungen.]

72
ShreevatsaR

run Djikstra's Algorithm um die kürzesten Wege zwischen allen kritischen Knoten zu finden (Start, Ende und Must-Pass), dann sollte eine Tiefendurchquerung den kürzesten Weg durch den resultierenden Subgraphen anzeigen, der sich berührt Alle Knoten beginnen ... müssen ... enden

23
Steven A. Lowe

Das Problem, das Sie gemeldet haben, ähnelt dem des Handlungsreisenden, aber ich denke näher an ein einfaches Problem bei der Wegfindung. Anstatt jeden Knoten einzeln aufzusuchen, müssen Sie nur einen bestimmten Knotensatz in kürzester Zeit (Entfernung) aufsuchen.

Der Grund dafür ist, dass Sie mit einem Maislabyrinth im Gegensatz zum Problem des Handlungsreisenden nicht direkt von einem Punkt zu einem anderen Punkt auf der Karte gelangen können, ohne andere Knoten passieren zu müssen, um dorthin zu gelangen.

Ich würde A * -Pfadfinding als zu berücksichtigende Technik empfehlen. Sie richten dies ein, indem Sie entscheiden, welche Knoten direkt auf welche anderen Knoten zugreifen können und wie hoch die "Kosten" für jeden Hop von einem bestimmten Knoten sind. In diesem Fall könnte jeder "Sprung" gleich teuer sein, da Ihre Knoten relativ eng beieinander liegen. Ein * kann diese Informationen verwenden, um den Pfad mit den niedrigsten Kosten zwischen zwei beliebigen Punkten zu finden. Da Sie von Punkt A nach Punkt B gelangen und ungefähr 12 dazwischen besuchen müssen, würde selbst ein Brute-Force-Ansatz mit Pfadfindung nicht schaden.

Nur eine Alternative zu prüfen. Es sieht aus bemerkenswert wie das Problem der reisenden Verkäufer, und das sind gute Zeitungen, über die man nachlesen kann, aber wenn man genauer hinschaut, wird man feststellen, dass es nur zu kompliziert ist. ^ _ ^ Das kommt aus dem Kopf eines Videospiel-Programmierers, der sich schon früher mit solchen Dingen beschäftigt hat.

14
Nicholas Flynt

Dies sind zwei Probleme ... Steven Lowe hat darauf hingewiesen, aber der zweiten Hälfte des Problems nicht genug Respekt geschenkt.

Sie sollten zuerst die kürzesten Wege zwischen all Ihren kritischen Knoten ermitteln (Start, Ende, Mustpass). Sobald diese Pfade erkannt wurden, können Sie ein vereinfachtes Diagramm erstellen, bei dem jede Kante im neuen Diagramm ein Pfad von einem kritischen Knoten zum anderen im ursprünglichen Diagramm ist. Es gibt viele Pfadfindungsalgorithmen, mit denen Sie hier den kürzesten Pfad finden können.

Sobald Sie dieses neue Diagramm haben, haben Sie jedoch genau das Problem mit dem reisenden Verkäufer (na ja, fast ... Sie müssen nicht mehr zu Ihrem Ausgangspunkt zurückkehren). Alle Beiträge zu diesem Thema, die oben erwähnt wurden, sind gültig.

14
Andrew Top

Andrew Top hat die richtige Idee:

1) Djikstras Algorithmus 2) Einige TSP-Heuristiken.

Ich empfehle die Lin-Kernighan-Heuristik: Sie ist eine der bekanntesten für alle NP Vollständigen Probleme. Das einzige andere, an das Sie sich erinnern müssen, ist, dass Sie möglicherweise nach Schritt 2 den Graphen wieder erweitert haben Wenn Ihr erweiterter Pfad Schleifen enthält, sollten Sie diese kurzschließen (sehen Sie sich den Grad der Scheitelpunkte entlang Ihres Pfades an).

Ich bin mir eigentlich nicht sicher, wie gut diese Lösung im Verhältnis zum Optimum sein wird. Es gibt wahrscheinlich einige pathologische Fälle, die mit einem Kurzschluss zu tun haben. Immerhin sieht dieses Problem VIEL wie Steiner Tree aus: http://en.wikipedia.org/wiki/Steiner_tree und Sie können Steiner Tree definitiv nicht annähern, indem Sie einfach Ihren Graphen verkleinern und Kruskals für ausführen Beispiel.

5
Ying Xiao

Dies ist nicht ein TSP-Problem und nicht NP-schwer, da die ursprüngliche Frage nicht erfordert, dass Knoten, die unbedingt passieren müssen, nur einmal besucht werden. Dies macht die Antwort sehr viel einfacher, nachdem eine Liste der kürzesten Pfade zwischen allen Must-Pass-Knoten mithilfe des Dijkstra-Algorithmus erstellt wurde. Es gibt vielleicht einen besseren Weg, aber ein einfacher wäre, einfach einen Binärbaum rückwärts zu bearbeiten. Stellen Sie sich eine Liste von Knoten vor [Anfang, a, b, c, Ende]. Summiere die einfachen Distanzen [start-> a-> b-> c-> end], dies ist deine neue Zieldistanz, die du schlagen musst. Versuchen Sie nun [start-> a-> c-> b-> end] und legen Sie dies besser als Ziel fest (und denken Sie daran, dass es von diesem Knotenmuster stammt). Arbeiten Sie die Permutationen rückwärts ab:

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

Eine davon ist die kürzeste.

(Wo sind die 'mehrfach besuchten' Knoten, falls vorhanden? Sie werden nur im Initialisierungsschritt für den kürzesten Pfad ausgeblendet. Der kürzeste Pfad zwischen a und b kann c oder sogar den Endpunkt enthalten. Sie brauchen sich nicht darum zu kümmern )

4
bjorke

Da die Anzahl der Knoten und Kanten relativ begrenzt ist, können Sie wahrscheinlich jeden möglichen Pfad berechnen und den kürzesten nehmen.

Im Allgemeinen ist dies als Problem des Handlungsreisenden bekannt und hat eine nicht deterministische polynomielle Laufzeit, unabhängig davon, welchen Algorithmus Sie verwenden.

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

3
Rafe

Es wäre nett gewesen, uns zu sagen, ob der Algorithmus in einer Sekunde, einem Tag, einer Woche oder so ablaufen sollte . Aber wenn es in eine Benutzeroberfläche eingebettet ist und viele Male am Tag berechnet werden muss ... ein weiteres Problem, denke ich.

2
Szundi

Eine Sache, die nirgendwo erwähnt wird, ist, ob es in Ordnung ist, dass derselbe Scheitelpunkt mehr als einmal im Pfad besucht wird. Die meisten Antworten hier gehen davon aus, dass es in Ordnung ist, denselben Edge mehrmals zu besuchen, aber meine Antwort auf die Frage (ein Pfad sollte denselben Scheitelpunkt nicht mehr als einmal besuchen!) Lautet: nicht ok denselben Scheitelpunkt zweimal zu besuchen.

Ein Brute-Force-Ansatz würde also weiterhin angewendet, aber Sie müssten bereits verwendete Scheitelpunkte entfernen, wenn Sie versuchen, jede Teilmenge des Pfads zu berechnen.

0
kirsch

Wie wäre es mit brachialer Gewalt auf dem Dutzend Knoten, die besucht werden müssen? Sie können alle möglichen Kombinationen von 12 Knoten leicht genug abdecken und haben so eine optimale Schaltung, der Sie folgen können, um sie abzudecken.

Jetzt ist Ihr Problem dahingehend vereinfacht, dass Sie optimale Routen vom Startknoten bis zur Rennstrecke finden, denen Sie dann folgen, bis Sie sie überdeckt haben, und dann die Route von dort bis zum Ende finden.

Der endgültige Pfad besteht aus:

start -> weg zum kreislauf * -> kreislauf muss knoten besuchen -> weg zum ende * -> ende

Sie finden die mit * gekennzeichneten Pfade wie folgt

Führen Sie eine A * -Suche vom Startknoten bis zu jedem Punkt auf der Strecke durch. Führen Sie jeweils eine A * -Suche vom nächsten und vorherigen Knoten auf der Strecke bis zum Ende durch (da Sie der Runde der Strecke in beide Richtungen folgen können) Am Ende gibt es viele Suchpfade, und Sie können den mit den niedrigsten Kosten auswählen.

Durch das Zwischenspeichern der Suchanfragen gibt es viel Raum für Optimierungen, aber ich denke, dies wird zu guten Lösungen führen.

Es geht jedoch nicht um die Suche nach einer optimalen Lösung, da dies dazu führen könnte, dass der Kreislauf, der unbedingt besucht werden muss, während der Suche verlassen wird.

0
justinhj