Seite 1 von 1

backtracking am labyrinth

Verfasst: Mittwoch 4. Januar 2006, 11:46
von JROppenheimer
Schalom und frohes neues, euch allen.

Im Vergleich komm ich mir immer ein bisschen blöd vor, weil meine Fragen im Vergleich zu denen der anderen immer ein bisschen dämlich wirken...

ich bastele gerade an dem Labyrinthproblem, das ich per Backtracking lösen soll ....

Ich bin schon soweit, dass der Drecksack das Ziel findet und die schritte als KoordinatenTupel in eine Liste schreibt.

Code: Alles auswählen

lab=[[1,1,1,1,1,1,1,1,1,1,1,1],
        [1,2,1,0,0,0,1,0,0,0,0,1],
        [1,0,0,0,1,1,1,1,1,0,1,1],
        [1,0,1,0,0,0,1,0,0,0,1,1],
        [1,0,1,1,1,0,1,0,1,0,1,1],
        [1,0,0,0,1,0,0,0,1,0,1,1],
        [1,1,1,1,1,0,1,0,1,0,0,1],
        [1,0,1,0,1,0,1,1,1,1,0,1],
        [1,0,1,0,0,0,1,0,0,0,0,1],
        [1,0,1,0,1,1,1,0,1,1,1,1],
        [1,0,0,0,0,0,1,0,0,0,3,1],
        [1,1,1,1,1,1,1,1,1,1,1,1]]
1 ist ne Wand
0 ist ein Weg
2 ist Start
3 ist Ziel

um das ein bisschen besser optisch verfolgen zu können, hab ichs umgewandelt, so dass
'#' ist ne Wand
' ' ist ein Weg
'S' Start
'Z' Ziel

Code: Alles auswählen

for i in range(len(lab)):
    for j in range(len(lab[0])):
        if lab[i][j] == 1:
            lab[i][j] = '#'
        elif lab[i][j] == 0:
            lab[i][j] = ' '
        elif lab[i][j] == 2:
            lab[i][j] = 'S'
        elif lab[i][j] == 3:
            lab[i][j] = 'Z'

Code: Alles auswählen

def print_lab(lab):
    for i in range(len(lab)):
        print lab[i]
erklärt sich ja selbst

Code: Alles auswählen

def markieren(zeile, spalte):
    lab[zeile][spalte] = 'x'
    weg.append((zeile, spalte))
def unmarkieren(zeile, spalte):
    lab[zeile][spalte] = ' '
    weg.remove((zeile, spalte))
markiert einen gegangenen Weg mit x und hängt die Koordinate an weg = [], bzw demarkiert, und löscht koordinate aus weg = []

Code: Alles auswählen

def noway(zeile, spalte):
    ways = 0
    if lab[zeile+1][spalte] is not '#':
        ways += 1
    if lab[zeile][spalte+1] is not '#':
        ways += 1
    if lab[zeile-1][spalte] is not '#':
        ways += 1
    if lab[zeile][spalte-1] is not '#':
        ways += 1
    print 'Von hier aus ',ways,' Wege...'
    return ways
prüft wieviele Wege vom aktuellen standpunkt aus möglich sind.

Code: Alles auswählen

def ziel(lab, zeile, spalte):
    if lab[zeile+1][spalte] is 'Z':
        print 'das ziel ist nach unten'
        ende = True
        return True
    if lab[zeile][spalte+1] is 'Z':
        print 'das ziel ist nach rechts'
        ende = True
        return True
    if lab[zeile-1][spalte] is 'Z':
        print 'das ziel ist nach oben'
        ende = True
        return True
    if lab[zeile][spalte-1] is 'Z':
        print 'das ziel ist nach links'
        ende = True
        return True
    else:
        return False
prüft, ob im nächsten Schritt das Ziel erreicht wird, und an DIESER Stelle sollte er eigndlich aufhören .... also wenn das Ziel erreicht wird.

Code: Alles auswählen

def ausgang_gefunden():
    print 'AUSGANG ERREICHT!'
    x = raw_input('to end press enter')
    print ''
    print ''
    print_lab(lab)
    print 'Weg: '
    for i in weg:
        print i,
    print '--------------------------------------------------------'
    return weg

der hauptteil des Programms sieht so aus:

Code: Alles auswählen

weg = []
richtigerWeg = []
ende = False
def weg_finden(lab, zeile, spalte):
    markieren(zeile, spalte)
        
    print ''
    print_lab(lab)
    if ziel(lab, zeile, spalte) == True:
        ausgang_gefunden()
    else:
        if lab[zeile+1][spalte] is ' ':
            print 'ich gehe nach unten'
            weg_finden(lab, zeile+1, spalte)
        if lab[zeile][spalte+1] is ' ':
            print 'ich gehe nach rechts'
            weg_finden(lab, zeile, spalte+1)
        if lab[zeile-1][spalte] is ' ':
            print 'ich gehe hoch'
            weg_finden(lab, zeile-1, spalte)
        if lab[zeile][spalte-1] is ' ':
            print 'ich gehe nach links'
            weg_finden(lab, zeile, spalte-1)
    if ende is not True:
        unmarkieren(zeile, spalte)
    return richtigerWeg

aufgerufen wird das ganze mit:

weg_finden(lab, 1, 1) <- in diesem Fall 1, 1 weil der Startpunkt bei (1,1) liegt. aber das programm soll auf beliebige Labyrinthe anwendbar sein.

Mein Problem ist jetzt, dass der zwar den Weg findet, und auch schön markiert und in die weg-Liste schreibt, aber wenn der am Ziel ist, soll der gleich aufhören und net erst noch die ganzen anderen Rekursionsschritte fertig machen. Das hat nämlich zur Folge, dass der meine weg-Variable wieder platt macht .....

ich bin für jegliche Art von Kritik offen, nur raus damit, ich bin ein programmierNeuling, deshalb dankbar für Hilfe und Anregungen...

liebe Grüße J.R.

Verfasst: Mittwoch 4. Januar 2006, 23:13
von JROppenheimer.
noch keine Antwort .... schwach!

ich hab das Problem jetzt gefunden. es lag nur an einer variablen, die global definiert war, in einer funktion dann geändert wurde, aber nur lokal ....

ein einfaches

Code: Alles auswählen

global
hat das Problem gelöst

Gruß JR

Re: backtracking am labyrinth

Verfasst: Mittwoch 4. Januar 2006, 23:18
von BlackJack
JROppenheimer hat geschrieben: um das ein bisschen besser optisch verfolgen zu können, hab ichs umgewandelt, so dass
'#' ist ne Wand
' ' ist ein Weg
'S' Start
'Z' Ziel

Code: Alles auswählen

for i in range(len(lab)):
    for j in range(len(lab[0])):
        if lab[i][j] == 1:
            lab[i][j] = '#'
        elif lab[i][j] == 0:
            lab[i][j] = ' '
        elif lab[i][j] == 2:
            lab[i][j] = 'S'
        elif lab[i][j] == 3:
            lab[i][j] = 'Z'
Anstelle der vielen ``elif`` Abfragen kannst Du die Werte des Labyrinths auch als Index in eine Zeichenkette benutzen, die an Stelle 0 ein Leerzeichen hat, an Stelle 1 ein '#' usw.

Wenn Du nicht das originale Labyrinth benutzt, sondern ein neues aus dem alten erstellst, dann könnte man das auch so schreiben (ungetestet):

Code: Alles auswählen

def convert_labyrinth(labyrinth):
    def convert_cell(cell):
        return ' #SZ'[cell]
    
    def convert_row(row):
        return map(convert_cell, row)
    
    return map(convert_row, labyrinth)

Code: Alles auswählen

def print_lab(lab):
    for i in range(len(lab)):
        print lab[i]
erklärt sich ja selbst
Etwas 'pythonischer' wäre es nicht mit den Indexen zu arbeiten sondern gleich über das `lab` zu itereren:

Code: Alles auswählen

def print_lab(lab):
    for row in lab:
        print row

Code: Alles auswählen

def noway(zeile, spalte):
    ways = 0
    if lab[zeile+1][spalte] is not '#':
        ways += 1
    if lab[zeile][spalte+1] is not '#':
        ways += 1
    if lab[zeile-1][spalte] is not '#':
        ways += 1
    if lab[zeile][spalte-1] is not '#':
        ways += 1
    print 'Von hier aus ',ways,' Wege...'
    return ways
prüft wieviele Wege vom aktuellen standpunkt aus möglich sind.
``is not`` ist keine gute Idee, das ist nur Zufall das das funktioniert. ``is`` prüft auf Objektidentität und nicht nur auf Wertegleichheit. Das alle '#'-Zeichen hier auch das selbe Objekt sind, ist eine Optimierung des Interpreters, die aber von Python nicht garantiert wird. Also besser ``!=`` nehmen.

Code: Alles auswählen

def ziel(lab, zeile, spalte):
    if lab[zeile+1][spalte] is 'Z':
        print 'das ziel ist nach unten'
        ende = True
        return True
    if lab[zeile][spalte+1] is 'Z':
        print 'das ziel ist nach rechts'
        ende = True
        return True
    if lab[zeile-1][spalte] is 'Z':
        print 'das ziel ist nach oben'
        ende = True
        return True
    if lab[zeile][spalte-1] is 'Z':
        print 'das ziel ist nach links'
        ende = True
        return True
    else:
        return False
prüft, ob im nächsten Schritt das Ziel erreicht wird, und an DIESER Stelle sollte er eigndlich aufhören .... also wenn das Ziel erreicht wird.
An der Stelle gibt's drei einfache Möglichkeiten.

1. Bei jedem rekursiven Aufruf am Anfang auf `ende` prüfen und falls das wahr ist einfach sofort mit `True` zurückkehren. Dann wird zwar noch ein Teil der Rekursion abgelaufen, das Ergebnis aber nicht mehr verändert.

2. Das Ergebnis kopieren, wenn das Ziel erreicht ist. Dann macht es auch nichts, wenn weitergesucht wird. Man kann das Ergebnis an eine Liste anhängen und dann weitersuchen und so alle Wege finden, falls es mehrere gibt.

3. Aus den rekursiven Aufrufen mit einer Ausnahme aussteigen.

Verfasst: Donnerstag 5. Januar 2006, 13:24
von JROppenheimer
erstmal danke für die netten tips. dachte schon, das kommt nix mehr :D

diese ganze noway-funktion kann weggelassen werden. ich hab gemerkt, dass ich dir gar nich benutze :D - passiert den besten...

das mit dem auf "ende" prüfen hat ja die ganze Zeit nicht funktioniert aus dem einfachen Grund, dass ich ende global definiert habe, und der mir dann noch ein lokales "ende" in der funktion ziel erstellt hat. deswegen ein einfaches "global ende" am anfang von ziel() und schon hat der ganze käse gemacht, was er sollte *freu.

hab ich aber auch erst rausgefunden, nachdem ich jede funktion einzeln getestet habe .....