ACM算法设计-BFS(广度搜索)-DFS入门(深度搜索)详解.ppt

1、2020/7/15,ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解,BFS算法,by plato,3,复习DFS算法,思想： 一直往深处走，直到找到解或者走不下去为止 框架： DFS(dep,) /dep代表目前DFS的深度 if (找到解|走不下去了) return; 枚举下一种情况，DFS(dep+1,) ,4,DFS的遍历方式,H,A,L,I,F,B,C,D,E,J,G,K,S,5,存在其他的遍历方式？,6,BFS的思想,1.从初始状态S开始，利用规则，生成下一层的状态。 2.顺序检查下一层的所有状态，看是否出现目标状态G。 否则就对该层所有状态节点，分别利用规则。生成再下一层

2、的所有状 态节点。 3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。 按层次的顺序来遍历搜索树,7,BFS框架,通常用队列(先进先出,FIFO)实现 初始化队列Q. Q=起点s; 标记s为己访问; while (Q非空) 取Q队首元素u; u出队; if (u = 目标状态) 所有与u相邻且未被访问的点进入队列; 标记u为已访问; ,8,寻找一条从入口到出口的通路,迷宫问题,9,东,南,北(上),西(左),前进方向：上(北)、下(南)、左(西)、右(东),首先从下方开始，按照逆时针方向搜索下一步可能前进的位置,迷宫问题-DFS,10,入口,出口,在迷宫

3、周围加墙，避免判断是否出界,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题-DFS,11,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈,迷宫问题-DFS,12,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),向下方前进一步,迷宫问题-DFS,13,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),i,(3,1),向下方前进一

4、步,迷宫问题-DFS,14,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(4,1),(3,1),i,向下方前进一步,break,迷宫问题-DFS,15,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(5,1),(3,1),(4,1),向下方前进一步,break,迷宫问题-DFS,16,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(6,1),(3,1),(4,1),

5、(5,1),向下方前进一步,break,迷宫问题-DFS,17,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),向下方前进一步,break,18,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方 、右方、左方均不能前进，上方是来路，则后退,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,迷宫问题-DFS,19,i,i,i,i

6、,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),向右方、左方均不能前进，下方路不通，上方是来路，则后退,break,迷宫问题-DFS,20,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前进一步,break,迷宫问题-DFS,21,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5

7、,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,3),(5,2),break,迷宫问题-DFS,22,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(5,2),(5,3),break,迷宫问题-DFS,23,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向

8、右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,4),(5,2),(5,3),(6,3),i,break,迷宫问题-DFS,24,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,5),(5,2),(5,3),(6,3),(6,4),break,迷宫问题-DFS,25,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4

9、,5,6,7,9,0,9,0,向下方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(7,5),(5,2),(5,3),(6,3),(6,4),(6,5),break,迷宫问题-DFS,26,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,5),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,迷宫问题-DFS,27,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2

10、,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,迷宫问题-DFS,28,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,7),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5)

11、,(8,5),(8,6),break,迷宫问题-DFS,29,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前进一步，到达出口,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),i,i,(8,7),break,迷宫问题-DFS,30,i,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,9,0,用栈保存了路径,栈,(1,1),(2,1),(3

12、,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),(8,7),迷宫问题-DFS,31,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,32,1,1,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,33,1,1,2,2,入口,出口,借助于队列可求得入口到出口的最短路径

13、(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,34,1,1,2,2,3,3,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,35,1,1,2,2,3,4,3,4,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,36,1,1,2,2,3,4,5,3,4,5,5,入口,出口,借助于队

14、列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,37,1,1,2,6,2,3,4,5,3,4,5,6,5,6,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,38,1,7,1,2,6,7,2,3,4,5,3,4,5,6,5,7,6,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫

15、问题(最短路径)-BFS,39,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,6,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,40,1,7,8,9,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,9,6,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,41,1,7,8,9,1,2,6,7,8,2,3,

16、4,5,10,3,10,4,5,6,10,5,7,8,9,6,10,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,42,1,7,8,9,1,2,6,7,8,2,3,4,5,10,11,3,11,10,11,4,5,6,10,11,5,7,8,9,6,10,11,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,43,1,7,8,9,1,2,6,7

17、,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,5,7,8,9,6,10,12,11,12,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,44,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5

18、,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,45,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,46,小结,DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。 类似于树的先根遍历 深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。 BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。 类似于树的按层次遍历的过程 广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是