Suchen Sie den kürzesten Pfad in einem Diagramm, das bestimmte Knoten besucht

Ich habe ein ungerichtetes Diagramm mit ungefähr 100 Knoten und ungefähr 200 Kanten. Ein Knoten ist mit "Start" gekennzeichnet, einer mit "Ende" und es gibt ungefähr ein Dutzend mit "Mustpass".

Ich muss den kürzesten Weg durch dieses Diagramm finden, der bei 'start' beginnt, bei 'end' endet und durch alle 'mustpass'-Knoten verläuft (in beliebiger Reihenfolge).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt ist das fragliche Diagramm - es repräsentiert ein Maislabyrinth in Lancaster, PA)

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 alle Eckpunkte besucht (ein Hamilton-Zyklus) - dies entspricht der Bezeichnung jedes Knotens mit der Bezeichnung "Mustpass".

In Ihrem Fall, vorausgesetzt, Sie haben nur etwa ein Dutzend mit "Mustpass" beschriftet und 12! ist ziemlich klein (479001600), Sie können einfach alle Permutationen nur der 'Mustpass'-Knoten ausprobieren und den kürzesten Pfad von' Start 'bis' Ende 'betrachten, der die' Mustpass'-Knoten in dieser Reihenfolge besucht - es wird einfach die Verkettung der kürzesten Pfade zwischen jeweils zwei aufeinander folgenden Knoten in dieser Liste sein.

Mit anderen Worten, finden Sie zuerst den kürzesten Abstand zwischen jedem Scheitelpunktpaar (Sie können den Dijkstra-Algorithmus oder andere verwenden, aber mit diesen kleinen Zahlen (100 Knoten) wird selbst der am einfachsten zu codierende Floyd-Warshall-Algorithmus rechtzeitig ausgeführt). Sobald Sie dies in einer Tabelle haben, versuchen Sie 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 möchten, müssen Sie verfolgen, welche Permutation die kürzeste Entfernung ergibt und welche kürzesten Pfade alle Paare sind, aber Sie haben die Idee.)

Es läuft in jeder vernünftigen Sprache in höchstens ein paar Sekunden :)
[Wenn Sie n Knoten und k 'Mustpass'-Knoten haben, beträgt seine Laufzeit O (n ³ ) für den Floyd-Warshall-Teil und O (k! N. ) für den Teil mit allen Permutationen und 100 ^ 3 + (12!) (100) sind praktisch Erdnüsse, es sei denn, Sie haben einige wirklich restriktive Einschränkungen.]

Führen Sie den Djikstra-Algorithmus aus , um die kürzesten Pfade zwischen allen kritischen Knoten (Start, Ende und Must-Pass) zu finden. Anschließend sollte eine Tiefenüberquerung den kürzesten Pfad durch den resultierenden Teilgraphen anzeigen , der alle Knotenstarts berührt. . muss passieren ... Ende

Dies sind zwei Probleme ... Steven Lowe wies darauf hin, schenkte der zweiten Hälfte des Problems jedoch nicht genügend Respekt.

Sie sollten zuerst die kürzesten Pfade 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 zu einem 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 genau das Problem mit dem reisenden Verkäufer (na ja, fast ... Sie müssen nicht mehr zu Ihrem Ausgangspunkt zurückkehren). Alle oben genannten Beiträge dazu gelten.

Eigentlich ähnelt das Problem, das Sie gepostet haben, dem des reisenden Verkäufers, aber ich denke eher an ein einfaches Wegfindungsproblem. Anstatt jeden einzelnen Knoten besuchen zu müssen, müssen Sie lediglich eine bestimmte Gruppe von Knoten in kürzester Zeit (Entfernung) besuchen.

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

Ich würde A * Pathfinding als eine 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" jedes Hops von einem bestimmten Knoten sind. In diesem Fall sieht es so aus, als ob jeder "Hop" die gleichen Kosten verursachen könnte, da Ihre Knoten relativ eng beieinander liegen. A * 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 überhaupt nicht schaden.

Nur eine Alternative zu prüfen. Es sieht bemerkenswert aus wie das Problem der reisenden Verkäufer, und das sind gute Papiere, über die man sich informieren kann, aber wenn man genauer hinschaut, wird man feststellen, dass es nur zu komplizierte Dinge sind. ^ _ ^ Dies kommt aus dem Kopf eines Videospielprogrammierers, der sich zuvor mit solchen Dingen befasst hat.

Andrew Top hat die richtige Idee:

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

Ich empfehle die Lin-Kernighan-Heuristik: Sie ist eine der bekanntesten für alle NP Complete-Probleme. Die einzige andere Sache, an die Sie sich erinnern sollten, ist, dass Sie nach dem erneuten Erweitern des Diagramms nach Schritt 2 möglicherweise Schleifen in Ihrem erweiterten Pfad haben. Daher 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 Kurzschluss zu tun haben. Immerhin sieht dieses Problem sehr nach Steiner Tree aus: http://en.wikipedia.org/wiki/Steiner_tree, und Sie können Steiner Tree definitiv nicht approximieren, indem Sie einfach Ihr Diagramm zusammenziehen und beispielsweise Kruskals ausführen.

Dies ist kein TSP-Problem und nicht NP-schwer, da die ursprüngliche Frage nicht erfordert, dass Must-Pass-Knoten nur einmal besucht werden. Dies macht die Antwort viel, viel einfacher, nur Brute-Force zu betreiben, nachdem eine Liste der kürzesten Pfade zwischen allen Must-Pass-Knoten über den Dijkstra-Algorithmus erstellt wurde. Es mag einen besseren Weg geben, aber ein einfacher wäre, einfach einen Binärbaum rückwärts zu arbeiten. Stellen Sie sich eine Liste von Knoten vor [Start, a, b, c, Ende]. Summiere die einfachen Entfernungen [Start-> a-> b-> c-> Ende]. Dies ist deine neue Zielentfernung, die du schlagen musst. Versuchen Sie nun [start-> a-> c-> b-> end] und wenn dies besser ist, legen Sie dies als Ziel fest (und denken Sie daran, dass es von diesem Knotenmuster stammt). Arbeiten Sie rückwärts ü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]

Eine davon wird am kürzesten sein.

(Wo sind die Knoten, die mehrfach besucht wurden, 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 müssen sich nicht darum kümmern )

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 Polynomlaufzeit, unabhängig davon, welchen Algorithmus Sie verwenden.

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

Die Frage spricht von Must-Pass in JEDER Reihenfolge . Ich habe versucht, nach einer Lösung für die definierte Reihenfolge der Must-Pass-Knoten zu suchen. Ich habe meine Antwort gefunden, aber da keine Frage zu StackOverflow eine ähnliche Frage hatte, poste ich hier, damit maximale Personen davon profitieren können.

Wenn die Reihenfolge oder der Must-Pass definiert ist, können Sie den Algorithmus von dijkstra mehrmals ausführen. Zum Beispiel lassen Sie uns annehmen , dass Sie aus beginnen müssen sdurchlaufen k1, k2und k3(in jeweiligen Reihenfolge) und Halt an e. Dann können Sie den Algorithmus von dijkstra zwischen jedem aufeinanderfolgenden Knotenpaar ausführen. Die Kosten und der Weg würden gegeben sein durch:

dijkstras(s, k1) + dijkstras(k1, k2) + dijkstras(k2, k3) + dijkstras(k3, 3)

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

Jetzt wird Ihr Problem vereinfacht, indem Sie optimale Routen vom Startknoten zur Rennstrecke finden, denen Sie dann folgen, bis Sie sie zurückgelegt haben, und dann die Route von dieser bis zum Ende finden.

Der letzte Pfad besteht aus:

Start -> Pfad zum Stromkreis * -> Stromkreis muss Knoten besuchen -> Pfad zum Ende * -> Ende

Sie finden die Pfade, die ich mit * markiert habe, so

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

Es gibt viel Raum für Optimierungen durch Zwischenspeichern der Suchvorgänge, aber ich denke, dies wird gute Lösungen generieren.

Es ist jedoch nicht annähernd die Suche nach einer optimalen Lösung, da dies dazu führen kann, dass der zu besuchende Schaltkreis innerhalb der Suche verlassen wird.

Eine Sache, die nirgendwo erwähnt wird, ist, ob es in Ordnung ist, denselben Scheitelpunkt mehr als einmal auf dem Pfad zu besuchen. Die meisten Antworten hier gehen davon aus, dass es in Ordnung ist, dieselbe Kante mehrmals zu besuchen, aber meine Meinung bei der Frage (ein Pfad sollte denselben Scheitelpunkt nicht mehr als einmal besuchen!) Ist, dass es nicht in Ordnung ist, 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.