《搜索之BFS优秀课件》由会员分享，可在线阅读，更多相关《搜索之BFS优秀课件（52页珍藏版）》请在金锄头文库上搜索。
1、SEARCHING STRATEGIESACM/ICPC 之 搜索篇 搜索概论l搜索被称为“通用解题法”，在算法和人工智能中占据重要地位。l但由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。l本节目标：希望同学们对于任意一个问题， 1.很快建立状态空间 2.提出一个合理算法 3.简单估计时空性能9/20/202425-搜索之BFS搜索分类l盲目搜索盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。l启发式搜索启发式搜索：在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向发展，加速问题的求解过程并找到最优解。9/20/202435
2、-搜索之BFS搜索算法l盲目搜索： 1. 广度优先搜索（Breadth First Search） 2. 深度优先搜索（Depth First Search） 3. 纯随机搜索、重复式搜索、迭代加深搜索、 迭代加宽搜索、柱型搜索l启发式搜索： 1. A*算法 2. IDA*算法9/20/202445-搜索之BFS状态空间明确以下概念：明确以下概念：l状态：问题在某一时刻进展状况的数学描述。l状态转移：问题从一种状态到另一种或几种状态的操作。l状态空间：一个“图”，图结点对应于状态，点之间的边对应于状态转移。l搜索：寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。9/20/2
3、02455-搜索之BFS过河问题l某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?9/20/202465-搜索之BFS过河问题（con 1）l状态：建立四元组（人，狗，鸡，米）。用0表示在左岸，1表示在右岸。l起始状态(0,0,0,0)，终止状态(1,1,1,1)l状态转移规则： (a,b,c,d) (1-a,1-b,c,d)（当a=b） (1-a,b,1-c,d)（当a=c） (1-a,b,c,1-d)（当a=d） (1-a,b,c,d)l约束：(a,b,c,d)中，当ab时bc；当ac时cd9/20/2024
4、75-搜索之BFS过河问题（con 2）v搜索：(0,0,0,0) (1,1,0,0) (1,0,1,0) (0,0,1,0) (1,0,1,1) (1,0,0,1) (1,1,1,0) (1,0,0,0)9/20/202485-搜索之BFS过河问题（con 3）v搜索：(1,0,1,1) (0,0,0,1)(1,1,0,1)(0,1,0,1) (1,1,1,1)ok (0,0,1,0)(1,0,1,1)(0,0,1,1) (0,0,1,1)(1,1,1,0) (0,0,1,0)(1,0,1,1)(0,0,1,1) (0,1,0,0)(1,1,0,1)(0,1,0,1) (1,1,1,1)ok
5、 (0,1,1,0)9/20/202495-搜索之BFS过河问题（con 4）l搜索在“图”中进行，但图不需要事先建立（“隐式图”）。l搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。l搜索树的结点个数、分枝数、深度，决定着搜索的效率。9/20/2024105-搜索之BFS过河问题（con 5）9/20/2024115-搜索之BFS过河问题（con 6）l普通状态可以用4个整数表示l压缩状态用4个bit表示(char型有8个bit，足够用)。l用广度优先(BFS, Breath First Search) 或 用深度优先(DFS, Depth First Search)9/20/20241
6、25-搜索之BFSBFS+DFS入门l顾名思义，广搜就是“往广了搜”，深搜就是“往深了搜”。l广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方l深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。9/20/2024135-搜索之BFSBFS思想l1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v2l2.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。l3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均
7、被访问到。/搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E)9/20/2024145-搜索之BFSBFS思想（cont.）l树、图的BFS演示01234859671002145369/20/2024155-搜索之BFSBFS程序基本结构定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;这个结构是普遍适用的。任何非递归非递归的BFS程序都能套进去9/20/2024165-搜索之BFSBFS演示l无向图如下，边权均为无向图如下，边权均为1，求
8、，求V1到到V3的最短路径的最短路径V3V2V4V1V6V59/20/2024175-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1队列结点记录两个信息1：顶点编号2：步数9/20/2024185-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V19/20/2024195-搜索之BF
9、S定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1v109/20/2024205-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1v10V1不是终点9/20/2024215-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，
10、从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v109/20/2024225-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v619/20/2024235-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,
11、输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v219/20/2024245-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V2不是终点v219/20/2024255-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V
12、2V4V1V6V5v21v41v51v61V3v32v219/20/2024265-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v329/20/2024275-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41
13、v51v61V3v32v419/20/2024285-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是终点9/20/2024295-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61
14、V3v32v419/20/2024305-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v519/20/2024315-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v619/20
15、/2024325-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v329/20/2024335-搜索之BFS定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是终点，结束搜索，输出29/
16、20/2024345-搜索之BFS休息一下happy29/20/2024355-搜索之BFS例1 Knight Moves l国际象棋棋盘上有一个马，要从起点跳到指定目标，最少跳几步？输入：输入：a1 h8输出：输出：To get from a1 to h8 takes 6 knight moves. a b c d e f g h12345678h8a19/20/2024365-搜索之BFS跳马规则 a b c d e f g h12345678在23的矩形里：9/20/2024375-搜索之BFSl例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了。To get from a1
17、to e4 takes 3 knight moves. a b c d e f g h123456780 332 13 22 31 233 22 3332 33333332 333329/20/2024385-搜索之BFSlbool in(int a,int b)llif(a0&a0&b=8)lreturn true;lreturn false;llint bfs()llint col,row,i;lwhile(!qq.empty()llcol=qq.front();lqq.pop();lrow=qq.front();lqq.pop();lans=qq.front();lqq.pop();li
18、f(col=a2&row=a3)lreturn ans;lfor(i=0;i8;i+)llif(in(row+diri.x,col+diri.y)&!mprow+diri.xcol+diri.y)llqq.push(col+diri.y);lqq.push(row+diri.x);lqq.push(ans+1);lmprow+diri.xcol+diri.y=true;llll#include #include using namespace std;struct xxxint x,y;xxx dir8=-2,1,-2,-1,-1,-2,1,-2,2,-1,2,1,1,2,-1,2;char
19、c6;int a6;queue qq;bool mp99;int ans;9/20/2024395-搜索之BFSlint main()llregister int i,j;l l while(gets(c)llwhile(!qq.empty()lqq.pop();lfor(i=0;i=8;i+)lfor(j=0;j=8;j+)lmpij=false;la0=c0-a+1;/ start colla1=c1-0;/start rowla2=c3-a+1;/end colla3=c4-0;/end rowlans=0;lqq.push(a0);lqq.push(a1);lqq.push(ans);
20、lmpa1a0=true;lans=bfs();lcoutTo get from c0c1 to c3c4 takes ans knight moves.判断是否有值，除以k的余数为零。 计算中间值取余，不影响结果。 (a + b) % k = ( a % k + b % k) % kn因此只需记录对k的余数。2=k=100，每层结点最多100个，不是指数级增加。9/20/2024445-搜索之BFS4 717 5 -21 15每层最多7个结点 (定义数组)：首先加入起点，17 % 7 = 3扩展第2层结点(3+5) % 7 = 1(3 5 + 7) % 7 =51 2 3 4 5 60+-扩
21、展第3层结点(1+ -21) % 7 = 1(1 -21) % 7 = 1(5+ -21) % 7 = 5(5 -21) % 7 = 51 2 3 4 5 60扩展第4层结点(1+ 15) % 7 = 2(1 15) % 7 = 0(5 + 15) % 7 = 6(5 15) % 7 = 41 2 3 4 5 601 2 3 4 5 609/20/2024455-搜索之BFS例3 Holedox Moving v一条长度为L“贪吃蛇”在n*m的迷宫中，求它走到出口（1，1）的最少步数。 (2L 8;1n,m 20)输入：输入：5 6 44 14 23 23 132 33 33 40 0 0输出
22、：输出：Case 1: 99/20/2024465-搜索之BFSl蛇头在上、下、左、右四方向上的探索过程l注意：l蛇不能出界，l不能撞自己，l不能撞石头。9/20/2024475-搜索之BFS例4：Eightl八数码游戏Input: 2 3 4 1 5 x 7 6 8 Output: ullddrurdllurdruldr 9/20/2024485-搜索之BFS 八数码问题的广度优先搜索八数码问题的广度优先搜索 9/20/2024495-搜索之BFSl分析：所给输入为初始状态，终态是1 2 3 4 5 6 7 8 x。l将x当作9，开一个数组a9！，存每种状态l采取双向BFS，前后搜同时进行。
23、l初始时每种状态标记为0. 在数组a里查找从前边搜到的状态，标记是0， 则置标记为1；标记是-1，则说明这是个前后搜重合状态，同时说明input有解。 在数组a里查找从后边搜到的状态，标记是0，则置为-1；标记是1，则也说明这是个前后搜重合状态，同时说明input有解。9/20/2024505-搜索之BFSBFS练习lzju 1091Knight Moveslzju 1047Image Perimeterslzju 1103Hike on a Graphlzju 1649Rescue lzju 1310Robot lzju 1136Multiplelzju 1530Find The Multiplelzju 1301The New Villa9/20/2024515-搜索之BFS此课件下载可自行编辑修改，供参考！此课件下载可自行编辑修改，供参考！感谢你的支持，我们会努力做得更好！感谢你的支持，我们会努力做得更好！
