深度优先搜索算法跳过迷宫中的空间？

Question

在结束哈佛大学人工智能课程关于edX的第一堂课后，我决定实施所教授的概念，首先是深度优先搜索算法

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

该项目目前由4个文件组成，（1）带有类方法的代码，用于操作或使用（2）包含迷宫的文本文件，另一个包含结果文件（AI已经探索过的地方）的文本文件（3）和主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

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

问题在于resultfile，如下所示：

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

人工智能跳过了一些空间来达到目标，为什么会这样

请随时问我任何澄清

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)