搜索之BFS.ppt

SEARCHING STRATEGIES,ACM/ICPC 之 搜索篇,2019/9/23,2,搜索概论,搜索被称为“通用解题法”，在算法和人工智能中占据重要地位。 但由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。 本节目标：希望同学们对于任意一个问题， 1.很快建立状态空间 2.提出一个合理算法 3.简单估计时空性能,2019/9/23,3,搜索分类,盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。 启发式搜索：在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向发展，加速问题的求解过程并找到最优解。,2019/9/23,4,搜索算法,盲目搜索： 1. 广度优先搜索（Breadth First Search） 2. 深度优先搜索（Depth First Search） 3. 纯随机搜索、重复式搜索、迭代加深搜索、 迭代加宽搜索、柱型搜索 启发式搜索： 1. A*算法 2. IDA*算法,2019/9/23,5,状态空间,明确以下概念： 状态：问题在某一时刻进展状况的数学描述。 状态转移：问题从一种状态到另一种或几种状态的操作。 状态空间：一个“图”，图结点对应于状态，点之间的边对应于状态转移。 搜索：寻找一种可行的操作序列，从起始状态经过一系列状态转移，达到目标状态。,2019/9/23,6,过河问题,某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河?,2019/9/23,7,过河问题（con 1）,状态：建立四元组（人，狗，鸡，米）。用0表示在左岸，1表示在右岸。 起始状态(0,0,0,0)，终止状态(1,1,1,1) 状态转移规则： (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) 约束：(a,b,c,d)中，当ab时bc；当ac时cd,2019/9/23,8,过河问题（con 2）,搜索： (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),2019/9/23,9,过河问题（con 3）,搜索： (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),2019/9/23,10,过河问题（con 4）,搜索在“图”中进行，但图不需要事先建立（“隐式图”）。 搜索过程就是对图的遍历过程，可以得到一棵“搜索树”。 搜索树的结点个数、分枝数、深度，决定着搜索的效率。,2019/9/23,11,过河问题（con 5）,2019/9/23,12,过河问题（con 6）,普通状态可以用4个整数表示 压缩状态用4个bit表示(char型有8个bit，足够用)。 用广度优先(BFS, Breath First Search) 或 用深度优先(DFS, Depth First Search),2019/9/23,13,BFS+DFS入门,顾名思义，广搜就是“往广了搜”，深搜就是“往深了搜”。 广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方 深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。,2019/9/23,14,BFS思想,1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v2 2.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。 3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。 /搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E),2019/9/23,15,BFS思想（cont.）,树、图的BFS演示,0,1,2,3,4,8,5,9,6,7,10,0,2,1,4,5,3,6,2019/9/23,16,BFS程序基本结构,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,这个结构是普遍适用的。任何非递归的BFS程序都能套进去,2019/9/23,17,BFS演示,无向图如下，边权均为1，求V1到V3的最短路径,2019/9/23,18,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,V1,队列结点记录两个信息 1：顶点编号 2：步数,2019/9/23,19,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,V1,2019/9/23,20,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V1,2019/9/23,21,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V1,V1不是终点,2019/9/23,22,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,2019/9/23,23,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,2019/9/23,24,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,2019/9/23,25,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V2不是终点,2019/9/23,26,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,27,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,28,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,29,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,V4不是终点,2019/9/23,30,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,31,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,32,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,33,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,2019/9/23,34,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解;,v1,0,V2,V4,V1,V6,V5,V3,V3是终点，结束搜索， 输出2,2019/9/23,35,休息一下,happy2,2019/9/23,36,例1 Knight Moves,国际象棋棋盘上有一个马，要从起点跳到指定目标，最少跳几步？,输入： a1 h8 输出： To get from a1 to h8 takes 6 knight moves.,2019/9/23,37,跳马规则,a b c d e f g h,1 2 3 4 5 6 7 8,在23的矩形里：,2019/9/23,38,例如：从a1到e4,当目标出现在所扩展出的结点里，结果就找到了。,To get from a1 to e4 takes 3 knight moves.,2019/9/23,39,bool in(int a,int b) if(a0 ,2019/9/23,40,int main() register int i,j; while(gets(c) while(!qq.empty() qq.pop(); for(i=0;i=8;i+) for(j=0;j=8;j+) mpij=false; a0=c0-a+1;/ start col a1=c1-0;/start row a2=c3-a+1;/end col a3=c4-0;/end row ans=0; qq.push(a0); qq.push(a1); qq.push(ans); mpa1a0=true; ans=bfs(); cout“To get from “c0c1“ to “c3c4“ takes “ans“ knight moves.“endl; return 0; ,2019/9/23,41,双向BFS,从起点、终点同时开始,双向BFS,有效地提高了时空效率。,从起点找2步能跳到的点,从终点找1步能跳到的点,2019/9/23,42,例2 Divisibility,输入N、K,然后输入N个整数，N个整数可列出若干加减运算式；若存在一个算式，它的值能被K整除,输出“Divisible”，否则输出“Not divisible”.,输入： 2 4 7 17 5 -21 15 4 5 17 5 -21 15,输出： Divisible Not divisible,2019/9/23,43,17，5，-21，15,17,5,5,-21,-21,-21,-21,15,15,15,15,15,15,15,15,+,+,+,17 + 5 + -21 + 15,+,+,+,+,-,-,-,-,-,-,-,17 - 5 + -21 - 15,2019/9/23,44,最坏情况N=10000，二叉树有10000层，结点总数210000-1。不可能枚举所有表达式,本题的目标：判断叶子结点上是否有值能被k 整除=判断是否有值，除以k的余数为零。 计算中间值取余，不影响结果。 (a + b) % k = ( a % k + b % k) % k,因此只需记录对k的余数。2=k=100，每层结点最多100个，不是指数级增加。,2019/9/23,45,4 7 17 5 -21 15,每层最多7个结点 (定义数组)：,首先加入起点，17 % 7 = 3,扩展第2层结点 (3+5) % 7 = 1 (3 5 + 7) % 7 =5,+,-,扩展第3层结点 (1+ -21) % 7 = 1 (1 -21) % 7 = 1 (5+ -21) % 7 = 5 (5 -21) % 7 = 5,扩展第4层结点 (1+ 15) % 7 = 2 (1 15) % 7 = 0 (5 + 15) % 7 = 6 (5 15) % 7 = 4,2019/9/23,46,例