webentwicklung-frage-antwort-db.com.de

Finde alle Pfade zwischen zwei Graphenknoten

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

Meine Frage: Wie ruft man alle möglichen Pfade von Node A zu sagen Node G oder sogar alle möglichen Pfade von Node A und zurück zu Node A

59
Paul

Das Finden aller möglichen Pfade ist ein schwieriges Problem, da es eine exponentielle Anzahl einfacher Pfade gibt. Sogar 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 s bis t zu finden, ist BFS , ohne dass ein visited gesetzt ist, oder für die gewichtete Version - Möglicherweise möchten Sie einheitliche Kostensuche verwenden

Beachten Sie, dass es in jedem Graphen mit Zyklen [es ist kein DAG ] unendlich viele Pfade zwischen s und t geben kann.

49
amit

Ich habe eine Version implementiert, in der grundsätzlich alle möglichen Pfade von einem Knoten zum anderen gefunden werden, aber es werden keine möglichen 'Zyklen' gezählt (der von mir verwendete Graph ist zyklisch). Im Grunde wird also kein Knoten innerhalb desselben Pfades zweimal vorkommen. 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 mir sicher bin, dass die Laufzeit so etwas wie exponentiell sein muss und so langsam wird wie die Grafik wird größer.

Hier ist ein Java Code, der zeigt, was ich implementiert habe. Ich bin mir sicher, dass es auch effizientere oder elegantere Methoden 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();
        }
    }
}
10
Omer Hassan

Ich werde Ihnen eine (etwas kleine) Version (obwohl verständlich, glaube 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 zum Aufzählen aller einfachen Pfade zwischen zwei ausgewählten und unterschiedlichen Knoten (z. B. s und t) in einem beliebigen Graphen G ist nicht polynomial. Beachten Sie, dass die Edge-Kosten unwichtig sind, da uns nur die Anzahl der Pfade zwischen diesen Knoten am Herzen liegt.

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


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

Wenn G verbunden ist, ist die Liste nicht leer. Wenn G nicht ist und s und t sich in verschiedenen Komponenten befinden, 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 bestünde das gesamte Diagramm nur aus dieser Komponente. Nehmen wir also an, dass G tatsächlich verbunden ist.

Die Anzahl der aufgelisteten Pfade muss dann polynomisch sein, da der Algorithmus sonst nicht alle zurückgeben kann. Wenn es alle auflistet, 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, dass dieser längste Pfad alle Eckpunkte von G durchqueren muss (obwohl ich mir keinen zusammenhängenden Ausdruck vorstellen kann). Wir haben also gerade einen Hamilton-Pfad mit einer Polynomprozedur gefunden! Dies ist jedoch ein bekanntes NP-schwieriges Problem.

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

9
araruna

Here ist ein Algorithmus, der alle Pfade von s nach t unter Verwendung der DFS-Modifikation 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]
4
yanis

find_paths [s, t, d, k]

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

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 maximal zu durchsuchende Tiefe
  • k ist die Anzahl der zu findenden Pfade

Wenn Sie die Unendlichkeitsform Ihrer Programmiersprache für d und k verwenden, erhalten Sie alle Pfade§.

§ Natürlich, wenn Sie einen gerichteten Graphen verwenden und alle ungerichteten Pfade zwischen s und t haben möchten Um dies in beide Richtungen auszuführen:

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, lasst 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 ein paar Dinge beachten:

  • der obige Pseudocode ist ein Mash-up von Sprachen - aber am stärksten ähnlich python (da ich nur darin programmiert habe). Ein striktes Kopieren-Einfügen funktioniert nicht.
  • [] Ist eine nicht initialisierte Liste. Ersetzen Sie diese durch die Entsprechung für die Programmiersprache Ihrer Wahl
  • paths_found Wird von Referenz übergeben. Es ist klar, dass die Rekursionsfunktion nichts zurückgibt. Behandeln Sie dies angemessen.
  • hier nimmt graph eine Form von hashed Struktur an. Es gibt eine Vielzahl von Möglichkeiten, ein Diagramm zu implementieren. In beiden Fällen erhalten Sie mit graph[vertex] Eine Liste benachbarter Scheitelpunkte in einem gerichteten Diagramm - passen Sie dies entsprechend an.
  • dies setzt voraus, dass Sie vorverarbeitet haben, um "Buckles" (Selbstschleifen), Zyklen und Mehrkanten zu entfernen
2
SumNeuron

Ich denke, was Sie wollen, ist eine Form des Ford-Fulkerson-Algorithmus, der auf BFS basiert. Es wird verwendet, um den maximalen Fluss eines Netzwerks zu berechnen, indem alle Erweiterungspfade zwischen zwei Knoten ermittelt werden.

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

1
richmb

Wenn Sie Ihre Pfade 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 mögliche 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 bestellen möchten, ist dies der richtige Weg.

Wenn Sie eine A * -basierte Implementierung wünschen, die in der Lage ist, alle vom kürzesten zum längsten geordneten Pfade zurückzugeben, wird dies durch die folgenden Schritte erreicht. Das hat mehrere Vorteile. Zuallererst ist es effizient, von der kürzesten zur längsten zu sortieren. 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 bei jeder Berechnung des nächsten Pfads für nachfolgende Pfade wiederverwendet, um eine höhere Effizienz zu erzielen. Wenn Sie einen gewünschten Pfad gefunden haben, können Sie den Vorgang 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 jedes Mal, wenn Sie nextShortestPath() aufrufen, bei Bedarf der nächste kürzeste Pfad für Sie generiert wird. Es werden nur die zusätzlichen Schritte berechnet und keine alten Pfade zweimal überquert. Wenn Sie sich außerdem dazu entschließen, nicht alle Pfade zu benötigen und die Ausführung vorzeitig zu beenden, sparen Sie sich erhebliche Rechenzeit. Sie berechnen nur bis zu der Anzahl der Pfade, die Sie benötigen, und nicht mehr.

Abschließend 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 direkt in einem Graphen 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

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

1
jpalecek

Ich nehme an, Sie möchten nach "einfachen" Pfaden suchen (ein Pfad ist einfach, wenn kein Knoten mehr als einmal darin vorkommt, 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.

0
Zruty

Es gibt einen netten Artikel, der Ihre Frage beantworten kann/nur werden die Pfade gedruckt, anstatt sie zu sammeln /. Bitte beachten Sie, dass Sie mit den C++/Python-Beispielen in der Online-IDE experimentieren können.

http://www.geeksforgeeks.org/find-paths-given-source-destination/

0
Attila Karoly