实验一、盲目搜索算法.doc

word
word
1 / 16
word
实验一：盲目搜索算法
一、实验目的
掌握盲目搜索算法之一的宽度优先搜索求解算法的根本思想。对于宽度优先搜索算法根本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。
二、实验环境
PC机一台，VC++
三、实验原理
宽度优先搜索算法〔又称广度优先搜索〕是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。同时，宽度优先搜索算法是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。 
其根本思想是：
(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，如此求得一个解答)。
　　(2) 如果OPEN是个空表，如此没有解，失败退出；否如此继续。
　　(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。
　　(4) 扩展节点n。如果没有后继节点，如此转向上述第(2)步。
　　(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。
　　(6) 如果n的任一个后继节点是个目标节点，如此找到一个解答，成功退出；否如此转向第(2)步。
word
word
2 / 16
word
宽度优先搜索示意图和宽度优先算法流程图如如下图1和图2所示：
S
B
A
D
C
E
F
G
H
I
J
图1、宽度优先搜索示意图
起始
把S放入OPEN表
Fangru
word
word
4 / 16
word
OPEN是否为空表?
否
是
失败
把第一个节点n,从OPEN表移出,并把它放入CLOSED表
扩展n,把它的后继节点放入OPEN
表的末端,提供回到n的指针
是否有任何后继节点为目标节点?
否
是
成功
图2、宽度优先算法流程图
四、实验数据与步骤
这局部容是通过一个实例来对宽度优先算法进展一个演示，分析其思想。问题描述了《迷宫问题》的出路求解方法。
定义一个二维数组： 
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，
};
word
word
4 / 16
word
它表示一个迷宫，其中的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={}，初始化所有节点为白色节点，说明：初始全部都是白色〔未访问〕，即将搜索起点〔灰色〕，已经被搜索过了〔黑色〕。开始我们的宽度搜索。执行步骤：
，参加队列Q，Q={(0，0)}
的头一个节点Vn，Vn={0，0}，Q={}
={0，0}染成黑色，取出Vn所有相邻的白色节点{(1，0)}
(4，4)，染成灰色，参加队列Q，Q={(1，0)}
的头一个节点Vn，Vn={1，0}，Q={}
={1，0}染成黑色，取出Vn所有相邻的白色节点{(2，0)}
(4，4)，染成灰色，参加队列Q，Q={(2，0)}
word
word
5 / 16
word
的头一个节点Vn，Vn={2，0}，Q={}
={2，0}染成黑色，取出Vn所有相邻的白色节点{(2，1)， (3，0)}
(4，4)，染成灰色，参加队列Q，Q={(2，1)， (3，0)}
的头一个节点Vn，Vn={2，1}，Q={(3，0)}
1