Ich versuche, den besten zeiteffizienten Algorithmus zu ermitteln, um die unten beschriebene Aufgabe zu erfüllen.
Ich habe eine Reihe von Aufzeichnungen. Für diesen Datensatz habe ich Verbindungsdaten, die angeben, wie Paare von Datensätzen aus diesem Satz miteinander verbunden sind. Dies stellt im Wesentlichen einen ungerichteten Graphen dar, wobei die Datensätze die Eckpunkte und die Verbindungsdaten die Kanten sind.
Alle Datensätze im Satz enthalten Verbindungsinformationen (dh es sind keine verwaisten Datensätze vorhanden; jeder Datensatz im Satz stellt eine Verbindung zu einem oder mehreren anderen Datensätzen im Satz her).
Ich möchte zwei beliebige Datensätze aus dem Satz auswählen und alle einfachen Pfade zwischen den ausgewählten Datensätzen anzeigen können. Mit "einfachen Pfaden" meine ich die Pfade, die keine wiederholten Datensätze im Pfad haben (dh nur endliche Pfade).
Hinweis: Die beiden ausgewählten Datensätze sind immer unterschiedlich (dh Start- und Endscheitelpunkt sind niemals gleich; keine Zyklen).
Beispielsweise:
Wenn ich folgende Unterlagen habe: A, B, C, D, E. und das Folgende repräsentiert die Verbindungen: (A, B), (A, C), (B, A), (B, D), (B, E), (B, F), (C, A), (C, E), (C, F), (D, B), (E, C), (E, F), (F, B), (F, C), (F, E) [wobei (A, B) bedeutet, dass Datensatz A mit Datensatz B verbunden ist]
Wenn ich B als Startdatensatz und E als Enddatensatz wählen würde, würde ich alle einfachen Pfade durch die Datensatzverbindungen finden wollen, die Datensatz B mit Datensatz E verbinden würden.
Alle Pfade, die B mit E verbinden: B-> E. B-> F-> E. B-> F-> C-> E. B-> A-> C-> E. B-> A-> C-> F-> E.
Dies ist ein Beispiel, in der Praxis kann ich Sätze haben, die Hunderttausende von Datensätzen enthalten.
quelle
Antworten:
Es scheint, dass dies mit einer Tiefensuche des Graphen erreicht werden kann. Bei der Tiefensuche werden alle nicht zyklischen Pfade zwischen zwei Knoten gefunden. Dieser Algorithmus sollte sehr schnell sein und auf große Diagramme skaliert werden können (Die Diagrammdatenstruktur ist spärlich, sodass nur so viel Speicher benötigt wird, wie benötigt wird).
Mir ist aufgefallen, dass das oben angegebene Diagramm nur eine Kante hat, die gerichtet ist (B, E). War das ein Tippfehler oder ist es wirklich ein gerichteter Graph? Diese Lösung funktioniert unabhängig davon. Entschuldigung, ich konnte es in C nicht machen, ich bin ein bisschen schwach in diesem Bereich. Ich gehe jedoch davon aus, dass Sie diesen Java-Code ohne allzu große Probleme übersetzen können.
Graph.java:
Search.java:
Programmausgabe:
quelle
Das Online-Wörterbuch für Algorithmen und Datenstrukturen des Nationalen Instituts für Standards und Technologie (NIST) listet dieses Problem als " alle einfachen Pfade" auf und empfiehlt eine Tiefensuche . CLRS liefert die relevanten Algorithmen.
Eine clevere Technik mit Petri-Netzen finden Sie hier
quelle
Hier ist der Pseudocode, den ich mir ausgedacht habe. Dies ist kein bestimmter Pseudocode-Dialekt, sollte aber einfach genug sein, um zu folgen.
Jeder möchte das auseinander nehmen.
[p] ist eine Liste von Eckpunkten, die den aktuellen Pfad darstellen.
[x] ist eine Liste von Pfaden, bei denen die Kriterien erfüllt sind
[s] ist der Quellscheitelpunkt
[d] ist der Zielscheitelpunkt
[c] ist der aktuelle Scheitelpunkt (Argument für die PathFind-Routine)
Angenommen, es gibt eine effiziente Möglichkeit, die benachbarten Scheitelpunkte nachzuschlagen (Zeile 6).
quelle
Da die in dieser Antwort angegebene nicht rekursive DFS-Implementierung fehlerhaft zu sein scheint, möchte ich eine bereitstellen, die tatsächlich funktioniert.
Ich habe dies in Python geschrieben, weil ich es durch Implementierungsdetails ziemlich lesbar und übersichtlich finde (und weil es das praktische
yield
Schlüsselwort zum Implementieren von Generatoren enthält ), aber es sollte ziemlich einfach sein, es in andere Sprachen zu portieren.Dieser Code verwaltet zwei parallele Stapel: einen mit den früheren Knoten im aktuellen Pfad und einen mit dem aktuellen Nachbarindex für jeden Knoten im Knotenstapel (sodass wir die Iteration durch die Nachbarn eines Knotens fortsetzen können, wenn wir ihn wieder entfernen der Stapel). Ich hätte genauso gut einen einzelnen Stapel von (Knoten-, Index-) Paaren verwenden können, aber ich dachte, die Zwei-Stapel-Methode wäre besser lesbar und für Benutzer anderer Sprachen möglicherweise einfacher zu implementieren.
Dieser Code verwendet auch einen separaten
visited
Satz, der immer den aktuellen Knoten und alle Knoten auf dem Stapel enthält, damit ich effizient prüfen kann, ob ein Knoten bereits Teil des aktuellen Pfads ist. Wenn Ihre Sprache zufällig über eine Datenstruktur "geordneter Satz" verfügt, die sowohl effiziente stapelähnliche Push / Pop-Operationen als auch effiziente Mitgliedschaftsabfragen bietet, können Sie diese für den Knotenstapel verwenden und den separatenvisited
Satz entfernen.Wenn Sie alternativ eine benutzerdefinierte veränderbare Klasse / Struktur für Ihre Knoten verwenden, können Sie einfach ein boolesches Flag in jedem Knoten speichern, um anzugeben, ob es als Teil des aktuellen Suchpfads besucht wurde. Natürlich können Sie mit dieser Methode nicht zwei Suchvorgänge im selben Diagramm gleichzeitig ausführen, falls Sie dies aus irgendeinem Grund wünschen.
Hier ist ein Testcode, der zeigt, wie die oben angegebene Funktion funktioniert:
Wenn Sie diesen Code in dem angegebenen Beispieldiagramm ausführen, wird die folgende Ausgabe ausgegeben:
Beachten Sie, dass dieses Beispieldiagramm zwar ungerichtet ist (dh alle Kanten in beide Richtungen verlaufen), der Algorithmus jedoch auch für beliebig gerichtete Diagramme funktioniert. Wenn Sie beispielsweise die
C -> B
Kante entfernen (indem Sie sieB
aus der Nachbarliste von entfernenC
), erhalten Sie dieselbe Ausgabe, mit Ausnahme des dritten Pfads (A -> C -> B -> D
), der nicht mehr möglich ist.Ps. Es ist einfach, Diagramme zu erstellen, für die einfache Suchalgorithmen wie dieser (und die anderen in diesem Thread) sehr schlecht funktionieren.
Betrachten Sie beispielsweise die Aufgabe, alle Pfade von A nach B in einem ungerichteten Diagramm zu finden, in dem der Startknoten A zwei Nachbarn hat: den Zielknoten B (der keine anderen Nachbarn als A hat) und einen Knoten C, der Teil einer Clique ist von n + 1 Knoten, wie folgt:
Es ist leicht zu erkennen, dass der einzige Pfad zwischen A und B der direkte ist, aber eine naive DFS, die von Knoten A aus gestartet wird, verschwendet O ( n !) Zeit, um Pfade innerhalb der Clique nutzlos zu erkunden, obwohl dies (für einen Menschen) offensichtlich ist Keiner dieser Pfade kann möglicherweise zu B führen.
Man kann auch DAGs mit ähnlichen Eigenschaften konstruieren , z. B. indem der Startknoten A den Zielknoten B und zwei andere Knoten C 1 und C 2 verbindet , die beide mit den Knoten D 1 und D 2 verbunden sind , die beide mit E verbunden sind 1 und E 2 und so weiter. Für n Schichten von Knoten, die so angeordnet sind, verschwendet eine naive Suche nach allen Pfaden von A nach B O (2 n ) Zeit, um alle möglichen Sackgassen zu untersuchen, bevor sie aufgegeben wird.
Das Hinzufügen einer Kante zum Zielknoten B von einem der Knoten in der Clique (außer C) oder von der letzten Schicht der DAG würde natürlich eine exponentiell große Anzahl möglicher Pfade von A nach B und a erzeugen Ein rein lokaler Suchalgorithmus kann nicht wirklich im Voraus sagen, ob er eine solche Kante findet oder nicht. In gewissem Sinne ist die schlechte Ausgabesensitivität solcher naiven Suchvorgänge darauf zurückzuführen, dass sie sich der globalen Struktur des Graphen nicht bewusst sind.
Zwar gibt es verschiedene Vorverarbeitungsmethoden (z. B. iteratives Entfernen von Blattknoten, Suchen nach Scheitelpunkttrennzeichen für einzelne Knoten usw.), mit denen einige dieser "Sackgassen in Exponentialzeit" vermieden werden können, aber ich kenne keine allgemeinen Vorverarbeitungstrick, der sie in allen Fällen beseitigen könnte . Eine allgemeine Lösung wäre, bei jedem Schritt der Suche zu überprüfen, ob der Zielknoten noch erreichbar ist (mithilfe einer Untersuche), und frühzeitig zurückzuverfolgen, wenn dies nicht der Fall ist - aber leider würde dies die Suche erheblich verlangsamen (im schlimmsten Fall) (proportional zur Größe des Diagramms) für viele Diagramme, die keine solchen pathologischen Sackgassen enthalten.
quelle
for path in find_simple_paths(graph, "A", "D"): print(" -> ".join(path))
, dasprint
fehlte die Klammer.Hier ist eine logisch besser aussehende rekursive Version im Vergleich zum zweiten Stock.
Programmausgabe
quelle
Lösung in C-Code. Es basiert auf DFS, das minimalen Speicher benötigt.
quelle
Dies mag spät sein, aber hier ist dieselbe C # -Version des DFS-Algorithmus in Java von Casey, um alle Pfade zwischen zwei Knoten mithilfe eines Stapels zu durchlaufen. Die Lesbarkeit ist mit rekursiv wie immer besser.
quelle
neighbours.Reverse()
? Ist esList<T>.Reverse
?Ich habe kürzlich ein ähnliches Problem gelöst, anstatt an allen Lösungen, die mich nur am kürzesten interessierten.
Ich habe eine iterative Suche mit der Breite zuerst verwendet, bei der eine Statuswarteschlange verwendet wurde, von der jede einen Datensatz enthielt, der einen aktuellen Punkt in der Grafik und den Weg dorthin enthielt.
Sie beginnen mit einem einzelnen Datensatz in der Warteschlange, der den Startknoten und einen leeren Pfad enthält.
Bei jeder Iteration durch den Code wird das Element vom Kopf der Liste gestrichen und überprüft, ob es sich um eine Lösung handelt (der Knoten ist der gewünschte, wenn dies der Fall ist, wir sind fertig). Andernfalls wird ein neuer erstellt Warteschlangenelement mit den Knoten, die mit dem aktuellen Knoten verbunden sind, und geänderten Pfaden, die auf dem Pfad des vorherigen Knotens basieren, wobei der neue Sprung am Ende angehängt wird.
Jetzt könnten Sie etwas Ähnliches verwenden, aber wenn Sie eine Lösung finden, anstatt anzuhalten, fügen Sie diese Lösung Ihrer "gefundenen Liste" hinzu und fahren Sie fort.
Sie müssen die Liste der besuchten Knoten verfolgen, damit Sie sich nie selbst zurückverfolgen, da Sie sonst eine Endlosschleife haben.
Wenn du ein bisschen mehr Pseudocode willst, poste einen Kommentar oder so, und ich werde es näher erläutern.
quelle
Ich denke, Sie sollten Ihr eigentliches Problem dahinter beschreiben. Ich sage das, weil Sie nach etwas zeiteffizientem fragen, aber die Antwort auf das Problem scheint exponentiell zu wachsen!
Daher würde ich keinen besseren Algorithmus erwarten als etwas Exponentiales.
Ich würde das ganze Diagramm zurückverfolgen und durchgehen. Speichern Sie alle besuchten Knoten auf dem Weg, um Zyklen zu vermeiden. Wenn Sie zurückkehren, heben Sie die Markierung des Knotens auf.
Rekursion verwenden:
Oder ist das falsch?
edit: Oh, und ich habe vergessen: Sie sollten die rekursiven Aufrufe eliminieren, indem Sie diesen Knotenstapel verwenden
quelle
Das Grundprinzip ist, dass Sie sich keine Gedanken über Diagramme machen müssen. Dies ist ein Standardproblem, das als Problem der dynamischen Konnektivität bezeichnet wird. Es gibt folgende Arten von Methoden, mit denen Sie erreichen können, dass Knoten verbunden sind oder nicht:
Hier ist der C-Code, den ich mit minimaler Zeitkomplexität ausprobiert habe. O (log * n) Das bedeutet, dass für die 65536-Kantenliste 4 Suchvorgänge und für 2 ^ 65536 5 Suchvorgänge erforderlich sind. Ich teile meine Implementierung mit dem Algorithmus: Algorithm Course der Princeton University
TIPP: Sie finden die Java-Lösung unter dem oben angegebenen Link mit den entsprechenden Erklärungen.
quelle
find_paths [s, t, d, k]
Diese Frage ist alt und bereits beantwortet. Keiner zeigt jedoch vielleicht einen flexibleren Algorithmus, um dasselbe zu erreichen. Also werfe ich meinen Hut in den Ring.
Ich persönlich finde einen Algorithmus der Form
find_paths[s, t, d, k]
nützlich, wobei:Verwenden Sie die Unendlichkeitsform Ihrer Programmiersprache für
d
undk
geben Sie alle Pfade§.Offensichtlich § wenn Sie einen gerichteten Graphen verwenden und Sie alle ungerichtete Pfade zwischen
s
undt
Sie werden diese in beide Richtungen laufen müssen:Hilfsfunktion
Ich persönlich mag Rekursion, obwohl es manchmal schwierig sein kann, lassen Sie uns trotzdem zuerst unsere Hilfsfunktion definieren:
Hauptfunktion
Damit ist die Kernfunktion trivial:
Lassen Sie uns zunächst einige Dinge beachten:
[]
Ist eine nicht initialisierte Liste, ersetzen Sie diese durch die Entsprechung für die Programmiersprache Ihrer Wahlpaths_found
wird als Referenz übergeben . Es ist klar, dass die Rekursionsfunktion nichts zurückgibt. Behandeln Sie dies angemessen.graph
wird irgendeine Form vonhashed
Struktur angenommen. Es gibt eine Vielzahl von Möglichkeiten, ein Diagramm zu implementieren. In beidengraph[vertex]
Fällen erhalten Sie eine Liste benachbarter Scheitelpunkte in einem gerichteten Diagramm - passen Sie sie entsprechend an.quelle
Hier ist ein Gedanke aus meinem Kopf:
quelle
Soweit ich das beurteilen kann, sind die von Ryan Fox ( 58343 , Christian ( 58444 ) und Ihnen ( 58461 ) ) gegebenen Lösungen so gut wie es nur geht. Ich glaube nicht, dass die Durchquerung der Breite in diesem Fall hilft, wie Sie wollen erhalten nicht alle Pfade , z. B. mit Kanten
(A,B)
,(A,C)
,(B,C)
,(B,D)
und(C,D)
Sie bekommen PfadeABD
undACD
, aber nichtABCD
.quelle
Ich habe einen Weg gefunden, alle Pfade aufzulisten, einschließlich der unendlichen, die Schleifen enthalten.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Atompfade und -zyklen finden
Wir möchten alle möglichen Pfade finden, die von Punkt A nach Punkt B führen. Da es sich um Zyklen handelt, können Sie nicht alle durchlaufen und aufzählen. Stattdessen müssen Sie einen atomaren Pfad finden, der keine Schleife aufweist, und die kleinstmöglichen Zyklen (Sie möchten nicht, dass sich Ihr Zyklus wiederholt).
Die erste Definition, die ich für einen Atompfad vorgenommen habe, ist ein Pfad, der nicht zweimal denselben Knoten durchläuft. Ich fand jedoch heraus, dass nicht alle Möglichkeiten genutzt wurden. Nach einigem Nachdenken stellte ich fest, dass Knoten nicht wichtig sind, Kanten jedoch! Ein Atompfad ist also ein Pfad, der nicht zweimal durch dieselbe Kante verläuft.
Diese Definition ist praktisch und funktioniert auch für Zyklen: Ein Atomzyklus von Punkt A ist ein Atompfad, der von Punkt A zu Punkt A führt.
Implementierung
Um den gesamten Pfad von Punkt A aus zu erhalten, werden wir den Graphen rekursiv von Punkt A aus durchlaufen. Während wir durch ein Kind gehen, werden wir ein Link-Kind -> Elternteil erstellen, um alle Kanten zu kennen, die wir haben habe schon gekreuzt. Bevor wir zu diesem Kind gehen, müssen wir diese verknüpfte Liste durchlaufen und sicherstellen, dass die angegebene Kante noch nicht durchlaufen wurde.
Wenn wir am Zielpunkt ankommen, können wir den gefundenen Pfad speichern.
Ein Problem tritt auf, wenn Sie die verknüpfte Liste freigeben möchten. Es ist im Grunde ein Baum, der in umgekehrter Reihenfolge angekettet ist. Eine Lösung wäre, diese Liste doppelt zu verknüpfen und den Baum vom Startpunkt zu befreien, wenn alle Atompfade gefunden wurden.
Eine clevere Lösung ist jedoch die Verwendung einer Referenzzählung (inspiriert von der Garbage Collection). Jedes Mal, wenn Sie einem übergeordneten Element einen Link hinzufügen, fügen Sie dem Referenzzähler einen hinzu. Wenn Sie dann am Ende eines Pfades ankommen, gehen Sie rückwärts und frei, während der Referenzzähler gleich 1 ist. Wenn er höher ist, entfernen Sie einfach einen und halten an.
Das Suchen nach dem Atomzyklus von A ist dasselbe wie das Suchen nach dem Atompfad von A nach A. Es gibt jedoch mehrere Optimierungen, die wir vornehmen können. Erstens, wenn wir am Zielpunkt ankommen, wollen wir den Pfad nur speichern, wenn die Summe der Kantenkosten negativ ist: Wir wollen nur Absorptionszyklen durchlaufen.
Wie Sie zuvor gesehen haben, wird der gesamte Graph bei der Suche nach einem Atompfad durchlaufen. Stattdessen können wir den Suchbereich auf die stark verbundene Komponente beschränken, die A enthält. Um diese Komponenten zu finden, müssen Sie den Graphen mit dem Tarjan-Algorithmus einfach durchlaufen.
Atompfade und Zyklen kombinieren
Zu diesem Zeitpunkt haben wir alle Atompfade von A nach B und alle Atomzyklen jedes Knotens, die uns überlassen bleiben, um alles zu organisieren, um den kürzesten Pfad zu erhalten. Von nun an werden wir untersuchen, wie man die beste Kombination von Atomzyklen auf einem Atompfad findet.
quelle
Wie von einigen anderen Postern geschickt beschrieben, besteht das Problem auf den Punkt gebracht darin, einen Tiefensuchalgorithmus zu verwenden, um den Graphen rekursiv nach allen Kombinationen von Pfaden zwischen den kommunizierenden Endknoten zu durchsuchen.
Der Algorithmus selbst beginnt mit dem Startknoten, den Sie ihm geben, untersucht alle ausgehenden Links und erweitert den ersten untergeordneten Knoten des angezeigten Suchbaums, wobei er immer tiefer sucht, bis ein Zielknoten gefunden wird oder bis er auf einen Knoten trifft das hat keine Kinder.
Die Suche wird dann zurückverfolgt und kehrt zum letzten Knoten zurück, den die Erkundung noch nicht abgeschlossen hat.
Ich gebloggt über dieses Thema sehr vor kurzem ein Beispiel C ++ Implementierung in dem Prozess der Veröffentlichung.
quelle
Neben der Antwort von Casey Watson finden Sie hier eine weitere Java-Implementierung. Initialisierung des besuchten Knotens mit dem Startknoten.
quelle