Methoden Wegsuche in einem Graph

[SchokoPanzer]

Nunja, es geht primär darum alle Wege in von einem Startknoten zu dem besagten Endknoten zu finden. Ich hab hier meinen rekursiven Ansatz, nur irgendwie funktioniert der nicht so ganz richtig wie er soll.

Naja zum Code selbst
Der Graph ist gerichtet
Kanten sind über eine Hashmap<T, HashSet<T>> implementiert
Die Idee ist über eine ForEach Schleife alle verfügbaren Zielknoten vom jeweiligen Standpunkt aus zu abzulaufen und halt cycle's zu vermeiden. Erfolgreich gefundene Pfade sollen in einer List<List<T> gespeichert werden.

Mein Problem ist, dass er a) immer nur einen Pfad findet und b) ist es nicht immer der gleiche Oo
Ab und an hängt er auch mal nen Knoten an den Pfad, obwohl keine Kante dahin führt.

Hat irgendwer ne Idee was falsch gelaufen sein könnte?
Ich vermute ich mach einen Denkfehler bei der Rekursion, aber hab keine Ahnung ob ich damit richtig liege und wie ichs anders machen könnte.

Wäre Dankbar für jedwede Hilfe =)


[Java]
private void RecursiveAllPathSearch(T CurrentNode, T endNode, ArrayList<T> path){
if (path.contains(CurrentNode)){ // cycle's abfangen
path = null;
}

else {
if (CurrentNode == endNode){ //erfolgreichen path speichern
path.add(CurrentNode);
paths.add(path);
}
else {
path.add(CurrentNode); // weiter "forschen" -> rekursiv
HashSet<T> NextNodes = edges.get(CurrentNode);
for(T elements : NextNodes){
RecursiveAllPathSearch(elements, endNode, path);
}
}

}
}
[Java]

 

[Herr K.]

Hallo,

ohne mir den Code näher angeschaut zu haben, fällt sofort ein Fehler auf:

f (path.contains(CurrentNode)){ // cycle's abfangen
path = null;
}

else {
if (CurrentNode == endNode){ //erfolgreichen path speichern
path.add(CurrentNode);

Da kannst Du gar nicht mehr als einen Weg finden, denn der Endknoten gehört zu jedem erfolgreichen Weg, Du verwirfst aber jeden Knoten, den Du schon kennst. Hier ist es (wie so oft) wichtig, dass Du die Reihenfolge beachtest.

Bei rekursiven Aufrufen sollte man immer mit dem Rekursionsanker anfangen, in Deinem Fall Endet die Rekursion in zwei Fällen:

1. Du hast den Endknoten gefunden
2. Es gibt keine Kindknoten mehr

 

[SchokoPanzer]

Wie implimentier ich das denn dann am sinnvollsten?

Schon richtig, die Methode soll aufhören sich in dieser Instanz aufzurufen wenn sie das Ziel hat, oder es nicht mehr weiter geht (Ende oder Cycle)

Die For Each soll in dem Fall garantieren dass für jeden verfügbaren Pfad vom derzeitigen Knoten weg, die methode mit den jeweiligen werten neu aufgerufen wird.

Für mich bedeutet dass, dass die Methode eigentlich weitermacht solange nicht alle For Each abgeklappert wurden ( Sinn einer For Each Schleife ), nur dass erfolgreiche Pfade nicht rekursiv weiter geführt werden, aber die restlichen sollten es doch eigentlich oder Oo?

 

[Gast2]

Ohne jetzt alles durchgelesen zu haben:
Hast du dir folgenden Algo mal angeschaut?
Dijkstra-Algorithmus ? Wikipedia

 

[SchokoPanzer]

Ja hab ich, ich brauch aber alle Pfade zum Ziel ausgegeben und nicht nur den kürzesten

ich brauch einen Algorithmus der alle Pfade zum Ziel findet, und mir diese Ausgibt ( am sinnvollsten in einer List of Lists )
Jeder Pfad soll durch eine Liste dargestellt werden

Wenn der Algorithmus nicht weitermachen, weil er sonst Cyclen würde, oder halt es keine Kindknoten mehr gibt, soll der bis dato erstellte Pfad einfach verworfen werden


Mein Problem ist dass mein Algorithmus komische Dinge tut und ich absolut keine Idee hab woran das liegt

 

[XHelp]

Warum baust du dir nicht einfach ein paar Debugausgaben rein und schaust, wie das ganze wirklich abläuft?
Du könntest deine Methode etwas umschreiben, damit die wirklich was zurückliefern. Ungetesteter Pseudocode:

List<List<T>> findPaths(T from, T to, List<T> currentPath) {
  List<List<T>> results = new ArrayList<List<T>>();
  if (currentPath.contains(from)) {
    return results;
  }
  if (from.equals(to)) {
    results.add(currentPath);
    return results;
  }
  currentPath.add(from);
  for (T child: nodeList) {
    results.addAll(findPaths(child, to, currentPath));
  }
  return results;
}

 

[SchokoPanzer]

So es ist geschafft =)

Nach etlichen Debugausgaben und mit dem Gedanken bei dem von Mr K. angesprochenen fehlerhaften Rekursionsanker
wanderte nun endlich die hand zum kopf, der mund ging auf und ich hab mich ewig für meine blödheit verflucht 🙂

ändert man

if (CurrentPath.contains(FromNode)){...}

in

if (CurrentPath.contains(FromNode) && FromNode != ToNode){ ... }

fängt der auf einmal an sinnvolle Pfade auszuspucken ^^

lg
Schoko

und vielen Dank für die Denkanstöße