实验二盲目搜索

系统教程810 更新时间：2026-04-04 16:45:57

2023年12月11日发(作者：)

实验二搜索问题形式化和无信息搜索

（2学时）

一实验目的

熟悉和掌握搜索问题形式化方法与步骤，使用Python语言实现搜索问题形式化；掌握基本无信息搜索算法，实现算法并验证。

二实验原理

搜索问题形式化即把要解决的问题描述为搜索问题，主要包括确定状态空间，初始状态，后继函数，目标测试及耗散等5方面内容；对于搜索问题可以应用通用的搜索算法求解，主要包括无信息(盲目)搜索和有信息搜索两大类，基本的无信息搜索有广度优先搜索和深度优先搜索。

三实验条件

1 Python解释器，及IDLE等程序开发调试环境。

2 本实验所提供的几个Python文件，包括:

用于构造、编辑、显示迷宫问题，以及对迷宫进行简单搜索；

编写搜索算法代码。实验要求的所有搜索Agent将通过改写本文件中类SearchAgent的solve方法来实现；

实现搜索算法可能使用到的一些数据结构；

用于构造、编辑、显示8数码问题；

迷宫文本文件。

四实验内容

1 搜索问题形式化

2 广度优先搜索

3 深度优先搜索

五实验步骤

1 建立文件夹，将实验提供的4个Python文件和3个文本文件拷到文件夹中，注意整个文件夹路径不能有中文字符

2 构造、编辑、显示迷宫问题

运行Python IDLE，在>>>提示符下输入

import mazeworld

此时会出现错误提示，分析为什么出错

#之所以会出现错误，是因为在sys的导入路径（path）中没有文件的路径，这是用户自定

#义的的路径，需要手工导入，即使用下面的方法 import sys

['D:Python27Libidlelib', 'C:',

'D:Python27DLLs', 'D:Python27lib', 'D:Python27libplat-win',

'D:Python27liblib-tk','D:Python27','D:Python27libsite-packages']

#这里是你sys初始导入路径

>>> ('D:QQPCmgrDesktopBlindSearchProject')

#这里是你sys新增的导入路径

>>>

['D:Python27Libidlelib', 'C:',

'D:Python27DLLs', 'D:Python27lib', 'D:Python27libplat-win',

'D:Python27liblib-tk', 'D:Python27','D:Python27libsite-packages',

'D:QQPCmgrDesktopBlindSearchProject']

#新增导入路径后确认路径导入成功

>>> import mazeworld此时，不再有出错提示，成功,分析成功原因

#由于此时系统具有了文件所在文件夹的路径，故当使用import命令时，系统会自动来到

#这个文件夹进查找，当然就可找到而不会出错了

#同时还有可能是因为版本问题出现报错，因为python2和python3要求的输出语言的代码不同

#python2系列可以支持 print “xxxx” ，python系列需要使用print("xxx")

simpleMaze = ([['#', ' ', ' ', ' '], ['~', 'S', ' ', 'E']])

print simpleMaze

理解迷宫的表现形式

#输出的迷宫为

- - - -

|# |

|~ S E|

- - - -

#迷宫最典型的表现形式便是矩阵，而此处的迷宫也同样如此。整个迷宫是一个列表，而迷宫的每一行也

#是一个列表，而行列表里的元素才是真正的迷宫格

#迷宫的输出是由maze类的方法__getAsciiString实现的

#从Maze类中，我们可以得到各种迷宫格对应值的含义：

# '#': 表示障碍单元（无法通过）

# '~': 表示“水”单元（可以通过，但是代价高）

# ' ': 空单元（可以通过）

# 'S': 起点

# 'E': 出口

3

实现最简单的搜索Agent(只是简单的往右走，如果碰巧迷宫的起点和终点在同一行，且没有障碍物阻挡，终点又是在起点的左边，那么这个最简单的Agent能够完成任务)： simpleMazeAgent = MazeAgent()

entOnMaze(simpleMazeAgent, simpleMaze)

分析运行结果

#运行的输出结果为：

- - - -

|# |

|~ S x E|

- - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 2.0

Number of nodes expanded: 2

Number of unique nodes expanded: 2

#运行结果的输出是由方法testAgentOnMaze完成的，具体如下：

def testAgentOnMaze(agent, maze, verbose=True):

"""

Test the search agent 'agent' on the 'maze'

and prints the cost of the solution and also

displays the maze along with 'x' for the cells

used in the solution and 'o' for cells expanded

but not used in the solution

"""

problem = MazeSearchProblem(maze)

# 生成MazeSearchProblem类的一个实例problem，迷宫布局为maze

solution, cost = (problem)

# 使用智能体来解迷宫问题

if solution == None:

print '找不到解决方案!'

ySearchStats()

earchStats()

return

if verbose:

grid_copy = []

for row in :

grid_([x for x in row])

# 生成一个迷宫网格的副本，以便之后生成解迷宫

for x,y in edNodeSet:

ch = [x][y]

if ch != 'S' and ch != 'E': grid_copy[x][y] = 'o'

# 在网格副本上记录搜索路径

for x,y in solution:

ch = [x][y] if ch != 'S' and ch != 'E': grid_copy[x][y] = 'x'

# 在网格副本上记录解路径

maze_copy = Maze(grid_copy)

# 使用迷宫网格生成解迷宫

print maze_copy

print "x - 解路径上的单元格"

print "o - 搜索过程扩展过的单元格"

print "-------------------------------"

print '解的耗散:', cost

ySearchStats()

# 输出解迷宫

5 直接从文本文件读入迷宫：

maze1 = zeFromFile('')

print maze1

输出结果为：

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

| |

| # # # # # # # # # # # # # # # |

| # # # # # # # # # # # # # # # E|

| # # # |

| S # # # |

| # # # |

| |

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

6 实现深度优先搜索(DFS)Agent：

在里的DepthFirstSearchAgent类中实现深度优先搜索算法

由于DepthFirstSearchAgent类已经由老师实现了，以下仅是针对代码给出本人的注释：

class DepthFirstSearchAgent(SearchAgent):

#继承SearchAgent类

def solve(self,searchProblem):

fringe = ()

#边缘堆栈，用于存储等待扩展的节点

(Node(rtState(), None, 0.0))

#将起始节点压入堆栈

closed = set() # faster than list for membership test

#已扩展节点的集合

while not y(): node = ()

#每次从堆栈中取最后一个节点出来扩展

if State():

return (tracepath(node), st)

#测试是否达到目标状态，若达到则返回解路径（由tracepath函数递归得到）和总耗散

elif not in closed:

()

for (nextstate, nextcost) in cessors():

(Node(nextstate, node, st + nextcost))

#若未达到目标状态，则将此节点加入已扩展集合，并将其新的扩展压入堆栈

return (None, 0.0)

#当找不到解路径时，返回空解和0耗散

#以下是上面提到的递归求解路径的函数：

def tracepath(node):

if :

return tracepath() + []

#通过递归将，逐步将解路径上的双亲节点加入解路径列表中来

else:

return []

通过下列语句测试你实现的DFS

import search

agent = irstSearchAgent()

entOnMaze(agent,maze1,verbose=True)

输出结果为：

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

| |

| # # # # # # # # # # # # # # # |

| # # # # # # # # # # # # # # # x x x x E|

| # # # x x x x x|

| S x x x x x x x # # # x x x x x|

| x # # # x x x x x|

| x x x x x x x x x|

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 61.0 Number of nodes expanded: 61

Number of unique nodes expanded: 61

#由上图可以推测出智能体的寻路顺序为：左、下、右、上。

#此算法仅给出了问题的一个解，但并不是最优解

7 实现广度优先搜索(BFS)Agent：

在里的BreadthFirstSearchAgent中实现广度优先搜索算法

class BreadthFirstSearchAgent(SearchAgent):

def solve(self,searchProblem):

fringe = ()

#边缘队列，存放等待扩展的节点

e(Node(rtState(), None, 0.0))

#将起始节点压入队列

closed = set() # faster than list for membership test

#已扩展节点集合

while not y():

node = e()

#每次从队列中取第一个节点来扩展

if State():

return (tracepath(node), st)

#测试是否达到目标状态，若达到则返回解路径和总耗散

elif not in closed:

()

for (nextstate, nextcost) in cessors():

e(Node(nextstate, node, st + nextcost))

#若未达到目标状态，则将此节点加入已扩展集合，并将其新的扩展压入队列

return (None, 0.0)

#当找不到解路径时，返回空解和0耗散

#注意到广度优先搜索的代码和深度优先搜索的代码极为相似，唯一的区别就是两者用于存放代扩展节点

#的容器（DFS为堆栈<先进后出>、BFS为队列<先进先出>），这也正反映了二者扩展节点的独特方式

并通过下列语句测试你的BFS

import search

agent = hFirstSearchAgent()

entOnMaze(agent,maze1,verbose=True)

输出结果为：

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

|o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o|

|o o o o o o o o o o # # # # # # # # # # # # # # # o o o o |

|o o o o o o o o o o # # # # # # # # # # # # # # # x x x x E|

|o o o o o o o o o o o o o o o o o o o o o o # # # x o o o o| |o o o o o o o o o o o o o o S o o o o o o o # # # x o o o o|

|o o o o o o o o o o o o o o x o o o o o o o # # # x o o o o|

|o o o o o o o o o o o o o o x x x x x x x x x x x x o o o o|

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 29.0

Number of nodes expanded: 277

Number of unique nodes expanded: 277

#这个算法求解的过程是相当惊人的，智能体几乎把迷宫走了个遍（除了终点E上面唯一的一格），但意外

#的发现是它居然是比深度优先更优的解（解耗散DFS：61、BFS：29），甚至是本问题的一个最优解，

#这会不会是一个巧合呢？当然不会，这是由广度搜索的逐层搜索策略所决定的：若问题的解存在，则它

#必然会在最浅的一层找到解，无可厚非，这便是最优解！！

#但不可否认地，它也为此最优解付出了沉重的代价：整个解的过程一共扩展到了第29层，扩展分支数为#4，于是扩展节点激增到了277个，几乎覆盖了整块迷宫。效率上大打折扣，在更大的迷宫问题上，这是

#不可容忍的。

与6得到的解相比较，哪一个得到的是最优解，两者扩展的节点数有何不同？

再将你实现的两种搜索算法应用于求解迷宫，并对比分析。

首先使用以下命令，观察迷宫：

maze2 = zeFromFile('')

print maze2

输入结果为：

- - - - - - - - - - - - - - - - - - - -

|# # # # |

|# # # # ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ |

|# S ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ E|

|# # # # # ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ |

|# # # # # | - - - - - - - - - - - - - - - - - - - -

#注意到这是相对复杂的迷宫，其中包含了大面积的水域

DFS求解：

键入以下命令：

agent = irstSearchAgent()

entOnMaze(agent,maze2,verbose=True)

输出结果为：

- - - - - - - - - - - - - - - - - - - -

|# # # # |

|# # # # ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ |

|# S x x x x x x x x x x x x x x x x x E|

|# # # # # ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ |

|# # # # # |

- - - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 70.0

Number of nodes expanded: 18

Number of unique nodes expanded: 18

BFS求解：

键入以下命令：

agent = hFirstSearchAgent()

entOnMaze(agent,maze2,verbose=True)

输出结果为：

- - - - - - - - - - - - - - - - - - - -

|# # # # o o o o o o o o o o o |

|# # # # o o o o o o o o o o o o ~ ~ ~ |

|# # # # o o o o o o o o o o o o o ~ ~ |

|# # # # o o o o o o o o o o o o o o ~ |

|# # # # o o o o o o o o o o o o o o o |

|# S x x x x x x x x x x x x x x x x x E|

|# # # # # o o o o o o o o o o o o o o |

|# # # # # o o o o o o o o o o o o o ~ |

|# # # # # o o o o o o o o o o o o ~ ~ |

|# # # # # o o o o o o o o o o o ~ ~ ~ | |# # # # # o o o o o o o o o o |

- - - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 70.0

Number of nodes expanded: 143

Number of unique nodes expanded: 143

#针对这个maze2迷宫，两种算法出现了相同的解（当然DFS出现这样的解是由它的寻路顺序决定的），

#但这个解却不是最优解，问什么呢？这是由于迷宫中存在不同耗散的缘故，现在更正一下，广度优先所

#求出的解必定是具有“最短路径”的，但现在由于路径上存在不同的耗散，故即使是“最短的路径“但

#却未必是“耗散最少的路径”。

8 实现代价一致搜索(UCS)Agent：

在里的类UniformCostSearchAgent中实现代价一致搜索算法

class UniformCostSearchAgent(SearchAgent):

def solve(self,searchProblem):

fringe = tyQueue()

#边缘优先队列，用于存储待扩展的节点（其内的元素为Node节点，参照节点耗散值，使用最小堆

#的方法对各节点进行排序）

ority(Node(rtState(), None, 0.0), 0.0)

#将起始点加入优先队列

closed = set() # faster than list for membership test

#已扩展节点集合

while not y():

node = e()

#每次从优先队列中弹出一个总耗散值最小节点进行扩展

if State():

return (tracepath(node), st)

#测试是否达到目标状态，若达到则返回解路径和总耗散

elif not in closed:

()

for (nextstate, nextcost) in cessors():

g = st + nextcost

ority(Node(nextstate, node, g), g)

#若未达到目标状态，则将此节点加入已扩展集合，并修改总耗散且将其新的扩展压入队列

return (None, 0.0) #当找不到解路径时，返回空解和0耗散

#这个优先队列（定义在文件中）的实现有些特别，它包含了一个节点列表（使用系统内置的堆函

#数可以对其进行排列），和一个索引字典（使用Node作为索引值，索引包含priority和Node的列表值）

将其应用于求解描述的迷宫，是否找到了最优解？再将其应用于求解，分析其扩展的节点是否都是求解需要扩展的节点？

求解maze2迷宫：

键入以下命令：

maze2 = zeFromFile('')

agent = search. UniformCostSearchAgent()

entOnMaze(agent,maze2,verbose=True)

输出结果为：

- - - - - - - - - - - - - - - - - - - -

|# # # # x x x x x x x x x x x x x x x x|

|# # # # x o o o o o o o o o o o o o o x|

|# # # # x o o o o o o o o o o ~ ~ ~ ~ x|

|# # # # x o o o o o ~ ~ ~ ~ ~ ~ ~ ~ ~ x|

|# S x x x o o o o o ~ ~ ~ ~ ~ ~ ~ ~ ~ E|

|# # # # # o o o o o ~ ~ ~ ~ ~ ~ ~ ~ ~ o|

|# # # # # o o o o o o o o o o ~ ~ ~ ~ o|

|# # # # # o o o o o o o o o o o o o o o|

- - - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 28.0

Number of nodes expanded: 120

Number of unique nodes expanded: 120

#由上图可见，代价一致算法的确找到了一个最优解

求解maze3迷宫：

键入以下命令：

maze3 = zeFromFile('')

print maze3

输出结果为：

- - - - - - - - - - - - - - - - - - -

|~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~|

|~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~| |~ ~ ~ ~ ~ ~ ~ ~ ~|

|~ ~ ~ ~ ~ ~ ~|

|# # # # # # # # ~ ~ ~ ~ ~ ~ ~ ~|

| # # # # # #|

| S # ~ ~ ~ ~ ~|

|# # # # # # # # # # # # ~ ~ ~ ~ ~|

| # # ~ ~ ~ ~ ~|

| # # # # # # # # # # # # ~ ~ ~|

| # # ~ ~ ~ ~ ~ ~|

| # # # # # # # ~ ~ ~ ~ ~ ~|

| E|

- - - - - - - - - - - - - - - - - - -

#这应该是目前为止最像迷宫的迷宫了^ ^

继续键入命令：

agent = search. UniformCostSearchAgent()

entOnMaze(agent,maze3,verbose=True)

输出结果为：

- - - - - - - - - - - - - - - - - - -

|~ ~ ~ ~ o o o o o o o o o o o ~ ~ ~ ~|

|~ ~ ~ o o o o o o o o o o o o o ~ ~ ~|

|~ ~ o o o o o o o o o o o o o o o ~ ~|

|~ o o o o o o o o o o o o o o o o o ~|

|# # # # # # # # o o o o o o o o o ~ ~|

|o o o o o o o o o o o o o # # # # # #|

|o o o o o o S x x o o o o # o ~ ~ ~ ~|

|# # # # # # o # x # # # # # o o ~ ~ ~|

|o o o o o # o # x x x x o o o o o ~ ~|

|o # o # o # # # # # # x # # # # ~ ~ ~|

|o # o o o o o o x x x x # ~ ~ ~ ~ ~ ~|

|o o o o o # # # x # # # # o ~ ~ ~ ~ ~|

|o o o o o o o o x x x x x x x x x x E|

- - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 24.0

Number of nodes expanded: 151

Number of unique nodes expanded: 151

#算法没有扩展多余的节点，这是由优先队列的性质决定的，解路径必定是所有路径中耗散最大的一条路

#径。

4 修改2中的迷宫，使得3的简单Agent无法求解；然后实现一个能求解你修改后迷宫的搜索Agent（例如可以简单把路线硬拷贝到你实现的简单Agent，即直接告诉它怎么走）这是中间的一道问题，但我却拿到后面来做，是因为我我写的这段代码实现的是迭代深入深度优先搜索，而并不是硬性给予智能体行动路线。

以下使我添加/改动的代码：

#Filename:

class Stack:

……

def removeAll(self):

"""

Remove all items from the stack

"""

del [:]

#在堆栈类中添加一个清空堆栈所有元素的函数

#Filename:

class Nodep:

def __init__(self, state, parent, pathcost, depth):

= state

= parent

st = pathcost

= depth

#创建一个包含深度信息节点类

class IterativeDeepeningSearchAgent(SearchAgent):

def solve(self,searchProblem):

fringe = ()

#边缘堆栈，用于存储等待扩展的节点

(Nodep(rtState(), None, 0.0, 1))

#设置起始节点深度为1，并将其压入堆栈

closed = set()

#已扩展节点的集合

limit = 50

#由于深度限制变量的接口不好扩展，要改动的地方太多，于是只能固化此值

depth = 1

#初始迭代深度为1

while depth != limit + 1 :

#只要节点深度未超过迭深度限制，则可继续扩展节点

while not y():

nodep = ()

#每次从堆栈中取最后一个节点出来扩展

if State():

return (tracepath(nodep),st) #测试是否达到目标状态，若达到则返回解路径和总耗散

if == depth:

continue

if not in closed:

()

for (nextstate, nextcost) in

cessors():

(Nodep(nextstate, nodep, st + nextcost,

+ 1))

#若未达到目标状态，则将此节点加入已扩展集合，并将其新的扩展压入堆栈

depth += 1

#迭代深度加1

All()

(Nodep(rtState(), None, 0.0, 1))

#边缘堆栈复原

()

#清空已扩展节点集合

esExpanded = 0

()

#重置扩展节点数及集合

#若一次迭代搜索为找到目标结点，则迭代深度加1并初始化部分变量

return (None, 0.0)

#当在最大深度内找不到解路径时，返回空解和0耗散

以下是一些性能的比较：

对maze1求解：

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

| |

| # # # # # # # # # # # # # # # |

| # # # # # # # # # # # # # # # E|

| # # # x|

| S x x x x x x x # # # o x|

| x # # # o o x|

| x # # # o x x|

| x # # # o o o x x|

| x # # # o o o o x|

| x x x x x x x x x|

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 31.0

Number of nodes expanded: 46 Number of unique nodes expanded: 46

#可见这是一种介于深度优先与广度优先之间的算法，它的解是相对较优的（不是最优的），而扩展节点数

#也是最少的

#事实上从理论上说，这种迭代深度深入算法是可以找到最优解的，但此处却出现了奇怪的现象，这是由

#于算法的不完美回溯造成的：即回溯的过程中并未释放访问过的节点，而这些节点有些可能不在最优解

#路径上的

对maze3求解：

- - - - - - - - - - - - - - - - - - -

|~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~|

|~ ~ ~ ~ ~ ~ ~ ~ o ~ ~ ~ ~ ~ ~ ~ ~ ~ ~|

|~ ~ ~ ~ ~ o o o o ~ ~ ~ ~|

|~ ~ ~ ~ o o o o o o o ~ ~ ~|

|# # # # # # # # o o o o o o ~ ~ ~ ~ ~|

| o o o o o o o o o # # # # # #|

| o o o S x x o o o o # ~ ~ ~ ~ ~|

|# # # # # # # x # # # # # ~ ~ ~ ~ ~|

| # # x x x x x x x x x x x|

| # # # # # # # # # # # # ~ ~ x|

| # # ~ ~ ~ ~ ~ x|

| # # # # # # # ~ ~ ~ ~ ~ x|

| E|

- - - - - - - - - - - - - - - - - - -

x - 解路径上的单元格

o - 搜索过程扩展过的单元格

-------------------------------

解的耗散: 50.0

Number of nodes expanded: 52

Number of unique nodes expanded: 52

#这个迭代深度深入算法与深度、广度优先一样，也只能对仅有单一权值的路径进行搜索。它和广度优先

#一样求解的是最短路径，解的最优性是建立在路径耗散一致的基础上的。

本文发布于:2023-12-11，感谢您对本站的认可！

本文链接:https://www.fzithome.com/xitong/1702295373a60956.html

实验二盲目搜索

发布评论取消回复

最近发表

相关推荐

标签列表

实验二 盲目搜索

发布评论 取消回复

最近发表

相关推荐

标签列表

实验二盲目搜索

发布评论取消回复