backtracking

BACKTRACKING

 

 

STRATEGIE IM IRRGARTEN

 

Der Alien soll den Ausgang aus dem Irrgarten finden. Diese Aufgabe lässt sich mit einem Backtracking-Algorithmus lösen.

Du verwendest hier nur ein kleines Zufallslabyrinth mit 11x11 Zellen. Das Labyrinth erzeugst du mit der Klasse Maze, die im WebTigerPython vorhanden ist. Es entsteht jedes Mal ein anderes zufälliges Labyrinth mit einem Eingang oben an der linken und einem Ausgang unten an der rechten Seite.

Mit isWall(loc) kannst du testen, ob sich an der Location loc eine Wandzelle befindet.

 

In deinem Programm ermittelst du die Nachbarknoten so, dass du von den 4 angrenzenden Zellen diejenigen auswählst, die nicht auf der Wand und nicht ausserhalb des Gitters liegen.

Programm: 

#Labyrinth.py
from gamegrid import *

def createMaze():
    global maze
    maze = GGMaze(11, 11)
    for x in range(11):
        for y in range(11):
            loc = Location(x, y)
            if maze.isWall(loc):
                getBg().fillCell(loc, Color(0, 50, 0))
            else:    
                getBg().fillCell(loc, Color(255, 228, 196))
    refresh()

def getNeighbours(node):
    neighbours = []
    for loc in node.getNeighbourLocations(0.5):
        if isInGrid(loc) and not maze.isWall(loc):
           neighbours.append(loc)
    return neighbours
    
def search(node):
    global targetFound, manual
    if targetFound:
        return
    visited.append(node)  # push
    alien.setLocation(node)
    refresh()
    delay(500)    

    # Check for termination
    if node == exitLocation:
        targetFound = True
        
    for neighbour in getNeighbours(node):
        if neighbour not in visited:
            backSteps = [node]
            backStepsList.append(backSteps)
            backSteps.append(neighbour)
            search(neighbour) # recursive call
            backSteps.reverse()
            if not targetFound:
                for loc in backSteps[1:]:
                    setTitle("Must go back...")
                    alien.setLocation(loc)
                    refresh()
                    delay(500)
                if manual:    
                    setTitle("Went back...")
                else:
                    setTitle("Went back. Find target...")
            backStepsList.pop()
    visited.pop() # pop

manual = True
targetFound = False
visited = []
backStepsList = []
makeGameGrid(11, 11, 40, False)
setTitle("Labyrinth")
show()
createMaze()
startLocation = maze.getStartLocation()
exitLocation = maze.getExitLocation()
alien = Actor("sprites/alieng.png")
addActor(alien, startLocation)
search(startLocation)
setTitle("Target found")
► In Zwischenablage kopieren

 

 

MERKE DIR...
 

Es ist interessant, die Lösungsstrategie des Menschen mit der des Computers zu vergleichen. Ein menschlicher Spieler erkennt auf einem Blick die Gesamtsituation und leitet daraus eine Strategie ab, wie er möglichst schnell zum Ausgang gelangt. Er handelt dabei mit einer für Menschen typischen globalen Übersicht, die deinem Computerprogramm fehlt. Dieses erfasst die momentane Situation nur lokal, "erinnert" sich aber dafür sehr genau an die bereits durchlaufenen Wege und durchsucht sehr systematisch neue Wege zum Ziel.

Die Situation ändert sich aber zu Gunsten des Computers, wenn man dem menschlichen Menschen die globale Übersicht vorenthält, z.B. wenn er sich selbst im Innern des Labyrinths befindet, oder wenn man die Anzahl Zellen wesentlich vergrössert.

 

 

8-DAMEN-PROBLEM
 

Auf einem Schachbrett mit 8x8-Feldern sollen 8 Damen so platziert werden, dass sie sich gemäss den Schachregeln gegenseitig nicht angreifen (Eine Dame kann sich horizontal, vertikal, sowie auf den Diagonalen bewegen).

Das Damenproblem gilt als Musterbeispiel für das Backtracking. Dabei setzt man Zug um Zug eine Dame nach der anderen derart auf das Brett, dass die neue Dame nicht in Konflikt mit den bereits vorhandenen gerät. Ist das Setzten einer weiteren Dame nicht möglich, wird die zuletzt gesetzte Dame an eine neue Position verschoben. Falls nötig, wird auch die zweitletzte Dame neu gesetzt usw.

  

Dein Algorithmus bricht ab, wenn er die erste Lösung gefunden hat (es gibt 92 verschiedene Lösungen). Je nach Leistung des Rechners (bzw. des Web Editors) musst du einige Sekunden bis einige Minuten warten, bis eine Lösung gefunden wird.

Programm:

#Quenns.py
from gamegrid import *

n = 8 # number of queens

def getNeighbours(node):
    squares = [] # list of occupied squares
    for i in range(n):
        if node[i] != -1:
           squares.append(Location(node[i], i))

    forbidden = [] # list of forbidden squares
    for location in squares:
        a = location.x 
        b = location.y
        for x in range(n):
            forbidden.append(Location(x, b))  # same row
        for y in range(n):
            forbidden.append(Location(a, y))  # same column
        for loc in getDiagonalLocations(location, True):#diagonal up
            forbidden.append(loc)
        for loc in getDiagonalLocations(location, False):#diagonal down
            forbidden.append(loc)

    allowed = [] # list of all allowed squares = all - forbidden
    for i in range(n):
        for k in range(n):
            loc = Location(i, k)
            if not loc in forbidden:
                allowed.append(loc)

    neighbourNodes = [] 
    for loc in allowed:
        neighbourNode = node[:]
        i = loc.y # row
        k = loc.x # col
        neighbourNode[i] = k 
        neighbourNodes.append(neighbourNode)
    return neighbourNodes        

def search(node):
    global found
    if found or isDisposed(): 
        return
    visited.append(node)  # node marked as visited

    # Check for solution
    if not -1 in node: 
        found = True
        drawNode(node)
        
    for s in getNeighbours(node):
        search(s)
    visited.pop()

def drawBoard():
    for i in range(n):
        for k in range(n):
            if (i + k) % 2 == 0:
                getBg().fillCell(Location(i, k), Color.white)

def drawNode(node):
    removeAllActors()
    for i in range(n):
        addActorNoRefresh(Actor("sprites/chesswhite_1.png"),
                   Location(node[i],i))
    refresh()

makeGameGrid(n, n, 600 // n, False)
setBgColor(Color.darkGray)
drawBoard()
show()
setTitle("Searching. Please wait..." )

visited = []
found = False
startNode = [-1] * n  # all squares empty
search(startNode)
setTitle("Search complete. ")
► In Zwischenablage kopieren