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

实验一:盲目搜索算法一、实验目的掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。对于宽度优先搜索算法基本过程,算法分析有一个清晰的思路,了解宽度优先搜索算法在实际生活中的应用。二、实验环境PC机一台,VC++、实验原理宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。同时,宽度优先搜索算法是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名。 其基本思想是:(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。(2)如果OPEN是个空表,则没有解,失败退出;否则继续。(3)把第一个节点(节点n)从OPEN表移出,并把它放入CLOSED扩展节点表中。(4)扩展节点n。如果没有后继节点,则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(2)步。宽度优先搜索示意图和宽度优先算法流程图如下图1和图2所示:SBADCEFGHIJ图1、宽度优先搜索示意图起始把S放入OPEN表FangruOPEN是否为空表?否是失败把第一个节点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,};它表示一个迷宫,其中的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={0,0},Q={}={0,0}染成黑色,取出Vn所有相邻的白色节点{(1,0)}(4,4),染成灰色,加入队列Q,Q={(1,0)},Vn={1,0},Q={}={1,0}染成黑色,取出Vn所有相邻的白色节点{(2,0)}(4,4),染成灰色,加入队列Q,Q={(2,0)},Vn={2,0},Q={}={2,0}染成黑色,取出Vn所有相邻的白色节点{(2,1), (3,0)}(4,4),染成灰色,加入队列Q,Q={(2,1), (3,0)},Vn={2,1},Q={(3,0)}={2,1}染成黑色,取出Vn所有相邻的白色节点{(2,2)}(4,4),染成灰色,加入队列Q,Q={(3,0), (2,2)},知道Vn的所有相邻的白色节点中包含了(4,4)……:图3 迷宫问题的搜索树图中标号即为我们搜索过程中的顺序,我们观察到,这个搜索顺序是按照上图的层次关系来的,例如节点(0,0)在第1层,节点(1,0)在第2层,节点(2,0)在第3层,节点(2,1)和节点(3,0)在第3层。我们的搜索顺序就是第一层->第二层->第三层->第N层这样子。我们假设终点在第N层,因此我们搜索到的路径长度肯定是N,而且这个N一定是所求最短的。我们用简单的反证法来证明:假设终点在第N层上边出现过,例如第M层,M<N