Backtracking (Aus dem Labyrinth entkommen), Optimierung von Backtracking

[rb1994]

Könnte mir jemand bitte helfen?

In der vorherigen Übung waren die möglichen Routen immer nur ein Feld breit. Wenn die möglichen
Routen breiter werden, ist es z.B. möglich, Schlangenlinien zu laufen. Sofern das Labyrinth klein
genug ist, fällt dies nicht ins Gewicht. Wird das Labyrinth aber größer, steigt auch die Anzahl der
möglichen Wege und somit die Zeit, um diese zu testen.

Wie könnte man vermeiden, dass Teilrouten immer wieder
getestet werden?

Code des vorherigen Übung:

Code: Alles auswählen

import copy
import os
import time

emptyMarker = " "
escapeMarker = "E"
fillMarker = "."
        
def convertFileToField(filename):
    f = open(filename, "r")
    line = f.readline()
    fld = []
    while line:
        fld.append(list(line[:-1]))
        line = f.readline()
    f.close
    return fld

def printField(f):
    print()
    for i in range(0,len(f)):
        for n in range(0,len(f[0])):
            print (f[i][n],end='')
        print()

def isFree(r, c):
    if field[r][c] == emptyMarker or field[r][c] == escapeMarker:
        return True
    else:
        return False
            
def isEscape (r, c):
    if field[r][c] == escapeMarker:
        return True
    else:
        return False
    
def isInField(r, c):
    if r >= 0 and r < len(field) and c >= 0 and c < len(field):
        return True
    else:
        return False
    
def minWeg(route):
    minimum = len(route[0])
    short = route[0]
    for i in range(1, len(route)):
        if (len(route[i])<minimum):
            minimum = len(route[i])
            short = route[i]
    return short
    
def findEscape(r,c,route=()):
    route += ((r,c), )
    if isEscape(r,c):
        return route
    
    relativeN = ((0,1),(0,-1),(1,0),(-1,0))    
    escapeRoutes = []
    for rN in relativeN:
        nr = r+rN[0]
        nc = c+rN[1]
        if isInField(nr, nc) and isFree(nr, nc) and not (nr, nc) in route:
            tmp = findEscape(nr, nc, route)
            if len(tmp) > 0:
                escapeRoutes += [tmp]
            
    if len(escapeRoutes) == 0:
        return ();
    kuerzesteWeg = minWeg(escapeRoutes)
    return kuerzesteWeg


field = convertFileToField("field2.txt")
zeit1=time.clock()
route = findEscape(1,1)
zeit2 = time.clock()
for p in route[:-1]:
    field[p[0]][p[1]] = fillMarker
printField(field)
print("\nKoordinaten der kuerzesten Weg: ",route)
print("Zeit: ",zeit2-zeit1)

[Sirius3]

@rb1994: außer Deiner Hausaufgabe hast Du nichts gepostet? Hast Du auch eine konkrete Frage?

Zum Code: die Namensschreibweise hält sich nicht an die Konventionen, die in PEP8 beschrieben sind. Konstanten werden komplett in GROSSBUCHSTABEN geschrieben, also EMPTY_MARKER. Variablen und Funktion klein_mit_unterstrich, also convert_file_to_field.

Statt der while-Schleife in convertFiletoField sollte man eine for-Schleife nehmen, close sollte man auch aufrufen f.close(). Unnötige Abkürzungen sollte man vermeiden: fld->field

Code: Alles auswählen

def convert_file_to_field(filename):
    field = []
    with open(filename, "r") as lines:
        for line in lines:
            field.append(list(line[:-1]))
    return field

In printField sollte man nicht über den Index iterieren, sondern direkt über die Elemente der Listen:

Code: Alles auswählen

def print_field(field):
    print()
    for row in field:
        for cell in row:
            print(cell, end='')
        print()

In isFree kann man gleich das Ergebnis des Vergleichs ohne if zurückgeben. field sollte als Argument mit übergeben werden und nicht magisch von außen kommen:

Code: Alles auswählen

def is_free(field, row, column):
    return field[row][column] in [emptyMarker, escapeMarker]

Die Anmerkungen kannst Du auf die restlichen Funktionen als Übung übertragen.

Alle Zeilen ab Zeile 74 sollten in einer Funktion stehen, die üblicherweise main heißt. Dadurch werden die globalen Variablen (field) zu lokalen, und solche Fehler wie bei isFree, dass man vergisst field als Parameter zu übergeben, werden gleich mit einer Fehlermeldung quitiert.

[__deets__]

@Sirius3 die Frage war recht deutlich - wie verkleinert er den Suchraum.

@rb1994: eine Moeglichkeit ist das Labyrinth sukzessive zu verkleinern, ohne seine Freiheitsgrade zu beschraenken. Wenn man sich mal einen Raum aufmalt auf Kaestchenpapier, und den dann von den Waenden her so verkleinert, dass man nur noch einen Weg mit entsprechend vielen Kreuzungen hat, dann kommt man da auf zwei einfache Kriterien, wo man ein Kaestchen plazieren kann, ohne das man das Labyrinth beschraenkt. Das muss man dann fuer sich genommen so lange anwenden, bis es keine Veraenderung mehr gibt, man also ein Labyrinth mit minimalem Freiraum hat - und das benutzt man dann zur Suche.