实验一盲目搜索算法.docx

实验一：盲目搜索算法
一、实验目的
掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。对于宽度优先搜索算法基本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。
二、实验环境
PC机一台，VC++6.0
三、实验原理
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。同时，宽度优先搜索算法是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。
其基本思想是：
(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。
宽度优先搜索示意图和宽度优先算法流程图如下图1和图2所示：

S

B
A

D
C

E
F

G

H

I

J

图1、宽度优先搜索示意图
起始

把S放入OPEN表
Fangru

OPEN是否为空表?
否
是

失败

把第一个节点n,从OPEN表移出,并把它放入CLOSED表

扩展n,把它的后继节点放入OPEN
表的末端,提供回到n的指针

是否有任何后继节点为目标节点?

否
是

成功

图2、宽度优先算法流程图

四、实验数据及步骤
这部分内容是通过一个实例来对宽度优先算法进行一个演示，分析其思想。问题描述了《迷宫问题》的出路求解办法。
定义一个二维数组：intmaze[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)}
2.取出队列Q的头一个节点Vn，Vn={0，0}，Q={}
3.把Vn={0，0}染成黑色，取出Vn所有相邻的白色节点{(1，0)}
4.不包含终点(4，4)，染成灰色，加入队列Q，Q={(1，0)}
5.取出队列Q的头一个节点Vn，Vn={1，0}，Q={}
6.把Vn={1，0}染成黑色，取出Vn所有相邻的白色节点{(2，0)}
7.不包含终点(4，4)，染成灰色，加入队列Q，Q={(2，0)}
8.取出队列Q的头一个节点Vn，Vn={2，0}，Q={}
9.把Vn={2，0}染成黑色，取出Vn所有相邻的白色节点{(2，1)，(3，0)}
10.不包含终点(4，4)，染成灰色，加入队列Q，Q={(2，1)，(3，0)}
11.取出队列Q的头一个节点Vn，Vn={2，1}，Q={(3，0)}
12.把Vn={2，1}染成黑色，取出Vn所有相邻的白色节点{(2，2)}
13.不包含终点(4，4)，染成灰色，加入队列Q，Q={(3，0)，(2，2)}
14.持续下去，知道Vn的所有相邻的白色节点中包含了(4，4)……
15.此时获得最终答案
我们来看看广度搜索的过程中节点的顺序情况：

图3迷宫问题的搜索树
图中标号即为我们搜索过程中的顺序，我们观察到，这个搜索顺序是按照上图的层次关系来的，例如节点(0，0)在第1层，节点(1，0)在第2层，节点(2，0)在第3层，节点(2，1)和节点(3，0)在第3层。
我们的搜索顺序就是第一层->第二层->第三层->第N层这样子。
我们假设终点在第N层，因此我们搜索到的路径长度肯定是N，而且这个N一定是所求最短的。

我们用简单的反证法来证明：假设