Finden Sie alle möglichen Pfade von einem Scheitelpunkt in einem gerichteten zyklischen Graphen in Erlang

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

Frage

Ich möchte eine Funktion implementieren, die alle möglichen Pfade zu allen möglichen Scheitelpunkten von einem Quellscheitelpunkt V in einem gerichteten zyklischen Graphen G findet. Toulouse Die Leistung spielt jetzt keine Rolle, ich möchte nur den Algorithmus verstehen. Ich habe die Definition des Tiefensuchalgorithmus gelesen, habe aber kein volles Verständnis dessen, was zu tun ist.

hier Ich habe hier keinen kompletten Code zur Verfügung zu stellen, da ich nicht sicher bin, wie:

  • Speichern Sie die Ergebnisse (zusammen mit A-> B-> C-> sollten wir auch A-> B und A-> B-> C speichern);
  • stellen den Graphen dar (Digraph? Liste der Tupel?);
  • Wie viele Rekursionen müssen verwendet werden (mit jedem benachbarten Scheitelpunkt arbeiten?).
< Wie finde ich alle möglichen Pfade von einem bestimmten Quellscheitelpunkt in einem gerichteten zyklischen Graphen in Erlang? Beito: Basierend auf den bisherigen Antworten muss ich die Graphdefinition neu definieren: Es ist ein nicht-azyklischer Graph. Ich weiß, dass meine rekursive Funktion eine unbestimmte Schleife ist, wenn sie auf einen Zyklus trifft. Um dies zu vermeiden, kann ich einfach überprüfen, ob sich ein aktueller Scheitelpunkt in der Liste des resultierenden Pfads befindet. Wenn ja, höre ich auf zu durchlaufen und gebe den Pfad zurück.
< UPD2: Vielen Dank für zum Nachdenken anregende Kommentare! Ja, ich muss alle einfachen Pfade finden, die keine Schleifen von einem Quellscheitelpunkt zu allen anderen haben.

In einem Diagramm wie diesem: Toul Nicht-azyklischer Graph

Mit dem Quellscheitelpunkt A sollte der Algorithmus die folgenden Pfade finden:

  • A, B
  • A, B, C A, B, C, D
  • A, D
  • A, D, C
  • A, D, C, B

    Der folgende Code erledigt den Job, ist jedoch mit Diagrammen mit mehr als 20 Eckpunkten unbrauchbar (ich denke, mit der Rekursion stimmt etwas nicht - benötigt zu viel Speicher, endet nie): 

    dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.

    <> UPD3:

    Das Problem ist, dass der reguläre Tiefensuchalgorithmus zuerst einen der zu-Pfade geht: (A, B, C, D) oder (A, D, C, B) und niemals den zweiten Pfad geht.

    In beiden Fällen ist dies der einzige Pfad. Wenn beispielsweise die reguläre DFS von (A, B, C, D) zurückverfolgt wird, geht sie zurück zu A und prüft, ob D (der zweite Nachbar von A) besucht wird . Und da die reguläre DFS für jeden Scheitelpunkt einen globalen Status beibehält, hätte D den Status "besucht". Wir müssen also einen rekursionsabhängigen Zustand einführen. Wenn wir von (A, B, C, D) nach A zurückkehren, sollten wir (A, B, C, D) in der Liste der Ergebnisse haben und wir sollten D als nicht besucht markieren, ganz am Anfang des Algorithmus.

    Ich habe versucht, die Lösung auf eine schwanzrekursive Lösung zu optimieren, aber die Laufzeit des Algorithmus ist immer noch nicht realisierbar. Es dauert ungefähr 4 Sekunden, um einen winzigen Graphen mit 16 Scheitelpunkten mit 3 Kanten pro Scheitelpunkt zu durchlaufen: 

    dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).

    Irgendwelche Ideen, um dies in akzeptabler Zeit auszuführen?

War es hilfreich?

Lösung

Bearbeiten: Okay, ich verstehe jetzt, Sie möchten alle einfachen Pfade von einem Scheitelpunkt in einem gerichteten Diagramm finden. Eine Tiefensuche mit Backtracking wäre also geeignet, wie Sie erkannt haben. Die allgemeine Idee ist, zu einem Nachbarn zu gehen, dann zu einem anderen (nicht zu einem, den Sie besucht haben) und weiterzumachen, bis Sie in eine Sackgasse geraten. Gehen Sie dann zurück zum letzten Scheitelpunkt, an dem Sie sich befanden, und wählen Sie einen anderen Nachbarn usw. aus. Sie müssen die fummeligen Teile richtig machen, aber es sollte nicht zu schwer sein. Z.B. Bei jedem Schritt müssen Sie die Scheitelpunkte als "erforscht" oder "unerforscht" kennzeichnen, je nachdem, ob Sie sie bereits zuvor besucht haben. Die Leistung sollte kein Problem sein, ein ordnungsgemäß implementierter Algorithmus sollte möglicherweise O (n ^ 2) Zeit in Anspruch nehmen. Ich weiß also nicht, was Sie falsch machen, vielleicht besuchen Sie zu viele Nachbarn? Z.B. Vielleicht besuchen Sie die Nachbarn, die Sie bereits besucht haben, erneut und gehen in Schleifen herum oder so.

Ich habe Ihr Programm nicht wirklich gelesen, aber die Wiki-Seite zur Tiefensuche enthält ein kurzes, einfaches Pseudocode-Programm, das Sie in Ihrer Sprache kopieren können. Speichern Sie die Diagramme als Adjazenzlisten, um dies zu vereinfachen.

Bearbeiten: Ja, tut mir leid, Sie haben Recht. Die Standard-DFS-Suche funktioniert derzeit nicht. Sie müssen sie leicht anpassen, damit die zuvor besuchten Scheitelpunkte erneut angezeigt werden. Sie dürfen also alle Scheitelpunkte besuchen, außer denen, die Sie bereits in Ihrem aktuellen Pfad gespeichert haben. Dies bedeutet natürlich, dass meine Laufzeit völlig falsch war, die Komplexität Ihres Algorithmus wird durch das Dach gehen. Wenn die durchschnittliche Komplexität Ihres Graphen d + 1 ist, gibt es ungefähr d * d * d * ... * d= d ^ n mögliche Pfade. Selbst wenn jeder Scheitelpunkt nur 3 Nachbarn hat, gibt es immer noch einige Pfade, wenn Sie über 20 Scheitelpunkte kommen. Daran führt kein Weg vorbei, denn wenn Sie möchten, dass Ihr Programm alle möglichen Pfade ausgibt, müssen Sie tatsächlich alle d ^ n von ihnen ausgeben.

Ich bin interessiert zu wissen, ob Sie dies für eine bestimmte Aufgabe benötigen oder nur versuchen, dies aus Interesse zu programmieren. In letzterem Fall müssen Sie nur mit kleinen, spärlich verbundenen Grafiken zufrieden sein.

Andere Tipps

Ich verstehe die Frage nicht. Wenn ich den Graphen G= (V, E)= ({A, B}, {(A, B), (B, A)}) habe, gibt es unendlich viele Wege von A nach B {[A, B], [ A, B, A, B], [A, B, A, B, A, B], ...}. Wie kann ich alle möglichen Pfade zu einem beliebigen Scheitelpunkt im zyklischen Diagramm finden?

Bearbeiten:

Haben Sie sogar versucht, mögliche Pfade für einige Diagramme zu berechnen oder zu erraten? Wenn Sie das Diagramm vollständig verbunden haben, erhalten Sie

  • 2 - 1
  • 3 - 4
  • 4 - 15
  • 5 - 64
  • 6 - 325
  • 7 - 1956
  • 8 - 13699
  • 9 - 109600
  • 10 - 986409
  • 11 - 9864100
  • 12 - 108505111
  • 13 - 1302061344
  • 14 - 16926797485
  • 15 - 236975164804
  • 16 - 3554627472075
  • 17 - 56874039553216
  • 18 - 966858672404689
  • 19 - 17403456103284420
  • 20 - 330665665962403999

    Sind Sie sicher, dass Sie alle Pfade für alle Knoten finden möchten? Wenn Sie in einer Sekunde einen Millionenpfad berechnen, dauert es 10750 Jahre, bis alle Pfade zu allen Knoten in einem vollständig verbundenen Diagramm mit 20 Knoten berechnet sind. Es ist die Obergrenze für Ihre Aufgabe, also denke ich, dass Sie es nicht gerne tun würden. Ich denke, Sie wollen etwas anderes.

Keine verbesserte algorithmische Lösung, aber Sie können die Leistung häufig verbessern, indem Sie mehrere Arbeitsthreads erzeugen, möglicherweise einen für jeden Knoten der ersten Ebene, und dann die Ergebnisse aggregieren.Dies kann naive Brute-Force-Algorithmen oft relativ leicht verbessern.

Hier sehen Sie ein Beispiel: Einige Erlang-Matrixfunktionen in der Funktion maximise_assignment (Kommentare ab Zeile 191 ab heute).Auch hier ist der zugrunde liegende Algorithmus ziemlich naiv und brutal, aber die Parallelisierung beschleunigt ihn für viele Arten von Matrizen recht gut.

Ich habe in der Vergangenheit einen ähnlichen Ansatz verwendet, um die Anzahl der Hamilton-Pfade in einem Diagramm zu ermitteln.

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