Suchen Sie alle Pfade zwischen zwei Diagrammknoten

72

Ich arbeite an einer Implementierung des Dijkstras-Algorithmus, um den kürzesten Weg zwischen miteinander verbundenen Knoten in einem Streckennetz abzurufen. Ich habe die Implentation funktioniert. Es gibt alle kürzesten Pfade zu allen Knoten zurück, wenn ich den Startknoten an den Algorithmus übergebe.

Meine Frage: Wie kann man alle möglichen Pfade von Knoten A abrufen, um Knoten G zu sagen, oder sogar alle möglichen Pfade von Knoten A und zurück zu Knoten A.

Paul
quelle
1
Wenn Ihr Diagramm Zyklen enthält, kann dies eine extrem lange Liste sein.
Zmccord
Möchten Sie Pfade, die keine Eckpunkte / Kanten wiederholen?
Liam Mencel
@ HexTree Ich bin mir nicht sicher, was du meinst. Jeder Eckpunkt ist einzigartig. Ich suche im Grunde für jeden Pfad das Gewicht dieses Pfades und die Anzahl der Knoten, die über jeden Pfad berührt wurden
Paul
Warum willst du alle Wege finden? Wenn Ihre Frage lautet, wie Sie umleiten sollen, wenn einige Knoten ausgefallen sind usw., gibt es einige Algorithmen (Heuristiken). Aber Ihr aktueller Fall ist sehr allgemein und np-schwer.
Saeed Amiri
1
Hallo Paul, hast du diese Frage gelöst? Hier ist ein Link, der für Sie hilfreich sein kann: geeksforgeeks.org/find-paths-given-source-destination
GoingMyWay

Antworten:

58

Das Finden aller möglichen Pfade ist ein schwieriges Problem, da es eine exponentielle Anzahl einfacher Pfade gibt. Selbst das Finden des k-ten kürzesten Pfades (oder des längsten Pfades) ist NP-schwer .

Eine mögliche Lösung, um alle Pfade (oder alle Pfade bis zu einer bestimmten Länge) von sbis zu finden, tist BFS , ohne einen visitedSatz beizubehalten , oder für die gewichtete Version. Möglicherweise möchten Sie eine einheitliche Kostensuche verwenden

Beachten Sie, dass auch in jedem Diagramm mit Zyklen [es ist keine DAG ] unendlich viele Pfade zwischen sbis vorhanden sein können t.

amit
quelle
Vielen Dank, ich werde versuchen, mir BFS oder die einheitliche Kostensuche anzusehen
Paul
1
@ Paul: Gern geschehen. Stellen Sie einfach sicher, dass Sie in beiden Fällen keinen visitedSatz verwenden (wie der ursprüngliche Algorithmus vorschlägt), da sonst nur ein Teil der Pfade angezeigt wird. Außerdem sollten Sie Pfade auf eine bestimmte Länge beschränken, um Endlosschleifen zu vermeiden [wenn der Graph Zyklen hat ...]. Viel Glück!
Amit
3
@VShreyas Das ist ein alter Thread, die Antwort lautet speziell "alle Pfade bis zu einer bestimmten Länge", und das kann mit BFS ohne besuchten Satz gemacht werden. Wenn Sie alle einfachen Pfade zwischen zwei Knoten verwenden möchten , können Sie dies mit DFS mit "lokalem" besuchtem Satz tun (der einen Knoten aus dem besuchten Satz löscht, wenn er zurückverfolgt wird).
Amit
1
@GarethRees Angenommen, es gibt einen Polynomzeitalgorithmus (NICHT Pseudopolynomialalgorithmus) für den kkürzesten einfachen Pfad zwischen zwei Knoten. Da es höchstens (3/2)n!solche Pfade gibt, können Sie binär suchen und herausfinden, ob es einen einfachen Längenpfad gibt n. Da log{(3/2)n!} es sich um ein Polynom handelt n, ist sowohl die Codierung der Anzahl als auch der Anzahl der erforderlichen Wiederholungen in der Eingabegröße polynomisch. Da der Algorithmus für seine Eingabe auch in Polynomzeit ausgeführt wird, ist die Gesamtlaufzeit Polynom, und die Antwort lautet, ob zwischen den Knoten ein Hamilton-Pfad besteht. Wenn also ein solcher Algorithmus existiert, ist P = NP.
Am
1
@GarethRees Anhang : Anzahl der Pfade, wählen Sie Anzahl der Knoten im Pfad (i = 1, ...., n) für jedes i, wählen (n, i) Knoten und Neuordnungs sie (i!), Geben:(3/2)n! .
Amit
12

Ich habe eine Version implementiert, in der im Grunde alle möglichen Pfade von einem Knoten zum anderen gefunden werden, aber keine möglichen "Zyklen" gezählt werden (das von mir verwendete Diagramm ist zyklisch). Grundsätzlich wird also kein Knoten zweimal auf demselben Pfad angezeigt. Und wenn der Graph azyklisch wäre, könnte man sagen, dass er alle möglichen Pfade zwischen den beiden Knoten zu finden scheint. Es scheint gut zu funktionieren, und für meine Grafikgröße von ~ 150 läuft es fast sofort auf meinem Computer, obwohl ich sicher bin, dass die Laufzeit ungefähr exponentiell sein muss und es daher langsam langsam wird Grafik wird größer.

Hier ist ein Java-Code, der zeigt, was ich implementiert habe. Ich bin sicher, dass es auch effizientere oder elegantere Wege geben muss.

Stack connectionPath = new Stack();
List<Stack> connectionPaths = new ArrayList<>();
// Push to connectionsPath the object that would be passed as the parameter 'node' into the method below
void findAllPaths(Object node, Object targetNode) {
    for (Object nextNode : nextNodes(node)) {
       if (nextNode.equals(targetNode)) {
           Stack temp = new Stack();
           for (Object node1 : connectionPath)
               temp.add(node1);
           connectionPaths.add(temp);
       } else if (!connectionPath.contains(nextNode)) {
           connectionPath.push(nextNode);
           findAllPaths(nextNode, targetNode);
           connectionPath.pop();
        }
    }
}
Omer Hassan
quelle
Gibt es eine nicht rekursive Version davon?
Arslan
1
Ich habe keine, nein, aber ich denke, theoretisch kann jedes rekursive Programm in ein nicht rekursives Programm konvertiert werden. Ich denke, indem man so etwas wie ein Stapelobjekt verwendet, um zu emulieren, was ein rekursives Programm tatsächlich tut Ich glaube, ich benutze den Stapelspeicher des Programms. Sie können das Prinzip der Konvertierung rekursiver Programme in nicht rekursive Programme nachschlagen.
Omer Hassan
11

Ich werde Ihnen eine (etwas kleine) Version (obwohl verständlich, denke ich) eines wissenschaftlichen Beweises geben, dass Sie dies nicht in einer realisierbaren Zeitspanne tun können.

Was ich beweisen werde, ist, dass die zeitliche Komplexität, um alle einfachen Pfade zwischen zwei ausgewählten und unterschiedlichen Knoten (z. B. sund t) in einem beliebigen Graphen aufzulisten, Gkein Polynom ist. Beachten Sie, dass die Kantenkosten unwichtig sind, da wir uns nur um die Anzahl der Pfade zwischen diesen Knoten kümmern.

Sicher, wenn das Diagramm einige gut ausgewählte Eigenschaften hat, kann dies einfach sein. Ich denke jedoch über den allgemeinen Fall nach.


Angenommen, wir haben einen Polynomalgorithmus, der alle einfachen Pfade zwischen sund auflistet t.

Wenn Geine Verbindung besteht, ist die Liste nicht leer. Wenn dies Gnicht der Fall ist sund tsich in verschiedenen Komponenten befindet, ist es wirklich einfach, alle Pfade zwischen ihnen aufzulisten, da es keine gibt! Wenn sie sich in derselben Komponente befinden, können wir so tun, als ob der gesamte Graph nur aus dieser Komponente besteht. Nehmen wir also an, dass dies Gtatsächlich verbunden ist.

Die Anzahl der aufgelisteten Pfade muss dann polynomisch sein, sonst könnte der Algorithmus mir nicht alle zurückgeben. Wenn es alle aufzählt, muss es mir das längste geben, also ist es da drin. Mit der Liste der Pfade kann ein einfaches Verfahren angewendet werden, um mich auf den längsten Pfad hinzuweisen.

Wir können zeigen (obwohl ich mir keine zusammenhängende Art vorstellen kann, es auszudrücken), dass dieser längste Pfad alle Eckpunkte von durchlaufen muss G. Wir haben also gerade einen Hamilton-Pfad mit einer Polynomprozedur gefunden! Dies ist jedoch ein bekanntes NP-hartes Problem.

Wir können dann schließen, dass dieser Polynomalgorithmus, von dem wir dachten, dass er existiert, sehr unwahrscheinlich ist , es sei denn, P = NP .

Araruna
quelle
Wenn ich das richtig verstehe, funktioniert dieser Beweis nur für ungerichtete Graphen, da in einem gerichteten Graphen die Behauptung, dass "dieser längste Pfad alle Eckpunkte von G" durchlaufen muss, nicht unbedingt gilt. Ist das richtig?
Boycy
Nun ja, aber Sie könnten Ihren Algorithmus verwenden, um zu beantworten, ob es auf ähnliche Weise einen gerichteten Hamilton-Pfad gibt, der auch NP-vollständig ist. Wenn Ihre Antwort ist n-1, dann gibt es. Wenn dies nicht der Fall ist, könnte es keinen solchen Pfad geben, sonst wäre er länger als Ihr bekanntester längster.
Araruna
1
Nur um das klar zu stellen. Wenn die gerichtete Version in Poly-Zeit gelöst werden könnte, würde ihre Antwort die Antwort auf den gerichteten Hamilton-Pfad geben. Wenn wir gewichtete Kanten hätten, könnte man außerdem zeigen, dass wir durch einen Polynomprozess das Problem des Handlungsreisenden beantworten könnten.
Araruna
4

Hier ist ein Algorithmus, der alle Pfade von s nach t unter Verwendung der Modifikation von DFS findet und druckt. Auch die dynamische Programmierung kann verwendet werden, um die Anzahl aller möglichen Pfade zu ermitteln. Der Pseudocode sieht folgendermaßen aus:

AllPaths(G(V,E),s,t)
 C[1...n]    //array of integers for storing path count from 's' to i
 TopologicallySort(G(V,E))  //here suppose 's' is at i0 and 't' is at i1 index

  for i<-0 to n
      if i<i0
          C[i]<-0  //there is no path from vertex ordered on the left from 's' after the topological sort
      if i==i0
         C[i]<-1
      for j<-0 to Adj(i)
          C[i]<- C[i]+C[j]

 return C[i1]
Yanis
quelle
2

find_paths [s, t, d, k]

Diese Frage ist jetzt ein bisschen alt ... aber ich werde meinen Hut in den Ring werfen.

Ich persönlich finde einen Algorithmus der Form find_paths[s, t, d, k]nützlich, wobei:

  • s ist der Startknoten
  • t ist der Zielknoten
  • d ist die maximale Suchtiefe
  • k ist die Anzahl der zu findenden Pfade

Verwenden Sie die Unendlichkeitsform Ihrer Programmiersprache für dund kgeben Sie alle Pfade§.

Offensichtlich § wenn Sie einen gerichteten Graphen verwenden und Sie alle ungerichtete Pfade zwischen sund tSie werden diese in beide Richtungen laufen müssen:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

Hilfsfunktion

Ich persönlich mag Rekursion, obwohl es manchmal schwierig sein kann, lassen Sie uns trotzdem zuerst unsere Hilfsfunktion definieren:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

Hauptfunktion

Damit ist die Kernfunktion trivial:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

Lassen Sie uns zunächst einige Dinge beachten:

  • Der obige Pseudocode ist ein Mash-up von Sprachen - aber am stärksten Python ähnlich (da ich nur darin codiert habe). Ein striktes Kopieren und Einfügen funktioniert nicht.
  • [] Ist eine nicht initialisierte Liste, ersetzen Sie diese durch die Entsprechung für die Programmiersprache Ihrer Wahl
  • paths_foundwird als Referenz übergeben . Es ist klar, dass die Rekursionsfunktion nichts zurückgibt. Behandeln Sie dies angemessen.
  • hier graphwird irgendeine Form von hashedStruktur angenommen. Es gibt eine Vielzahl von Möglichkeiten, ein Diagramm zu implementieren. In beiden graph[vertex]Fällen erhalten Sie eine Liste benachbarter Scheitelpunkte in einem gerichteten Diagramm - passen Sie sie entsprechend an.
  • Dies setzt voraus, dass Sie vorverarbeitet haben, um "Schnallen" (Selbstschleifen), Zyklen und Mehrfachkanten zu entfernen
SumNeuron
quelle
2

Wenn Sie Ihre Pfade tatsächlich vom kürzesten zum längsten Pfad ordnen möchten, ist es weitaus besser, einen modifizierten A * - oder Dijkstra-Algorithmus zu verwenden . Mit einer geringfügigen Änderung gibt der Algorithmus so viele der möglichen Pfade zurück, wie Sie möchten, und zwar in der Reihenfolge des kürzesten Pfades zuerst. Wenn Sie also wirklich alle möglichen Pfade vom kürzesten zum längsten geordnet haben möchten, ist dies der richtige Weg.

Wenn Sie eine A * -basierte Implementierung wünschen, die alle vom kürzesten zum längsten geordneten Pfade zurückgeben kann, wird dies im Folgenden erreicht. Es hat mehrere Vorteile. Zunächst einmal ist es effizient beim Sortieren vom kürzesten zum längsten. Außerdem wird jeder zusätzliche Pfad nur bei Bedarf berechnet. Wenn Sie also vorzeitig anhalten, weil Sie nicht jeden einzelnen Pfad benötigen, sparen Sie Verarbeitungszeit. Außerdem werden Daten für nachfolgende Pfade jedes Mal wiederverwendet, wenn der nächste Pfad berechnet wird, um die Effizienz zu steigern. Wenn Sie einen gewünschten Pfad finden, können Sie ihn vorzeitig abbrechen, um Rechenzeit zu sparen. Insgesamt sollte dies der effizienteste Algorithmus sein, wenn Sie nach Pfadlänge sortieren möchten.

import java.util.*;

public class AstarSearch {
    private final Map<Integer, Set<Neighbor>> adjacency;
    private final int destination;

    private final NavigableSet<Step> pending = new TreeSet<>();

    public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
        this.adjacency = adjacency;
        this.destination = destination;

        this.pending.add(new Step(source, null, 0));
    }

    public List<Integer> nextShortestPath() {
        Step current = this.pending.pollFirst();
        while( current != null) {
            if( current.getId() == this.destination )
                return current.generatePath();
            for (Neighbor neighbor : this.adjacency.get(current.id)) {
                if(!current.seen(neighbor.getId())) {
                    final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
                    this.pending.add(nextStep);
                }
            }
            current = this.pending.pollFirst();
        }
        return null;
    }

    protected int predictCost(int source, int destination) {
        return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
    }

    private static class Step implements Comparable<Step> {
        final int id;
        final Step parent;
        final int cost;

        public Step(int id, Step parent, int cost) {
            this.id = id;
            this.parent = parent;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public Step getParent() {
            return parent;
        }

        public int getCost() {
            return cost;
        }

        public boolean seen(int node) {
            if(this.id == node)
                return true;
            else if(parent == null)
                return false;
            else
                return this.parent.seen(node);
        }

        public List<Integer> generatePath() {
            final List<Integer> path;
            if(this.parent != null)
                path = this.parent.generatePath();
            else
                path = new ArrayList<>();
            path.add(this.id);
            return path;
        }

        @Override
        public int compareTo(Step step) {
            if(step == null)
                return 1;
            if( this.cost != step.cost)
                return Integer.compare(this.cost, step.cost);
            if( this.id != step.id )
                return Integer.compare(this.id, step.id);
            if( this.parent != null )
                this.parent.compareTo(step.parent);
            if(step.parent == null)
                return 0;
            return -1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Step step = (Step) o;
            return id == step.id &&
                cost == step.cost &&
                Objects.equals(parent, step.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, parent, cost);
        }
    }

   /*******************************************************
   *   Everything below here just sets up your adjacency  *
   *   It will just be helpful for you to be able to test *
   *   It isnt part of the actual A* search algorithm     *
   ********************************************************/

    private static class Neighbor {
        final int id;
        final int cost;

        public Neighbor(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public int getCost() {
            return cost;
        }
    }

    public static void main(String[] args) {
        final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
        final AstarSearch search = new AstarSearch(adjacency, 1, 4);
        System.out.println("printing all paths from shortest to longest...");
        List<Integer> path = search.nextShortestPath();
        while(path != null) {
            System.out.println(path);
            path = search.nextShortestPath();
        }
    }

    private static Map<Integer, Set<Neighbor>> createAdjacency() {
        final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();

        //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to.
        addAdjacency(adjacency, 1,2,1,5,1);         //{1 | 2,5}
        addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
        addAdjacency(adjacency, 3,2,1,5,1);         //{3 | 2,5}
        addAdjacency(adjacency, 4,2,1);             //{4 | 2}
        addAdjacency(adjacency, 5,1,1,2,1,3,1);     //{5 | 1,2,3}

        return Collections.unmodifiableMap(adjacency);
    }

    private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
        if( dests.length % 2 != 0)
            throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");

        final Set<Neighbor> destinations = new HashSet<>();
        for(int i = 0; i < dests.length; i+=2)
            destinations.add(new Neighbor(dests[i], dests[i+1]));
        adjacency.put(source, Collections.unmodifiableSet(destinations));
    }
}

Die Ausgabe des obigen Codes lautet wie folgt:

[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]

Beachten Sie, dass bei jedem Aufruf nextShortestPath()bei Bedarf der nächst kürzere Pfad für Sie generiert wird. Es werden nur die zusätzlichen erforderlichen Schritte berechnet und keine alten Pfade zweimal durchlaufen. Wenn Sie entscheiden, dass Sie nicht alle Pfade benötigen und die Ausführung vorzeitig beenden, haben Sie sich außerdem erhebliche Rechenzeit gespart. Sie berechnen nur bis zur Anzahl der benötigten Pfade und nicht mehr.

Schließlich sollte angemerkt werden, dass die A * - und Dijkstra-Algorithmen einige geringfügige Einschränkungen aufweisen, obwohl ich nicht glaube, dass dies Auswirkungen auf Sie haben würde. Es funktioniert nämlich nicht richtig in einem Diagramm mit negativen Gewichten.

Hier ist ein Link zu JDoodle, über den Sie den Code selbst im Browser ausführen und sehen können, wie er funktioniert. Sie können das Diagramm auch ändern, um anzuzeigen, dass es auch in anderen Diagrammen funktioniert: http://jdoodle.com/a/ukx

Jeffrey Phillips Freeman
quelle
2

Die folgenden Funktionen (modifiziertes BFS mit einer rekursiven Pfadfindungsfunktion zwischen zwei Knoten) erledigen die Aufgabe für einen azyklischen Graphen :

from collections import defaultdict

# modified BFS
def find_all_parents(G, s):
    Q = [s]
    parents = defaultdict(set)
    while len(Q) != 0:
        v = Q[0]
        Q.pop(0)
        for w in G.get(v, []):
            parents[w].add(v)
            Q.append(w) 
    return parents

# recursive path-finding function (assumes that there exists a path in G from a to b)   
def find_all_paths(parents, a, b): 
    return [a] if a == b else [y + b for x in list(parents[b]) for y in find_all_paths(parents, a, x)]

Zum Beispiel mit dem folgenden Diagramm ( DAG ) Gvon

G = {'A':['B','C'], 'B':['D'], 'C':['D', 'F'], 'D':['E', 'F'], 'E':['F']}

Wenn wir alle Pfade zwischen den Knoten 'A'und 'F'(unter Verwendung der oben definierten Funktionen als find_all_paths(find_all_parents(G, 'A'), 'A', 'F')) finden möchten , werden die folgenden Pfade zurückgegeben:

Geben Sie hier die Bildbeschreibung ein

Sandipan Dey
quelle
1

Normalerweise möchten Sie das nicht, da es in nichttrivialen Diagrammen eine exponentielle Anzahl davon gibt. Wenn Sie wirklich alle (einfachen) Pfade oder alle (einfachen) Zyklen erhalten möchten, finden Sie nur einen (indem Sie durch die Grafik gehen) und kehren dann zu einem anderen zurück.

jpalecek
quelle
Es ist einfach, effizient und für jede DAG machbar. Sie führen @Paul in die Irre.
Diego
0

Ich nehme an, Sie möchten 'einfache' Pfade finden (ein Pfad ist einfach, wenn kein Knoten mehr als einmal darin erscheint, außer vielleicht dem ersten und dem letzten).

Da das Problem NP-schwer ist, möchten Sie möglicherweise eine Variante der Tiefensuche durchführen.

Generieren Sie grundsätzlich alle möglichen Pfade aus A und prüfen Sie, ob sie in G enden.

Zruty
quelle