Rekursionen abbrechen

[andi_wand]

Moin,
ich bins scho wieder, da ich noch eine Frage habe.
Folgendes: Ich hab ein Programm, in dem eine Funktion rekursiv arbeitet. Normalerweise ist es ja so, dass, wenn ich das Rekursionsende erreicht habe, dass ich dann um eine Stufe zurückgehe, dort diese Stufe wieder beenden muss, usw.
Wie kann ich denn gleich mehrere Stufen überspringen?
D.h. dass, wenn die Rekursion beendet wurde, dass ich dann gleich bis zur 5. Stufe zurückspringen kann.
Für Hinweise wäre ich euch dankbar

[EyDu]

Das könnte man über den Rückgabewert regeln. Was genau hast du denn vor?

[andi_wand]

Ich bin immer noch bei der Labyrinth-Aufgabe, die ich mittels Rekursion lösen soll. Dort gehe ich wie folgt vor:

Code: Alles auswählen

def solve_Backtrack(self,start, last_Pos,last_Crossing):
        Pos=start
        if(type(start)==None):
            print "Lab has no starting point. Exiting"
            sys.exit()
        Pos_x=Pos[0]
        Pos_y=Pos[1]
        Pos_x_last=last_Pos[0]
        Pos_y_last=last_Pos[1]
        time.sleep(0.02)
        print "Schritt"
        print self.__str__()
        if(self.maze_Rows[Pos_x+1][Pos_y]=="F"):
            print "Finished"
            print Pos_x,Pos_y
            return 0
        else:
            if(self.maze_Rows[Pos_x-1][Pos_y]=="F"):
                print "Finished"
                print Pos_x,Pos_y
                return 0
            else:
                if(self.maze_Rows[Pos_x][Pos_y-1]=="F"):
                    print "Finished"
                    print Pos_x,Pos_y
                    return 0
                else:
                    if(self.maze_Rows[Pos_x][Pos_y+1]=="F"):
                        print "Finished"
                        print Pos_x,Pos_y
                        return 0
                    
        suggested_dir=suggest((Pos_x,Pos_y),self.maze_Rows,(Pos_x_last,Pos_y_last))
        counter=0
        for i in xrange(len(suggested_dir)):
            if(suggested_dir[i]==True):
                counter = counter+1
        if(counter>=2):
            self.Crossings.append((Pos_x,Pos_y))
            last_Crossing=last_Crossing+1
        if(suggested_dir[0]==True):
            self.solve_Backtrack((Pos_x+1,Pos_y), (Pos_x,Pos_y),last_Crossing)
            self.maze_Rows[Pos_x][Pos_y]="."
        else:
            if(suggested_dir[1]==True):
                self.solve_Backtrack((Pos_x-1,Pos_y), (Pos_x,Pos_y),last_Crossing)
                self.maze_Rows[Pos_x][Pos_y]="."
            else:
                if(suggested_dir[2]==True):
                    self.solve_Backtrack((Pos_x,Pos_y-1), (Pos_x,Pos_y),last_Crossing)
                    self.maze_Rows[Pos_x][Pos_y]="."
                else:
                    if(suggested_dir[3]==True):
                        self.solve_Backtrack((Pos_x,Pos_y+1), (Pos_x,Pos_y),last_Crossing)
                        self.maze_Rows[Pos_x][Pos_y]="."
                    else:
                        if(last_Crossing==0):
                            print "Lab could not solved. Exiting"
                            sys.exit()
                        last_waypoint=self.Crossings[last_Crossing-1]
                        self.Crossings.pop()
                        last_Crossing=last_Crossing-1
                        self.solve_Backtrack(last_waypoint, last_waypoint, last_Crossing)

Nun will ich aber, sofern ich in einer Sackgasse stecke, zu der Rekursionsstufe zurück, in der ich an der letzten Kreuzung war, und alle anderen, die darunter waren, löschen.
Wie mache ich das dann?
Danke

[EyDu]

Wende doch erstmal die von BlackJack genannten Vorschläge auf deinen Code an, damit verkürzt er sich auf die Hälft und strotzt nicht mehr vor Redundanz und haarsträubenden Dingen. Dann kann man vielleicht sinnvol das Problem lösen.

[andi_wand]

suggest() wurde bereits bearbeitet, für diese Funktion (maze_Backtrack()) gab es leider keine Verbesserung...
Danke

[EyDu]

Es wurden genug allgemeine Tipps gegeben, welche du auch auf diesen Code anwenden kannst.

[andi_wand]

Ok, ich versuchs mal, melde mich dann vermutlich morgen wieder.
Danke aber für die Hilfe

[Hyperion]

Ohne mich damit jetzt tiefer befasst zu haben: Reicht es nicht aus, so lange aus der Rekursion zurückzukehren, bis man an einen Punkt gelangt, an dem man sich noch "neu" entscheiden kann? Man muss sich natürlich an jeder Position merken, welche Entscheidungsmöglichkeiten hinsichtlich der Richtungswahl noch offen sind...

[andi_wand]

Genau das möchte ich ja umgehen, ich möchte direkt zurückspringen, ohne den Umweg zu machen...

[/me]

Genau das möchte ich ja umgehen, ich möchte direkt zurückspringen, ohne den Umweg zu machen...

"Gehe direkt zu Assembler. Gehe direkt dorthin. Ziehe nicht 4000 DM ein."

Woher weißt du denn, wie viele Funktionsaufrufe du zurückspringen möchtest? Grundsätzlich ist das ein dermaßen verkorkster Ansatz, dass du so etwas meiner Einschätzung nach in keiner einzigen Hochsprache geboten bekommst.

[andi_wand]

Ich weiß, wie viele Funktionenaufrufe ich zurückspringen muss (wird in einer Variablen abgelegt). Die Frage ist nur, wie ich das genau mache, sodass ich nicht den "normalen" Weg über die aufrufende Funktion gehe, sondern direkt zurückkomme.

[Hyperion]

Genau das möchte ich ja umgehen, ich möchte direkt zurückspringen, ohne den Umweg zu machen...

Das ist doch nur eine Optimierung! Bei "Ästen", die keine Wahlmöglichkeit bieten, kann man natürlich auf Rekursion verzichten und direkt so lange "weitergehen", bis man an eine Stelle kommt, an der man wählen kann.

Beispiel:

Code: Alles auswählen

########
#S     #
########

In diesem simplen Labyrinth kann ich natürlich nur nach rechts gehen, da ich in jedem Feld nur eine Wahlmöglichkeit habe. Komme ich am Ende an, so würde ich aus der letzten Rekursionsstufe zurückspringen. In der Ebene davor erkenne ich nun, dass ich hier auch keine Wahlmöglichkeit mehr habe und springe auch zurück, usw. Der Prozess endet im Startpunkt.

Erweitern wir das Labyrinth:

Code: Alles auswählen

########
#S     #
# ######
# #
# #
###

Hier habe ich bereits im Startpunkt die Option, zwei Richtungen (rechts und unten) einzuschlagen. Den Weg nach rechts hatten wir ja schon. Bin ich aus der Rekursion bis auf die erste Ebene zurückgekehrt, kann ich erkennen, dass meine Wahlliste noch den Eintrag "unten" umfasst. Diesen wähle ich nun als nächstes und beginne erneut mit dem Abstieg der Rekursion. Am Ende angelangt springt man auch hier wieder bis zur ersten Ebene zurück.

Mehr als eine Ebene kann man aus einer Rekursion nicht zurückspringen - zumindest geht das in Python nicht / mir ist da kein Weg bekannt. Will ich diese "trivialen" Abschnitte also optimieren, so kann ich bei nur einer Wahlmöglichkeit auf Rekursion verzichten und einfach den Strang so lange weitergehen, bis ich wieder auf ein Feld treffe, an dem ich wählen kann. Den "Pfad" dazwischen muss ich mir halt entsprechend merken und bei einem erfolgreichen Pfad bis zum Ziel komplett einfügen - oder eben komplett verwerfen, sollte dieser Ast nicht zielführend sein. Das ist imho aber eben eine Optimierung und ich würde das erst einmal außen vor lassen, bevor ich nicht einfach auch so eine Lösung gefunden habe.

[/me]

Ich weiß, wie viele Funktionenaufrufe ich zurückspringen muss (wird in einer Variablen abgelegt). Die Frage ist nur, wie ich das genau mache, sodass ich nicht den "normalen" Weg über die aufrufende Funktion gehe, sondern direkt zurückkomme.

Du kannst den Stack nicht manipulieren.

Grundsätzlich wirkt das jetzt so, als wärest du mit Rekursionen überfordert. Wie auch immer, du könntest vielleicht eine spezielle Exception definieren und werfen, die dann auf der passenden Ebene gefangen wird(bzw. auf unpassenden Ebenen durchgereicht).

[andi_wand]

@Hyperion: Ich denke, so werd ich das mal umsetzen.
@/me: Ich versuche nur, die Rekursionsfunktion zu optimieren
Danke für den Tipp

[Hyperion]

Ich habe es mal auf die schnelle selber implementiert - ohne Optimierungen. Meine rekursive Funktion hat 11 Zeilen. Im Grunde bin ich einfach so vorgegangen:

1.) Prüfen, ob Ausgang (bestimmtes Symbol) erreicht ist, wenn ja, aktuelle Position zurückgeben.
2.) Aktuelle Position als besucht markieren
3.) Mögliche Wegoptionen scannen (separate Funktion)
4.) Alle Möglichkeiten durchgehen, Funktion rekursiv mit aktueller Position + "Offset" der aktuell betrachteten Wahlmöglichkeit aufrufen.
5.) Sofern ein Rückabewert (Liste der Positionen als Pfad) vorliegt, aktuelle Position anhängen und zurückliefern

Am Ende erhält man eine Liste, die alle Felder beinhaltet (x und y Wert). Diese liegt natürlich in verkehrter Reihenfolge vor.

Meine vorgeschlagene Optimierung sollte sich da relativ einfach einbauen lassen - aber ich frage mich dennoch: Wozu? Rekursion ist in diesem Falle eh keine wirklich praktikable Lösung.

[andi_wand]

Das ist leider die Aufgabe, sonst hätte ich schon drei andere Varianten gehabt...

[Hyperion]

Das ist leider die Aufgabe, sonst hätte ich schon drei andere Varianten gehabt...

Was ist genau die Aufgabe?

[andi_wand]

Aufgabe: Implementieren Sie ein Pythonprogramm welches ein Labyrinth aus
einer Datei einliest und einen Weg vom Start (S) zum Ziel (F) findet und ausgibt.
Im Folgenden wird der Aufbau des Programms im Detail besprochen.
1.) Das Labyrinth
Es benden sich mehrere Beispiele auf der Webseite. Eine Wand ist im Labyrinth
durch ein '#' gekennzeichnet. Der Start wird mit 'S' und das Ziel mit 'F' markiert:
Eine Position im Labyrinth wird durch kartesische Koordinaten beschrieben, wobei
links oben der Punkt (0; 0) ist. D.h. im Beispiel oben, hat der Start 'S' die
Koordinaten (1; 11) das Ziel 'F' die Koordinaten (11, 1). Achtung: hier sind zur
besseren Lesbarkeit zusatzliche Leerzeichen eingebaut. Dies ist bei den Beispielen
auf der Webseite nicht der Fall. Es ist aber nutzlich (und sogar einfacher) auch bei
der Ausgabe des Python-Programms geeignet zusatzliche Leerzeichen auszugeben.
Erstellen Sie eine Klasse Maze, welche die folgenden Funktionen unterstutzt:
i) Die Klasse wird mit
m = Maze("maze1.txt")
instanziert, wobei sich in der Datei \maze1.txt" ein Labyrinth bendet welches
von geeigneten Methoden der Klasse gelesen und entsprechend gespeichert
wird.
ii) Auf das Element (x; y) des Labyrinths kann mit m[x, y] zugegriffen werden.
Zusatzlich kann mit m[x, y] = '.' ein Element im Labyrinth auf '.' gesetzt
werden.
iii) Die Klasse soll eine Methode getStart haben, welche die Position (x; y)
des Starts zuruck gibt, im Beispiel oben also (1; 11). Der Start ist mit dem
Buchstaben \S" gekennzeichnet.
iv) Das Labyrinth soll einfach mit
print m
ausgegeben werden konnen, wobei m eine Instanz der Klasse Maze ist.
3.) Losen des Labyrinths durch Backtracking
DerWeg durch das Labyrinth soll mit Backtracking gefunden werden. Backtracking
ist eine einfache Problemlosungsmethode, welche alle moglichen Losungen durchprobiert.
Sehen Sie sich auch nochmal das Beispiel der 8 Damen aus der Ubung
dazu an! Die Losung wird schrittweise gesucht, d.h. man probiert zuerst nach rechts
zu gehen, dann nach oben, nach unten und schlielich nach links. Wenn man in
einer Sackgasse landet, muss man denWeg nicht weiter verfolgen.
Implementieren Sie nun eine Funktion searchMaze, welche als Parameter die Startkoordinaten
(x; y) und eine Instanz der Klasse m erhalt. Nachdem die Funktion
searchMaze erfolgreich abgelaufen ist, soll im Labyrinth in m der Weg mit Punkten
(wie oben im Beispiel) markiert sein. Geben Sie das Labyrinth nach jedem
Schritt aus um damit die Suche zu visualisieren.
4.) Beispiele
Setzen Sie nun die Funktion searchMaze und die Klasse Maze so ein, dass Sie Labyrinthe
wie oben besprochen losen konnen. Beispiele nden Sie auf der Webseite.
Achten Sie auch auf Sonder- und Fehlerfalle!

[Hyperion]

Also zunächst einmal lese ich da nichts von Rekursion! Insofern gibt es auch keinerlei Beschränkungen hinsichtlich von Rücksprüngen bei Sackgassen!

Hier mal die Ausgabe meiner Lösung (Die Webseite kennen wir ja nicht, daher starte ich immer bei (1, 1) und scanne nicht nach "S"):

Code: Alles auswählen

########
#      #
# ######
#      #
# ## ###
#  #  @#
########
[[6, 5], (5, 5), (4, 5), (4, 4), (4, 3), (3, 3), (2, 3), (1, 3), (1, 2), (1, 1)]

########
#o.....#
#o######
#oooo..#
# ##o###
#  #ooo#
########

Alle betretenden Felder sind mit einem "." markiert, zusätzlich wurde der Weg noch mit "o" am Schluss markiert.

Insofern sollte meine Lösung tun - auch wenn Rekursion hier nicht unbedingt sinnvoll ist. (Jetzt warte ich mal auf sma, der mir dafür einen reinwürgt und anschließend BlackJack oder Leonidas, die dem widersprechen )

[andi_wand]

Backtracking->Rekursion, so wurde mir das erklärt, und daran muss ich mich (leider) halten, sonst hätt ich hier schon zwei funktionsfähige Varianten...