最新5-搜索之BFS

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

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

3、状态。 5/3/202165-搜索之BFS l某人要带一条狗、一只鸡、一箩米过河，但 小船除需要人划外，最多只能载一物过河， 而当人不在场时，狗要咬鸡、鸡要吃米。问 此人应如何过河? 5/3/202175-搜索之BFS 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时cd 5/3/2

4、02185-搜索之BFS 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) 5/3/202195-搜索之BFS 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) 5/3

5、/2021105-搜索之BFS l搜索在“图”中进行，但图不需要事先建立 （“隐式图”）。 l搜索过程就是对图的遍历过程，可以得到一 棵“搜索树”。 l搜索树的结点个数、分枝数、深度，决定着 搜索的效率。 5/3/2021115-搜索之BFS 5/3/2021125-搜索之BFS l普通状态可以用4个整数表示 l压缩状态用4个bit表示(char型有8个bit， 足够用)。 l用广度优先(BFS, Breath First Search) 或 用深度优先(DFS, Depth First Search) 5/3/2021135-搜索之BFS l顾名思义，广搜就是“往广了搜”，深搜就 是“往深了

6、搜”。 l广搜例子:你的眼镜掉在地上以后，你趴在 地板上找。你总是先摸最接近你的地方，如 果没有，再摸远一点的地方 l深搜例子：走迷宫，你没有办法用分身术来 站在每个走过的位置。不撞南山不回头。 5/3/2021145-搜索之BFS l1.从图中某顶点v0出发，在访问了v0之后，搜索v0 的(所有未被访问的)邻接顶点v1.v2 l2.依次从这些邻接顶点出发，广搜图中其它顶点， 直至图中所有已被访问的顶点的邻接顶点都被访问 到。 l3.若此时图中还有未被访问到的顶点，则再选择其 中之一作为v0重复上述过程。直到图中所有顶点 均被访问到。 /搜索过程没有回溯，是一种牺牲空间换取时 间的方法。时间复

7、杂度：O(V+E) 5/3/2021155-搜索之BFS l树、图的BFS演示 0 123 4 8 5 9 67 10 0 2 1 45 3 6 5/3/2021165-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; 这个结构是普遍适用 的。任何非递归非递归的 BFS程序都能套进去 5/3/2021175-搜索之BFS l无向图如下，边权均为无向图如下，边权均为1，求，求V1到到V3的最短路径的最短路径 V3 V2 V4V1 V6 V5

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

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

10、标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 v1 0 5/3/2021235-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 5/3/2021245-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空)

11、取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 v2 1 5/3/2021255-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V2不是终点 v2 1 5/3/2021265-搜索之BFS 定义

12、一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v2 1 5/3/2021275-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6

13、1 V3 v3 2 5/3/2021285-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v4 1 5/3/2021295-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V

14、2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v4 1 V4不是终点 5/3/2021305-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v4 1 5/3/2021315-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩

15、展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v5 1 5/3/2021325-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v6 1 5/3/2021335-搜索之BFS 定义一个队列; 起始点加入队列; while(队

16、列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v3 2 5/3/2021345-搜索之BFS 定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添到队尾; 若循环中找到目标,输出结果; 否则输出无解; v1 0 V2 V4V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v3 2 V3是终点，结

17、束搜索， 输出2 5/3/2021355-搜索之BFS happy2 5/3/2021365-搜索之BFS l国际象棋棋盘上有一个马，要从起点跳到指 定目标，最少跳几步？ 输入：输入： a1 h8 输出：输出： To get from a1 to h8 takes 6 knight moves. a b c d e f g h 1 2 3 4 5 6 7 8 h8 a1 5/3/2021375-搜索之BFS a b c d e f g h 1 2 3 4 5 6 7 8 在23的矩形里： 5/3/2021385-搜索之BFS l例如：从a1到e4 当目标出现在所扩展出的 结点里，结果就找到了。

18、 To get from a1 to e4 takes 3 knight moves. a b c d e f g h 1 2 3 4 5 6 7 8 0 3 3 2 1 3 2 2 3 1 2 3 3 2 2 3 3 3 2 3 3 3 3 3 3 3 2 3 3 3 3 2 5/3/2021395-搜索之BFS lbool in(int a,int b) l lif(a0 lreturn false; l lint bfs() l lint col,row,i; lwhile(!qq.empty() l lcol=qq.front(); lqq.pop(); lrow=qq.front()

19、; lqq.pop(); lans=qq.front(); lqq.pop(); lif(col=a2 lfor(i=0;i8;i+) l lif(in(row+diri.x,col+diri.y) lqq.push(row+diri.x); lqq.push(ans+1); lmprow+diri.xcol+diri.y=true; l l l l 5/3/2021405-搜索之BFS lint main() l lregister int i,j; l l while(gets(c) l lwhile(!qq.empty() lqq.pop(); lfor(i=0;i=8;i+) lfor

20、(j=0;j=8;j+) lmpij=false; la0=c0-a+1;/ start col la1=c1-0;/start row la2=c3-a+1;/end col la3=c4-0;/end row lans=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)

21、% k n因此只需记录对k的余数。2=k=100，每 层结点最多100个，不是指数级增加。 5/3/2021455-搜索之BFS 4 7 17 5 -21 15 每层最多7个结点 (定义数组)： 首先加入起点，17 % 7 = 3 扩展第2层结点 (3+5) % 7 = 1 (3 5 + 7) % 7 =5 1 2 3 4 5 60 +- 扩展第3层结点 (1+ -21) % 7 = 1 (1 -21) % 7 = 1 (5+ -21) % 7 = 5 (5 -21) % 7 = 5 1 2 3 4 5 60 扩展第4层结点 (1+ 15) % 7 = 2 (1 15) % 7 = 0 (5

22、+ 15) % 7 = 6 (5 15) % 7 = 4 1 2 3 4 5 60 1 2 3 4 5 60 5/3/2021465-搜索之BFS v一条长度为L“贪吃蛇”在n*m的迷宫中，求 它走到出口（1，1）的最少步数。 (2L 8;1n,m 20) 输入：输入： 5 6 4 4 1 4 2 3 2 3 1 3 2 3 3 3 3 4 0 0 0 输出：输出： Case 1: 9 5/3/2021475-搜索之BFS l蛇头在上、下、左、右四方向上的探索过程 l注意： l蛇不能出界， l不能撞自己， l不能撞石头。 5/3/2021485-搜索之BFS l八数码游戏 5/3/2021495-搜索之BFS 2 2 1 7 8 6 3 4 5 8 2 7 3 6 4 5 1 8 2 7 1 6 3 4 5 22 8 2 76 3 4 5 1 23 8 2 76 3 4 5 1 14 6 8 7 6 3 4 5 1 2 7 8 7 3