搜索之BFS（课堂PPT）

1、SEARCHING STRATEGIES3/5/20222.l搜索被称为“通用解题法”，在算法和人工智能中占据重要地位。l但由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。l本节目标：希望同学们对于任意一个问题， 1.很快建立状态空间 2.提出一个合理算法 3.简单估计时空性能3/5/20223.l盲目搜索盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。l启发式搜索启发式搜索：在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向发展，加速问题的求解过程并找到最优解。3/5/20224.l盲目搜索： 1. 广度优先搜索（Bread

2、th First Search） 2. 深度优先搜索（Depth First Search） 3. 纯随机搜索、重复式搜索、迭代加深搜索、 迭代加宽搜索、柱型搜索l启发式搜索： 1. A*算法 2. IDA*算法3/5/20225.明确以下概念：明确以下概念：l状态：问题在某一时刻进展状况的数学描述。l状态转移：问题从一种状态到另一种或几种状态的操作。l状态空间：一个“图”，图结点对应于状态，点之间的边对应于状态转移。l搜索：寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。3/5/20226.l某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当

3、人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?3/5/20227.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时cd3/5/20228.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) (

4、1,0,0,0)3/5/20229.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 (0,1,1,0)3/5/202210.l搜索在“图”中进行，但图不需要事先建立（“隐式图”）。l搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。l搜索树的结点个数、分枝数、深度，决定着搜索的效率。3/5/202211.3

5、/5/202212.l普通状态可以用4个整数表示l压缩状态用4个bit表示(char型有8个bit，足够用)。l用广度优先(BFS, Breath First Search) 或 用深度优先(DFS, Depth First Search)3/5/202213.l顾名思义，广搜就是“往广了搜”，深搜就是“往深了搜”。l广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方l深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。3/5/202214.l1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点

6、v1.v2l2.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。l3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。/搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E)3/5/202215.l树、图的BFS演示01234859671002145363/5/202216.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;这个结构是普遍适用的。任何非递

7、归非递归的BFS程序都能套进去3/5/202217.l无向图如下，边权均为无向图如下，边权均为1，求，求V1到到V3的最短路径的最短路径V3V2V4V1V6V53/5/202218.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1队列结点记录两个信息1：顶点编号2：步数3/5/202219.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输

8、出结果;否则输出无解;v10V13/5/202220.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1v103/5/202221.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V1v10V1不是终点3/5/202222.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态

9、,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61v103/5/202223.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v613/5/202224.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否

10、则输出无解;v10V2V4V1V6V5v21v41v51v61v213/5/202225.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V2不是终点v213/5/202226.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V

11、3v32v213/5/202227.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v323/5/202228.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v413/5/202229.定义一个队列;起始点加入队

12、列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是终点3/5/202230.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v413/5/202231.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点;

13、若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v513/5/202232.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v613/5/202233.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点

14、,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v323/5/202234.定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10V2V4V1V6V5v21v41v51v61V3v32v32V3是终点，结束搜索，输出23/5/202235.happy23/5/202236.l国际象棋棋盘上有一个马，要从起点跳到指定目标，最少跳几步？输入：输入：a1 h8输出：输出：To get from a

15、1 to h8 takes 6 knight moves. a b c d e f g h12345678h8a13/5/202237. a b c d e f g h12345678在23的矩形里：3/5/202238.l例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了。To get from a1 to e4 takes 3 knight moves. a b c d e f g h123456780 332 13 22 31 233 22 3332 33333332 333323/5/202239.lbool in(int a,int b)llif(a0&a0&

16、;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();lif(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+d

17、iri.x);lqq.push(ans+1);lmprow+diri.xcol+diri.y=true;llll3/5/202240.lint main()llregister int i,j;ll 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.

18、push(ans);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个，不是指数级增加。3/5/202245.4 717 5 -21 15每层最多7个结点 (定义数组)：首先加入起点，17 % 7 = 3扩展第2层结点(3+5) % 7 = 1(3 5 + 7) % 7 =51 2 3 4 5 60+

19、-扩展第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 603/5/202246.v一条长度为L“贪吃蛇”在n*m的迷宫中，求它走到出口（1，1）的最少步数。 (2L 8;1n,m 20)输入：输入：5 6 44 14 23 23 132 33 33 40 0 0输出：输出：Case 1: 93/5/202247.l蛇头在上、下、左、右四方向上的探索过程l注意：l蛇不能出界，l不能撞自己，l不能撞石头。3/5/202248.l八数码游戏3/5/202249.22