最新5搜索之BFS

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

2、fsl盲目搜索： 1. 广度优先搜索（breadth first search） 2. 深度优先搜索（depth first search） 3. 纯随机搜索、重复式搜索、迭代加深搜索、 迭代加宽搜索、柱型搜索l启发式搜索： 1. a*算法 2. ida*算法11/1/202155-搜索之bfs明确以下概念：明确以下概念：l状态：问题在某一时刻进展状况的数学描述。l状态转移：问题从一种状态到另一种或几种状态的操作。l状态空间：一个“图”，图结点对应于状态，点之间的边对应于状态转移。l搜索：寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。11/1/202165-搜索之bfsl

3、某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?11/1/202175-搜索之bfsl状态：建立四元组（人，狗，鸡，米）。用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时cd11/1/202185-搜索之bfsv搜索：(0,0,0,0) (1,1,

4、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)11/1/202195-搜索之bfsv搜索：(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)11/1/2021105-搜索之bfsl搜索在“图”中进行，但图不需要事先建立（

5、“隐式图”）。l搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。l搜索树的结点个数、分枝数、深度，决定着搜索的效率。11/1/2021115-搜索之bfs11/1/2021125-搜索之bfsl普通状态可以用4个整数表示l压缩状态用4个bit表示(char型有8个bit，足够用)。l用广度优先(bfs, breath first search) 或 用深度优先(dfs, depth first search)11/1/2021135-搜索之bfsl顾名思义，广搜就是“往广了搜”，深搜就是“往深了搜”。l广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸

6、远一点的地方l深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。11/1/2021145-搜索之bfsl1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v2l2.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。l3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。/搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：o(v+e)11/1/2021155-搜索之bfsl树、图的bfs演示012348596710021453611/1/2

7、021165-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;这个结构是普遍适用的。任何非递归非递归的bfs程序都能套进去11/1/2021175-搜索之bfsl无向图如下，边权均为无向图如下，边权均为1，求，求v1到到v3的最短路径的最短路径v3v2v4v1v6v511/1/2021185-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循

8、环中找到目标,输出结果;否则输出无解;v10v1队列结点记录两个信息1：顶点编号2：步数11/1/2021195-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v111/1/2021205-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v1v1011/1/2021215-搜索之bfs定义

9、一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v1v10v1不是终点11/1/2021225-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v1011/1/2021235-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是

10、所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v6111/1/2021245-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v2111/1/2021255-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点

11、,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v2不是终点v2111/1/2021265-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v3v32v2111/1/2021275-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环

12、中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v3v3211/1/2021285-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v3v32v4111/1/2021295-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出

13、无解;v10v2v4v1v6v5v21v41v51v61v3v32v41v4不是终点11/1/2021305-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v3v32v4111/1/2021315-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10

14、v2v4v1v6v5v21v41v51v61v3v32v5111/1/2021325-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v3v32v6111/1/2021335-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v2

15、1v41v51v61v3v32v3211/1/2021345-搜索之bfs定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾;若循环中找到目标,输出结果;否则输出无解;v10v2v4v1v6v5v21v41v51v61v3v32v32v3是终点，结束搜索，输出211/1/2021355-搜索之bfshappy211/1/2021365-搜索之bfsl国际象棋棋盘上有一个马，要从起点跳到指定目标，最少跳几步？输入：输入：a1 h8输出：输出：to get from a1 to h8 takes 6 knig

16、ht moves. a b c d e f g h12345678h8a111/1/2021375-搜索之bfs a b c d e f g h12345678在23的矩形里：11/1/2021385-搜索之bfsl例如：从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 3333211/1/2021395-搜索之bfslbool in(int a,int b)llif(a0&a0

17、&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(r

18、ow+diri.x);lqq.push(ans+1);lmprow+diri.xcol+diri.y=true;llll11/1/2021405-搜索之bfslint 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.p

19、ush(a1);lqq.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个，不是指数级增加。11/1/2021455-搜索之bfs4 717 5 -21 15每层最多7个结点 (定义数组)：首先加入起点，17 % 7 = 3扩展第2层结点(3+5) % 7 = 1(3 5 + 7)

20、 % 7 =51 2 3 4 5 60+-扩展第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 6011/1/2021465-搜索之bfsv一条长度为l“贪吃蛇”在n*m的迷宫中，求它走到出口（1，1）的最少步数。 (2l 8;1n,m 20)输入：输入：5 6 44 14 23 23 132 33 33 40 0 0输出：输出：case 1: 911/1/2021475-搜索之bfsl蛇头在上、下、左、右四方向上的探索过程l注意：l蛇不能出界，l不能撞自己，l不能撞石头。11/1/2021485-搜索之bfsl八数码游戏