文章目录

一、实验内容二、深度优先搜索和广度优先搜索总结1.深度优先搜索算法2.广度优先搜索算法三、实验代码和用于测试的迷宫1.实验代码2.测试迷宫2.1 maze1.txt2.2 maze2.txt2.3 maze3.txt四、实验结果1. maze1.txt2. maze2.txt3. maze3.txt五、结果分析总结

一、实验内容

下载mymaze.py文件maze1.txt,maze2.txt,maze3.txt以及requirements.txt几个文件，将它们放于同一个文件夹中，安装相应的环境定义。读懂文件中所给的类和函数，请按照mymaze.py中的提示,补全代码,执行深度优先搜索和广度优先搜索的代码并对结果进行记录。

二、深度优先搜索和广度优先搜索总结

1.深度优先搜索算法

总是先扩展frontier表中最深的结点Frontier是一个栈结构——后进先出

2.广度优先搜索算法

总是先扩展frontier表中最浅的结点Frontier是一个队列结构——先进先出

三、实验代码和用于测试的迷宫

1.实验代码

#!/usr/bin/python# -*- coding:utf-8 -*-class Node():def __init__(self, state, parent, action):self.state = stateself.parent = parentself.action = actionclass StackFrontier():def __init__(self):self.frontier = []def add(self, node):self.frontier.append(node)def contains_state(self, state):return any(node.state == state for node in self.frontier)def empty(self):return len(self.frontier) == 0def remove(self):if self.empty():raise Exception("empty frontier")else:#please add your code here to get a node from the frontier, according to FIBO#请在下面添加你的代码，从frontier表中按照后进先出的顺序移除一个结点，并将移除的结点给nodenode = self.frontier[-1]#after remove a node ,your frontier should adaptive accordingly#在移除了一个结点后，你的frontier表应该相应的更新del self.frontier[-1]return nodeclass QueueFrontier(StackFrontier):def remove(self):if self.empty():raise Exception("empty frontier")else:#请添加你的代码，按照先进先出的顺序移除结点node = self.frontier[0]#请更新frontier表，使得frontier表为移除了一个结点剩下的结点组成del self.frontier[0]return nodeclass Maze():def __init__(self, filename):# Read file and set height and width of mazewith open(filename) as f:contents = f.read()# Validate start and goalif contents.count("A") != 1:raise Exception("maze must have exactly one start point")if contents.count("B") != 1:raise Exception("maze must have exactly one goal")# Determine height and width of mazecontents = contents.splitlines()self.height = len(contents)self.width = max(len(line) for line in contents)# Keep track of wallsself.walls = []for i in range(self.height):row = []for j in range(self.width):try:if contents[i][j] == "A":self.start = (i, j)row.append(False)elif contents[i][j] == "B":self.goal = (i, j)row.append(False)elif contents[i][j] == " ":row.append(False)else:row.append(True)except IndexError:row.append(False)self.walls.append(row)self.solution = Nonedef print(self):solution = self.solution[1] if self.solution is not None else Noneprint()for i, row in enumerate(self.walls):for j, col in enumerate(row):if col:print("#", end="")elif (i, j) == self.start:print("A", end="")elif (i, j) == self.goal:print("B", end="")elif solution is not None and (i, j) in solution:print("*", end="")else:print(" ", end="")print()print()def neighbors(self, state):row, col = statecandidates = [("up", (row - 1, col)),("down", (row + 1, col)),("left", (row, col - 1)),("right", (row, col + 1))]result = []for action, (r, c) in candidates:if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:result.append((action, (r, c)))return resultdef solve(self):"""Finds a solution to maze, if one exists."""# Keep track of number of states exploredself.num_explored = 0# Initialize frontier to just the starting positionstart = Node(state=self.start, parent=None, action=None)#please add the frontier of stackfroniter or queuefrontier#请声明栈结构或者队列的frontier实例"""每一次都改的地方！！！"""frontier = QueueFrontier()#frontier = StackFrontier()frontier.add(start)# Initialize an empty explored setself.explored = set()# Keep looping until solution foundwhile True:# If nothing left in frontier, then no pathif frontier.empty():raise Exception("no solution")# Choose a node from the frontier,please finish the sentencenode = frontier.remove()self.num_explored += 1# If node is the goal, then we have a solutionif node.state == self.goal:actions = []cells = []while node.parent is not None:actions.append(node.action)cells.append(node.state)node = node.parentactions.reverse()cells.reverse()self.solution = (actions, cells)return# Mark node as exploredself.explored.add(node.state)# Add neighbors to frontierfor action, state in self.neighbors(node.state):if not frontier.contains_state(state) and state not in self.explored:child = Node(state=state, parent=node, action=action)frontier.add(child)def output_image(self, filename, show_solution=True, show_explored=False):from PIL import Image, ImageDrawcell_size = 50cell_border = 2# Create a blank canvasimg = Image.new("RGBA",(self.width * cell_size, self.height * cell_size),"black")draw = ImageDraw.Draw(img)solution = self.solution[1] if self.solution is not None else Nonefor i, row in enumerate(self.walls):for j, col in enumerate(row):# Wallsif col:fill = (40, 40, 40)# Startelif (i, j) == self.start:fill = (255, 0, 0)# Goalelif (i, j) == self.goal:fill = (0, 171, 28)# Solutionelif solution is not None and show_solution and (i, j) in solution:fill = (220, 235, 113)# Exploredelif solution is not None and show_explored and (i, j) in self.explored:fill = (212, 97, 85)# Empty cellelse:fill = (237, 240, 252)# Draw celldraw.rectangle(([(j * cell_size + cell_border, i * cell_size + cell_border),((j + 1) * cell_size - cell_border, (i + 1) * cell_size - cell_border)]),fill=fill)img.save(filename)"""if len(sys.argv) != 2:sys.exit("Usage: python maze.py maze.txt")"""m = Maze("maze3.txt")print("Maze:")m.print()print("Solving...")m.solve()print("States Explored:", m.num_explored)print("Solution:")m.print()m.output_image("maze3_广度优先.png", show_explored=True)

2.测试迷宫

2.1 maze1.txt

#####B###### ##### ##### ####A######

2.2 maze2.txt

### ########## ################### # ## ##### # # ## ################### # # # ## # # # ###################### # # # ## ### # # ## # ## ### ## ######### # # ## # # ##B# # # ## # ## ################ # # #### ## #### # # #### ############## ## # # # #### ## # # # ####### ######## ####### # # ####### #### # #A######################

2.3 maze3.txt

## ### ## ##B # ## ## ####A######

四、实验结果

下图中黑色格子代表迷宫中的墙，深红色代表起点，深绿色代表终点，浅红色代表走过的错路，浅绿色代表走到正确的路线。

1. maze1.txt

深度优先算法结果

广度优先算法结果

2. maze2.txt

深度优先算法结果

广度优先算法结果

3. maze3.txt

深度优先算法结果

广度优先算法结果

五、结果分析

从完备性角度上分析：深度优先搜索和广度优先搜索都可以找到解。从最优性角度上分析：深度优先搜索不一定能找到最优解，而广度优先搜索可以找到最优解。从时间复杂度角度上分析：深度优先搜索跑了更多的结点所以它的时间复杂度比广度优先搜索高。从空间复杂度角度上分析：广度优先搜索在找到最终结点之前需要记录所有已经走过的结点，所以空间复杂度要高一些。

总结

算法引自——人工智能 一种现代的方法（第3版）

代码源自网络，仅用于教学实验

本文来源于实验报告

如果觉得《迷宫问题 深度优先搜索 广度优先搜索 宽度优先搜索【python】》对你有帮助，请点赞、收藏，并留下你的观点哦！