文档介绍：实验一、盲目搜索算
法
实验一：盲目搜索算法
一、实验目的
掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。对于宽度优先搜索算法基本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。
二、实验环境
PC 机一台，VC++
三、实验原理
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一，
这一算法也是很多重要的图的算法的原型。Dijkstra 单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS属于
一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。同时，宽度优先搜索算法是连通图的一种遍历策略。因为它的思想是从一个顶点 V0开始，辐射状地优先遍历其周围较广的区域，故得名。
其基本思想是：
把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一
个解答)。
如果OPEN是个空表，则没有解，失败退出；否则继续。
把第一个节点(节点n)从OPEN表移出，并把它放入 CLOSE扩展
节点表中。
扩展节点n。如果没有后继节点，则转向上述第(2)步。
把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点
回到n的指针。
如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第⑵步。
宽度优先搜索示意图和宽度优先算法流程图如下图 1和图2所示：
扩展n,把它的后继节点放入
四、实验数据及步骤
这部分内容是通过一个实例来对宽度优先算法进行一个演示，分析其思
想。问题描述了《迷宫问题》的出路求解办法。
定义一个二维数组：
int maze[5][5]
={
0,
1,
0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
0,
0,
0,
0,
1,
0,
｝；
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。题目保证了输入是一定有解的。下面我们队问题进行求解：
对应于题目的输入数组：
0，1，0，0，0，
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
我们把节点定义为(y, x), (y, x)表示数组maze的项maze[x][y]。于是起点
就是(0, 0),终点是(4, 4)。我们大概梳理一遍：
初始条件：起点Vs为(0, 0),终点Vd为(4, 4),灰色节点集合Q={}，初始化所有节点为白色节点，说明：初始全部都是白色(未访问)，即将搜索起点(灰色)，已经被搜索过了(黑色)。开始我们的宽度搜索。执行步骤：
1•起始节点Vs变成灰色，加入队列 Q, Q={(0 , 0)}
取出队列Q的头一个节点Vn, Vn={0 , 0}, Q={}
把Vn={0 , 0}染成黑色，取出Vn所有相邻的白色节点{(1 , 0)}
不包含终点(4, 4),染成灰色，加入队列 Q, Q={(1 , 0)}
取出队列Q的头一个节点Vn , Vn={1 , 0} , Q={}
把Vn={1 , 0}染成黑色,取出Vn所有相邻的白色节点{(2 , 0)}
不包含终点(4 , 4),染成灰色,加入队列 Q , Q={(2 , 0)}
取出队列Q的头一个节点Vn , Vn={2 , 0} , Q={}
把Vn={2, 0}染成黑色，取出Vn所有相邻的白色节点{(2, 1) , (3 , 0)}
不包含终点(4 , 4),染成灰色,加入队列 Q , Q={(2, 1) , (3 , 0)}
11取出队列Q的头一个节点Vn , Vn={2 , 1} , Q={(3 , 0)}
把Vn={2 , 1}染成黑色，取出Vn所有相邻的白色节点{(2, 2)}
不包含终点(4 , 4),染成灰色,加入队列 Q , Q={(3 , 0) , (2 , 2)}
持续下去，知道Vn的所有相邻的白色节点中包含了 (4 , 4)……
此时获得最终答案
我们来看看广度搜索的过程中节点的顺序情况：
(0,t>}
¥
图3迷宫问题的搜索树
图中标号即为我们搜索过程中的顺序，我们观察到，这个搜索顺序是按照上图的层次关系来的，例如节点（0，0）在第1层，节点（1，0）在第2层，节点（2，0）在第3层，节点（2，1）和节点（3，0）在第3层。
我们的搜索顺序就是第一层-＞第二层-＞第三层-＞第N层这样子。
我们假设终