迷宫的搜索算法课件.ppt

《迷宫的搜索算法课件.ppt》由会员分享，可在线阅读，更多相关《迷宫的搜索算法课件.ppt（38页珍藏版）》请在三一文库上搜索。

1、迷宫的搜索算法,1,株洲市二中 陈鸥辉,迷宫的搜索算法实现,迷宫的搜索算法,2,本周内容,1. 迷宫的构成 2. 迷宫的深度优先搜索 3. 迷宫的广度优先搜索,迷宫的搜索算法,3,1、迷宫的构成,迷宫场地 一般如下，移动方向可能四种：上下左右,入口,出口,迷宫的搜索算法,4,2、深度优先搜索,A,B,C,D,E,J,H,G,I,F,深度优先搜索: ABFICDGHJE 原理就是一条道走到底 走不通再回来尝试下一 条道。,迷宫的搜索算法,5,2、深度优先搜索,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,深度优先遍历的方法是，从表中起点出发： （1）访问A； （2）依次从表中的

2、未被访问的邻接点出发，对表进行深度优先遍历；直至图中和A有路径相通的点都被访问； （3）若此时表中尚有顶点未被访问，则从一个最后入栈未被访问的顶点出发，重新进行深度优先遍历，直到表中所有顶点均被访问过为止。,迷宫的搜索算法,6,3、广度优先搜索,A,B,C,D,E,J,H,G,I,F,广度优先搜索: ABCDEFGHIJ 原理就是一层层遍历 直到遍历最后一层,迷宫的搜索算法,7,3、广度优先搜索,A,B,C,D,E,F,H,I,J,K,L,M,N,O,广度优先遍历的方法是，从表中起点A出发： （1）访问A； （2）依次从表中的未被访问的邻接点出发，对表进行广度优先遍历；直至图中和A有路径相通的

3、点都被访问； （3）若此时表中尚有顶点未被访问，则从最先入队的未被访问的顶点出发，重新进行广度优先遍历，直到表中所有顶点均被访问过为止。,迷宫的搜索算法,8,2.5基本算法之搜索 ,迷宫的搜索算法,9,2753:走迷宫,描述 一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。 给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。 输入 第一行是两个整数，和，代表迷宫的长和宽。（ 1= R，C = 40) 接下来是行，每行个字符，代表整个迷宫。 空地格子用.表示，有障碍物的格子用#表示。 迷宫左上角和右下

4、角都是.。 输出 输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。,迷宫的搜索算法,10,2753:走迷宫,样例输入 5 5 .# #. #.#.# #.#.# #.#. 样例输出 9,迷宫的搜索算法,11,2753:走迷宫,样例输入 5 5 .# #. #.#.# #.#.# #.#. 样例输出 9,起点：（0,0） 终点（4,4）,迷宫的搜索算法,12,2753:走迷宫,起点：（0,0） 终点（4,4）,深度优先遍历的方法是，从表中起点（0,0）出发： （1）访问（0,0）； （2）依次从表中的未被访问的邻接点出发，对表进行深度优先遍历；直至

5、图中和（0,0）有路径相通的点都被访问； （3）若此时表中尚有顶点未被访问，则从一个最后入栈未被访问的顶点出发，重新进行深度优先遍历，直到表中所有顶点均被访问过为止。,迷宫的搜索算法,13,2753:走迷宫深度优先实现方法：,起点：（0,0） 终点（4,4）,栈,栈：先进后出,依次入栈，并将走过的点(0,0)标记#，不能再走。,迷宫的搜索算法,14,2753:走迷宫深度优先实现方法：,起点：（0,0） 终点（4,4）,栈,栈：先进后出,依次入栈，并将走过的点(0,1)标记#，不能再走。,迷宫的搜索算法,15,2753:走迷宫深度优先实现方法：,起点：（0,0） 终点（4,4）,栈,栈：先进后出

6、,依次入栈，直到（1,4）点无路可以扩展，开始回溯 即出栈,迷宫的搜索算法,16,2753:走迷宫深度优先实现方法：,起点：（0,0） 终点（4,4）,栈,栈：先进后出,（1,4）出栈后，（1,3）可以继续扩展深度搜索,迷宫的搜索算法,17,2753:走迷宫深度优先实现方法：,起点：（0,0） 终点（4,4）,栈,栈：先进后出,直到(4,4)入栈，说明走出迷宫,迷宫的搜索算法,18,2753:走迷宫深度优先实现方法：,起点：（0,0） 终点（4,4）,栈,栈：先进后出,如果不剪枝，则会继续回溯，将所有点都遍历完。并且栈元素为空。,栈,迷宫的搜索算法,19,2753:走迷宫递归实现参考程序,#i

7、nclude #include using namespace std; char a4040;int s4040,n,m; void check(int x,int y) axy=#;/遍历过的点标记不能再走 /向四个方向扩展搜索，由于递归实现的就是栈的功能，所以实现的是深搜 if(axy-1=. ,迷宫的搜索算法,20,2753:走迷宫模拟栈实现参考程序,#include #include using namespace std; char a4040;int s4040,n,m,top; structint x;int y;p10000;/栈元素，二维数组元素的下标 void push(

8、int x,int y)top+;ptop.x=x;ptop.y=y;/压栈 int pop()return top-;/出栈 void check(int x,int y) do axy=#;/遍历过的点标记不能再走 if(x-10 ,迷宫的搜索算法,21,6264:走出迷宫,描述 当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。 假设你已经得到了一个m*n的迷宫的图纸，请你找出从起点到出口的最短路。 输入 第一行是两个整数m和n(1=m,n=100)，表示迷宫的行数和列数。 接下来m行，每行一个长为n的字符串，表示整个迷宫的布局。

9、字符.表示空地，#表示墙，S表示起点,T表示出口。 输出 输出从起点到出口最少需要走的步数。,样例输入 3 3 S#T .#. . 样例输出 6,迷宫的搜索算法,22,6264:走出迷宫,样例输入 5 5 .S. #.#. #.#. #.#.# #.T 样例输出 7,起点：（0,1） 终点（4,4）,迷宫的搜索算法,23,6264:走出迷宫,样例输入 5 5 S. #.#. #.#. #.#.# #.T 样例输出 7,起点：（0,1） 终点（4,4）,迷宫的搜索算法,24,6264:走出迷宫模拟栈实现深搜参考程序,#include #include using namespace std; c

10、har a100100;int s100100,n,m,top,bx,by,ex,ey; structint x;int y;p10000;/栈元素，二维数组元素的下标 void push(int x,int y)top+;ptop.x=x;ptop.y=y;/压栈 int pop()return top-;/出栈 void check(int x,int y) do axy=#;/遍历过的点标记不能再走 if(x-10/只要栈不为空，则一直执行入栈出栈操作 ,int main() cinmn; for(int i=0;iaij; if(aij=S) bx=i;by=j;aij=.; if(a

11、ij=T) ex=i;ey=j;aij=.; check(bx,by); coutsexeyendl; return 0; ,深搜能够得到解，但一般最先走出的路径不是最优解， 所以此程序只能通过部分测试点。,迷宫的搜索算法,25,6264:走出迷宫,样例输入 5 5 .S. #.#. #.#. #.#.# #.T 样例输出 7,起点：（0,1） 终点（4,4）,迷宫的搜索算法,26,6264:走出迷宫广度优先搜索,起点：（0,1） 终点（4,4）,广度优先遍历的方法是，从表中起点（0,0）出发： （1）访问（0,0）； （2）依次从表中的未被访问的邻接点出发，对表进行广度优先遍历；直至图中和（

12、0,0）有路径相通的点都被访问； （3）若此时表中尚有顶点未被访问，则从最先入队的未被访问的顶点出发，重新进行广度优先遍历，直到表中所有顶点均被访问过为止。,迷宫的搜索算法,27,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,依次入队列，并将走过的点(0,1)标记#，不能再走。,迷宫的搜索算法,28,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（0,0）出队，无路可走，即（0,0）点无可扩展点，则没有点可以入队，继续下一点出队,迷宫的搜索算法,29,6264:走出迷宫广度优先实现方法：,起点：（0

13、,0） 终点（4,4）,队列,队列：先进先出,（0,2）出队，有一条路可走，即（0,3）入队，继续下一点出队。,迷宫的搜索算法,30,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（1,1）出队，有一条路可走，即（2,1）入队，继续下一点出队。,迷宫的搜索算法,31,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（0,3）出队，有一条路可走，即（0,4）入队，继续下一点出队。,迷宫的搜索算法,32,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（0,3

14、）出队，有一条路可走，即（0,4）入队，继续下一点出队。,迷宫的搜索算法,33,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（2,1）出队，有一条路可走，即（3,1）入队，继续下一点出队。,迷宫的搜索算法,34,6264:走出迷宫广度优先实现方法：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（4,4）出队，搜索完毕。由广搜可以得知，7是我们要查找的最短路径。,迷宫的搜索算法,35,6264:走出迷宫模拟队列实现广搜参考程序,#include #include using namespace std; char a100100;in

15、t s100100,n,m,rear,bx,by,ex,ey,front; structint x;int y;p10000;/队列元素，二维数组元素的下标 void push(int x,int y)prear.x=x;prear.y=y;rear+;/入队 int pop()return front+;/出队 void check(int x,int y) do axy=#;/出队的点标记不能再走 if(x-1=0/只要队列不为空，则一直执行入队出队操作 ,int main(int argc, char* argv) cinmn; for(int i=0;iaij; if(aij=S) b

16、x=i;by=j;aij=.; if(aij=T) ex=i;ey=j;aij=.; check(bx,by); coutsexeyendl; return 0; ,广搜能够得到正确解，但如果不优化，就会出现超时。,迷宫的搜索算法,36,6264:广搜的特殊情况思考：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（0,2）出队，有两条路可走，即（0,3）,(2,2)入队，继续下一点出队。,迷宫的搜索算法,37,6264:广搜的特殊情况思考：,起点：（0,0） 终点（4,4）,队列,队列：先进先出,（1,1）出队，有两条路可走，即（2,1）,(2,2)入队，这时出现了什么问题？ （2

17、,2）出现了两次入队，所以我们要进行优化。,迷宫的搜索算法,38,6264:走出迷宫模拟队列实现广搜参考程序,#include #include using namespace std; char a100100;int s100100,n,m,rear,bx,by,ex,ey,front; structint x;int y;p10000;/队列元素，二维数组元素的下标 void push(int x,int y)prear.x=x;prear.y=y;rear+;/入队 int pop()return front+;/出队 void check(int x,int y) axy=#;/起点标记不能再走 do if(x-1=0/只要队列不为空，则一直执行入队出队操作 ,int main(int argc, char* argv) cinmn; for(int i=0;iaij; if(aij=S) bx=i;by=j;aij=.; if(aij=T) ex=i;ey=j;aij=.; check(bx,by); coutsexeyendl; return 0; ,广搜随着扩展点的增多，会进行大量的搜索，此时，必须尽可能优化或剪枝。,