Backtracking bei verzweigender Rekursion

[petter2]

Hallo!

Folgendes Problem:

Func Funktion($a)

If Fehler() Then Return -1

; Funktion

; ...

For $a in $b ; Bedingung für weitere Durchführungen

$erfolgreich = Funktion($a)

If $erfolgreich == -1 Then 

; Funktion rückgängig machen

; ...

Return -1

EndIf

Next

Return 1

EndFunc

Angenommen, er geht das erste mal in die Funktion hinein. Die zweite Ebene durchläuft er auch, der erste Zweig ist erfolgreich und er kommt wieder zurück, beim zweiten Zweig gibt es einen Fehler. Dann löscht er auch die erste Ebene. Aber was muss man wie programmieren, damit er auch die Entscheidungen von der zweiten Ebene vom ersten Zweig löscht (das ist ja auch verzweigt und verschachtelt)?

Ich hoffe ich habe mich verständlich ausgedrückt, ansonsten bitte Fragen.

Vielen Dank!

[flashpixx]

Ich verstehe das Problem nicht, evtl machst Du mal eine Graphik, wie der Baum aussieht. Beim Backtracking wird bei einem Fehler der Zweig so lange wieder aufwärts durchlaufen bis an einem Knoten eine noch nicht bearbeite Möglichkeit entsteht, siehe Backtracking

Wenn wie im Bild der Code 1,8,12 läuft, 12 einen Fehler produziert, dann geht er auf die 8, geht in die 9 usw. wenn die 9 abgearbeitet ist, geht er in die 8 und 1. Die Reihenfolge legt die Traversierung fest

[petter2]

Vielen Dank für Deine Antwort!

Ich habe mal versucht mit Paint das darzustellen. Wenn das Programm auf ein Problem trifft, soll er so lange zurück gehen, bis eine andere Möglichkeit vorhanden ist (das ist in der Grafik nicht ersichtlich). Meine Frage ist jetzt, wie ich die Blau markierten Felder wieder "leeren" kann, da da ja durch die andere Entscheidung auch wiederrum alles ändern kann.

Vielen Dank!

EDIT:

Wird aber deutlich komplizierter, z.B. hier, zurück bis auf 2:

Bearbeitet 11. November 2011 von petter2

[flashpixx]

Ah okay. Also da es ja bei Dir wie ein Binärbaum aussieht, würde ich gar nicht zu einem Baum tendieren, sondern diesen linear ablegen ( Binärbaum ), damit kannst Du die Positionen der Blätter direkt anspringen und ggf ändern. Falls es eben kein Binärbaum ist, kannst Du Dir während der Traversierung Pointer auf die Knoten / Blätter speichern, so dass Du eben bei einem Fehler alle bisher durchlaufenen Knoten / Blätter direkt verändern kannst.

In C++ würde ich eben einen std::vector<node*> anlegen und bei jedem durchlaufen des Knotens diesen des Vectors hinzufügen, wenn ein Fehler auftritt kann man dann diese Liste durchlaufen und verarbeiten. Letzteres würde auch mit einer beliebigen Art eines Baumes funktionieren, erfordert aber halt eine zusätzliche Datenstruktur, die so viele Elemente enthält, wie es Knoten im Baum gibt, wenn der Baum vollständig / ohne Fehler aufgebaut wird

Bearbeitet 11. November 2011 von flashpixx

[petter2]

OK, danke!

Jede Verbindung braucht eine Pfeilrichtung. Jedes Kästchen hat aber ein bestimmtes Limit, wie viel Pfeile dort hinzeigen dürfen. Fällt einem dazu vielleicht noch etwas ein?

Die Verbindungen und Kästchen sind in zwei Arrays.

Bearbeitet 11. November 2011 von petter2

[flashpixx]

Nein man braucht keine Richtung, denn die Richtung wird durch die Traversierung bestimmt. Du brauchst nur Zeiger auf die Knoten.

[petter2]

Das ist aber meine Problemstellung

Die Richtung, wie das Skript auf die Verbindung kommt, ist, wie von dir geschrieben, egal.

[flashpixx]

Wo ist das Problem !? Für jeden Knoten wird entschieden, ob diese nun einen Fehlerzustand true / false hat, wenn der Zustand true ist, dann können alle Knoten, die bis zu diesem verarbeitet wurden, nochmals besucht werden, in dem man eine eben die Liste mitführt. Welche Knoten in der Liste landen, legt die Traversierung fest.

[petter2]

Ok, also eine Liste führen. Vielen Dank!