ACM算法_BFS.pptx

1、ACM算法系列 之广度优先搜索（Breadth-First-Search）,By : Billy_Hwong,资料取自互联网,2,复习DFS算法,思想： 一直往深处走，直到找到解或者走不下去为止 框架： Void DFS(dep,) /dep代表目前DFS的深度 if (找到解|走不下去了) / （- 递归基） return; 枚举下一种情况，DFS(dep+1,) ,例1：POJ 3984,Description 定义一个二维数组：int maze55 = 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,

2、 1, 0, ;它表示一个迷宫，其中的1表示墙壁，0表示可以走的路， 只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 Output 左上角到右下角的最短路径，格式如样例所示。 (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4),寻找一条从入口到出口的通路,TIPS： 在迷宫周围加墙， 避免判断是否出界 （Whyyyyyy?),5,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题-DFS,6,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,

3、7,9,0,9,0,栈,(1,1),(2,1),向下方前进一步,迷宫问题-DFS,7,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),向下方前进一步,迷宫问题-DFS,8,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,9,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,

4、1),向下方前进一步,break,迷宫问题-DFS,10,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,1),向下方前进一步,break,迷宫问题-DFS,11,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,12,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,

5、4,5,6,7,9,0,9,0,向下方 、右方、左方均不能前进，上方是来路，则后退,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,迷宫问题-DFS,13,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,1),向右方、左方均不能前进，下方路不通，上方是来路，则后退,break,迷宫问题-DFS,14,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,

6、9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前进一步,break,迷宫问题-DFS,15,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),(5,3),(5,2),break,迷宫问题-DFS,16,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

7、),(4,1),(5,1),(6,1),(5,2),(5,3),break,迷宫问题-DFS,17,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,4),(5,2),(5,3),(6,3),i,break,迷宫问题-DFS,18,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

8、,5),(5,2),(5,3),(6,3),(6,4),break,迷宫问题-DFS,19,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,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,20,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

9、,1),(3,1),(4,1),(5,1),(8,5),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,迷宫问题-DFS,21,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,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,迷宫问题-DFS,22,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,

10、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),(8,5),(8,6),break,迷宫问题-DFS,23,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),(

11、8,5),(8,6),i,i,(8,7),break,迷宫问题-DFS,24,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,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,25,BFS的简要思想,1.从初始状态S开始，利用规则，生成下一层的状态。 2.顺序检查下一层的所有状态，看是否出现目标状态G。 否则就对该层所有状态节点，分别利用规则。生成再下一层的所有状 态节点。 3.继

12、续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。,科普一下 树的概念,26,DFS的遍历方式,H,A,L,I,F,B,C,D,E,J,G,K,S,遍历形式： 先序 中序 后序 层序,27,BFS遍历方式？,28,BFS框架,通常用队列(先进先出,FIFO)实现 Void bfs() 初始化队列Q. Q=起点s; 标记s为己访问; while (Q非空) 取Q队首元素u; u出队; if (u = 目标状态) 所有与u相邻且未被访问的点进入队列; 标记u为已访问; ,STL：queue,#include 定义一个queue的变量 queue M查看是否为空队列

13、 M.empty() 是的话返回1，不是返回0;从已有元素后面增加元素 M.push()输出现有元素的个数 M.size()显示第一个元素 M.front()显示最后一个元素 M.back()清除第一个元素 M.pop(),重新回到迷宫,30,1,1,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径)-BFS,31,1,1,2,2,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路

14、径)-BFS,32,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,33,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,34,1,1,2,2,3,4,5,3,4,5,5,入口,出口,借助于队列可求得入口到出口的最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,

15、0,9,0,迷宫问题(最短路径)-BFS,35,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,36,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,迷宫问题(最短路径)-BFS,37,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,

16、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,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,39,1,7,8,9,1,2,6,7,8,2,3,4,5,10,3,10,4,5,6,10,5,7,8,9,6,10,入口,出口,借助于队列可求得入口到出口的

17、最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径)-BFS,40,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,41,1,7,8,9,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,5,7,8

18、,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,42,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,43,1,7,8

19、,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,44,小结,DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。 深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头 BFS：使用队列保存未被检测的结点。结点

20、按照宽度优先的次序被访问和进、出队列。 广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方层层深入,BFS的优势就是第N步就把N步所能达到的所有状态都找出来。当然这样子是有代价的，那就是可能需要比DFS多很多的空间。不过BFS的优势在于它能够很快的找到最优解。BFS和DFS一样都是很暴力的算法，因为它们都属于盲目搜索算法。,45,例题2 Oil Deposits,题意：给出一个N*M的矩形区域和每个区域的状态 - 有/没有石油，（定义）如果两个有石油的区域是相邻的（水平、垂直、斜）则认为这是属于同一个oil pocket。 求这块矩形区域一共有

21、多少oil pocket 。,DFS,BFS都能做哦思密达,46,思路： 对于每个有油区域，找出所有与它同属一个oil pocket的有油区域，最后计算一共有多少个oil pocket。 ？怎样去找出所有与它同属一个oil pocket BFS：找到一个起点； 从这个点出发，枚举四周寻找有油区域； 顺序从找到的新的区域出发，循环上述过程，直到没有新的区域加入。 ？怎样去标志同属一个oil pocket的有油区域 设置一个访问标志代表此区域有没有被包含过，这样的话调用BFS的次数就= oil pocket的数目。 当然DFS也是可以这样做的。,47,框架：,Void BFS(int i,int j) 初始化队列Q； while(Q不为空） 取出队首元素u; 枚举元素u的相邻区域， if (此区域有油) 入队;访问标记; Int main() 枚举所有区域，if (此区域有油,综上所述: 得到递归表达式： f(m,n)=1 当 m=1或n=1; f(m,n)=f(m,m) 当mn; f(m,n)=f(m-n,n)+f(m,n-1);,算法效率的分析,此算法的效率比较低，为指数级算法。效率相当之