深度优先搜索算法在迷宫中跳过空格？

Question

在 edX 上结束了哈佛人工智能课程的第一讲后，我决定将所教授的概念付诸实践，首先是深度优先搜索算法。

本程序objective是在文本文件mazefile中输入一个迷宫，使用深度优先搜索算法找到从S到G的路径.

项目目前包含4个文件，（1）代码用class方法操作或使用（2）包含迷宫的文本文件，（3）包含迷宫的文本文件结果文件（AI 探索过的地方）和主要 python 脚本 (4)。它们就在这里，随时将它们复制并粘贴到一个文件夹中，看看它们如何运行。

processText.py（文件 1）

#code to process the mazefile file.

class importMaze:
    def __init__(self,maze):
        self.fileLines = []
        self.fileName = maze
        self.switch = False
        self.toBeReturned = []
    def processThis(self):
        f = open(self.fileName,"r")
        for x in f:
            self.fileLines.append(x[:-1])
        f.close()
        for i in self.fileLines:
            if self.switch == True:
                if str(i) == "END":
                    self.switch = False
                else:
                    self.toBeReturned.append(i)
            else:
                if str(i) == "START":
                    self.switch = True
        return self.toBeReturned
class mazePointer:
    def __init__(self,mazearray):
        self.Sample = mazearray
        self.initialPosition = []
        for y in range(0, len(self.Sample)):
           for x in range(0,len(self.Sample[y])):
               if str(self.Sample[y][x]) == "S":
                    self.initialPosition = [x,y]
        self.currentPosition = self.initialPosition
    def whatIs(self,xcoordinate,ycoordinate):
        return (self.Sample[ycoordinate])[xcoordinate]
    def nearbyFreeSpaces(self,search):
        self.freeSpaces = []
        if self.whatIs(self.currentPosition[0]-1,self.currentPosition[1]) == search:
            self.freeSpaces.append([self.currentPosition[0]-1,self.currentPosition[1]])
        if self.whatIs(self.currentPosition[0]+1,self.currentPosition[1]) == search:
            self.freeSpaces.append([self.currentPosition[0]+1,self.currentPosition[1]])
        if self.whatIs(self.currentPosition[0],self.currentPosition[1]-1) == search:
            self.freeSpaces.append([self.currentPosition[0],self.currentPosition[1]-1])
        if self.whatIs(self.currentPosition[1],self.currentPosition[1]+1) == search:
            self.freeSpaces.append([self.currentPosition[1],self.currentPosition[1]+1])
        return self.freeSpaces

    def moveTo(self,position):
        self.currentPosition = position

TestingTrack.py（主文件）

from processText import importMaze, mazePointer

testObject = importMaze("mazefile")
environment = testObject.processThis()
finger = mazePointer(environment)
frontier = []
explored = []
result = ""
def Search():
    global  result
    if len(finger.nearbyFreeSpaces("G")) == 1: #If the goal is bordering this space
        result = finger.nearbyFreeSpaces("G")[0]
        explored.append(finger.currentPosition)
    else:
        newPlaces = finger.nearbyFreeSpaces("F") #finds the free spaces bordering
        for i in newPlaces:
            if i in explored: #Skips the ones already visited
                pass
            else:
                frontier.append(i)

while result == "":
    explored.append(finger.currentPosition)
    Search()
    finger.moveTo(frontier[-1])
    frontier.pop(-1)


exploredArray = []
for y in range(len(environment)): #Recreates the maze, fills in 'E' in where the AI has visited.
    holder = ""
    for x in range(len(environment[y])):
        if [x,y] in explored:
            holder+= "E"
        else:
            holder+= str(environment[y][x])
    exploredArray.append(holder)
def createResult(mazeList,title,append): #Creating the file
    file = open("resultfile",append)
    string = title + " \n F - Free \n O - Occupied \n S - Starting point \n G - Goal \n E - Explored/Visited \n (Abdulaziz Albastaki 2020) \n \n (top left coordinate - 0,0) \n "
    for i in exploredArray:
        string+= "\n" + str(i)
    string+= "\n \n Original problem \n"
    for i in environment:
        string+= "\n" +str(i)
    file.write(string)
    file.close()
def tracingPath():
    initialExplored = explored
    proceed = True
    newExplored = []
    for i in explored:
        finger.moveTo() #incomplete
print(explored)
createResult(exploredArray,"DEPTH FIRST SEARCH", "w")

mazefile（程序会读取这个文件得到迷宫）

F - Free
O - Occupied
S - Starting point
G - Goal
(Abdulaziz Albastaki 2020)

START
OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OSFFFFFFFFFFFFFO
OOOOOOOOOOOOOOOO
END



Made by Abdulaziz Albastaki in October 2020
You can change the maze and its size however it must
-Respect the key above
-Have ONE Starting point and goal
-The maze must be in between 'START' and 'END'
-The maze MUST be surrounded by occupied space


SAMPLE PROBLEMS:

OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OSFFFFFFFFFFFFFO
OOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOO
OFOFFFFFOOOFFFOOO
OFFFOOOFOOFFOOOFO
OFOOOOOFOOFOOOOFO
OSFGFFFFFFFFFFFFO
OOOOOOOOOOOOOOOOO

还有一个结果文件，但是如果您只是创建一个具有该名称（无扩展名）的空文本文件，程序将用结果填充它。

问题出在结果文件上，这里是：

DEPTH FIRST SEARCH 
 F - Free 
 O - Occupied 
 S - Starting point 
 G - Goal 
 E - Explored/Visited 
 (Abdulaziz Albastaki 2020) 
 
 (top left coordinate - 0,0) 
 
OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOEO
OFOOOOOOOOOOOOEO
OFOOOOOOOOOOOOEO
OEOOOOOOOOOOOOEO
OEFFFEEEEEEEEEEO
OOOOOOOOOOOOOOOO
 
 Original problem 

OOOOOOOOOOOOOOOO
OFFFFFFFFFFFFFGO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OFOOOOOOOOOOOOFO
OSFFFFFFFFFFFFFO
OOOOOOOOOOOOOOOO

AI 在到达目标时跳过了几个空格，为什么会这样？

如有任何疑问，请随时询问我。

Answer 1

存在以下问题：

nearbyFreeSpaces 中的最后一个 if 块使用了错误的索引：

if self.whatIs(self.currentPosition[1],self.currentPosition[1]+1) == search:
    self.freeSpaces.append([self.currentPosition[1],self.currentPosition[1]+1])

应该是：

if self.whatIs(self.currentPosition[0],self.currentPosition[1]+1) == search:
    self.freeSpaces.append([self.currentPosition[0],self.currentPosition[1]+1])

最终位置没有正确添加到路径中。该块的最后一行：

if len(finger.nearbyFreeSpaces("G")) == 1: #If the goal is bordering this space
    result = finger.nearbyFreeSpaces("G")[0]
    explored.append(finger.currentPosition)

...应该是：

    explored.append(result)

深度优先搜索算法在迷宫中跳过空格？

Depth first search algorithm skipping spaces in maze?

python

algorithm

search

artificial-intelligence

depth-first-search