在完成哈佛大学edX平台上的AI课程的第一讲后，我决定实施所教授的概念，首先是深度优先搜索算法。

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

该项目目前包括4个文件，（1）包含类方法的代码，用于操作或使用（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.toBeReturnedclass 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, mazePointertestObject = 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() #incompleteprint(explored)createResult(exploredArray,"DEPTH FIRST SEARCH", "w")

mazefile（程序将读取此文件以获取迷宫）

F - FreeO - OccupiedS - Starting pointG - Goal(Abdulaziz Albastaki 2020)STARTOOOOOOOOOOOOOOOOOFFFFFFFFFFFFFGOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOSFFFFFFFFFFFFFOOOOOOOOOOOOOOOOOENDMade by Abdulaziz Albastaki in October 2020You 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 spaceSAMPLE PROBLEMS:OOOOOOOOOOOOOOOOOFFFFFFFFFFFFFGOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOSFFFFFFFFFFFFFOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOFOFFFFFOOOFFFOOOOFFFOOOFOOFFOOOFOOFOOOOOFOOFOOOOFOOSFGFFFFFFFFFFFFOOOOOOOOOOOOOOOOOO

还有一个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)  OOOOOOOOOOOOOOOOOFFFFFFFFFFFFFGOOFOOOOOOOOOOOOEOOFOOOOOOOOOOOOEOOFOOOOOOOOOOOOEOOEOOOOOOOOOOOOEOOEFFFEEEEEEEEEEOOOOOOOOOOOOOOOOO  Original problem OOOOOOOOOOOOOOOOOFFFFFFFFFFFFFGOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOFOOOOOOOOOOOOFOOSFFFFFFFFFFFFFOOOOOOOOOOOOOOOOO

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

欢迎随时向我询问任何需要澄清的地方。

回答：

存在以下问题：

• 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)