backtracking am labyrinth
Verfasst: Mittwoch 4. Januar 2006, 11:46
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.
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
erklärt sich ja selbst
markiert einen gegangenen Weg mit x und hängt die Koordinate an weg = [], bzw demarkiert, und löscht koordinate aus weg = []
prüft wieviele Wege vom aktuellen standpunkt aus möglich sind.
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.
der hauptteil des Programms sieht so aus:
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.
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]]
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]
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))
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
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
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
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.