ACMICPC之搜索篇

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

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

3、之BFSl某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?10/26/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时cd10/26/202185-搜索之BFSv搜索：(0,0,0,0

4、) (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)10/26/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)10/26/2021105-搜索之BFSl搜索在“图”中进行，但

5、图不需要事先建立（“隐式图”）。l搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。l搜索树的结点个数、分枝数、深度，决定着搜索的效率。10/26/2021115-搜索之BFS10/26/2021125-搜索之BFSl普通状态可以用4个整数表示l压缩状态用4个bit表示(char型有8个bit，足够用)。l用广度优先(BFS, Breath First Search) 或 用深度优先(DFS, Depth First Search)10/26/2021135-搜索之BFSl顾名思义，广搜就是“往广了搜”，深搜就是“往深了搜”。l广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近

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

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

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

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

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

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

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

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

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

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

16、出：To get from a1 to h8 takes 6 knight moves. a b c d e f g h12345678h8a110/26/2021375-搜索之BFS a b c d e f g h12345678在23的矩形里：10/26/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 3333210/26/2021395-搜索之

17、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();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(

18、col+diri.y);lqq.push(row+diri.x);lqq.push(ans+1);lmprow+diri.xcol+diri.y=true;llll10/26/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 rowla

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

20、结点(3+5) % 7 = 1(3 5 + 7) % 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 6010/26/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: 910/26/2021475-搜索之BFSl蛇头在上、下、左、右四方向上的探索过程l注意：l蛇不能出界，l不能撞自己，l不能撞石头。10/26/2021485-搜索之BFSl八数码游戏