广度优先搜索课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,广度优先搜索,广度优先搜索,1,引入问题why queue,搜索广度优先搜索,队列的维护,什么是队列？,引入问题why queue搜索广度优先搜索,2,队列,队列是限定在一端进行插入，另一端进行删除的特殊的线性表。,删除的一端称为队首，插入的一端称为队尾。,具体事例：排队买票，后来的人排在队尾（插入），队首的人离开（删除）。,队列队列是限定在一端进行插入，另一端进行删除的特殊的线性表。,3,队列的特点,线性,队头读 队尾写,先进先出,队列的特点线性,4,队列的定义,静态数组,Type arr=array1.n of integer;,queue=record,vec:arr;,front,rear:integer;,end;,Var q:queue;,Var queue:arr;,front,rear:integer;,队列的定义静态数组Var queue:arr;,5,队列的基本操作,操作,静态数组(A,f,r),建立空队列,测试队列是否为空,入队(insert),出队(dele),尾插法,F:=0;r:=0,Fr,R:=r+1;ar:=x;,If f=0 then f:=1;,X:=af;f:=f+1;,和约定有关,队列的基本操作操作静态数组(A,f,r)建立空队列测试队列是,6,深度、广度优先搜索,在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。,深度、广度优先搜索在搜索过程中，我们把每个状态看作是结点，把,7,深度、广度优先搜索,初始状态对应根结点，目标状态对应目标结点。问题的一个解就是一条从根结点到目标结点的路径。,对“搜索树”的搜索算法类似于树的遍历，通常有两种不同的实现方法：,广度优先搜索(BFS),深度优先搜索(DFS),深度、广度优先搜索初始状态对应根结点，目标状态对应目标结点。,8,广度优先搜索,BFS每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。,广度优先搜索BFS每次都先将搜索树某一层的所有节点全部访问完,9,广度优先搜索,一般来说，BFS使用队列来实现。,BFS一般用来求最优解。,在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及由父状态转换过来所执行的操作。,Data,OP,Pre,广度优先搜索一般来说，BFS使用队列来实现。DataOPPr,10,广度优先搜索算法,初始状态入队,op:=1,对队首状态进行操作op，得到新状态；,检查此状态是否出现过，如未出现则将此状态入队；,如果此状态为目标状态，则输出；,如所有操作都已完成，则队首出队，否则op:=op+1，返回(3)。,广度优先搜索算法初始状态入队,11,广度优先搜索的程序框架,procedure bfs;,begin,head:=0;tail:=1;datatail.data:=初始状态;,datatail.op:=0;datatail.pre:=0;flag:=false;,repeat,inc(head);,while datahead还可以扩展 do begin,new:=op(datahead.state);,if new已经出现 then continue;,inc(tail);datatail.data:=new;,datatail.op:=op;datatail.pre:=head;,if new是目标状态 then begin flag:=true;break;end;,end;,until(tail=head)or flag,if flag then output else writeln(No Answer);,end;,广度优先搜索的程序框架procedure bfs;,12,DFS or BFS,搜索方式,时间,空间,适用问题,DFS,O(c,k,),O(k),必须完全遍历或不要求解的深度最小,BFS,O(c,d,),O(c,d,),解靠近根或要求解的深度最小,k表示树的深度；d表示解的深度；dk,DFS or BFS搜索方式时间空间适用问题DFSO(ck),13,从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：,现将上面的路线图，按记录结构存储如下,：,队列应用,从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：,14,请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。,请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算,15,从列表中可以看出出口关卡号（17）的被访问路径最短的是：(17)(16)(19)(18)(1)开始,关卡（最短路径）,I：=1；,WHILE NOI 17 DO I:=I+1 ;,REPEAT,WRITE(,NOI,);WRITE();,I:=PREI;,UNTIL I=0；,从列表中可以看出出口关卡号（17）的被访问路径最短的是：(1,16,编一个程序，找出一条通过迷宫的路径。这里有黑色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。,迷宫问题,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,入口,出口,编一个程序，找出一条通过迷宫的路径。这里有黑色方块的,17,大小：8 5 入口:2 1 出口 8 4 则路径如(2),*,.*入口$*,*.*$*,*.*.$*,*.*.$*,*.*.$*,*.*$*,*.*.$*,出口,(1 )(2 ),大小：8 5 入口:2 1 出口 8,18,迷宫问题-,找出一个从入口到出口的最短路径（八个方向）,0,1,1,1,0,1,1,1,1,0,1,0,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,1,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,迷宫问题-找出一个从入口到出口的最短路径（八个方向）01,19,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,总行数：0m+1,总列数：0n+1,111111111110111011111101010101,20,8个方向表示可以用数组说明：,1,0,1,2,1,1,3,1,0,4,1,-1,5,0,-1,6,-1,-1,7,-1,0,8,-1,1,如何记录探索的踪迹？,队列,序号,1,2,3,4,5,6,X,1,2,3,3,3,2,Y,1,2,3,1,4,4,pre,0,1,2,2,3,3,8个方向表示可以用数组说明：10121131041-150-,21,如何防止重复探索：将迷宫中的0替换为-1,队列中入队、出队情况如下表：,迷宫问题,如何防止重复探索：将迷宫中的0替换为-1迷宫问题,22,sq1.x:=1;sq1.y:=1;sq1.pre:=0 ;,front:=1;rear:=1;mg1,1:=-1 ;,while front=rear do,x:=sqfront.x;y:=sqfront.y;,for v:=1 to 8 do,I:=x+zv.x;j:=y+zv.y;,if mgI,j=0 then,rear:=rear+1;sqrear.pre:=front;,sqrear.x:=I;sqrear.y:=j;,mgI,j:=-1;,if (i=m)and(j=n)then print;,front:=front+1 ;,sq1.x:=1;sq1.y:=1;sq1.,23,打印最短路径：,打印最短路径：,Procedure print(var sq:sqtype;rear:integer);,begin,k:=rear;,repeat,writeln(,sqk.x,sqk.y,);,k:=sqk.pre;,until k=0 ;,end;,打印最短路径：打印最短路径：,24,迷宫问题,其实本题也可以用深度优先搜索来做，但是正如前面所说的，因为要求最优解，深度优先搜索需要将整个搜索树都搜索完。,宽度优先搜索搜到的第一个解一定是最优解，所以找到解后就可以停止了。,迷宫问题其实本题也可以用深度优先搜索来做，但是正如前面所说的,25,应用,现要找出一条从A到H经过城市最少的一条路径。,应用现要找出一条从A到H经过城市最少的一条路径。,26,广度优先遍历:A,广度优先遍历:A ,27,具体过程如下：,（1）将城市A入队，队首、队尾都为1。,（2）将队首所指的城市所有可直通的城市入队（,如何判断？,），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。,A,H,具体过程如下：AH,28,宽搜基本框架,F,r,队列初始化；,While f=r do,取队首；,扩展+判重+入队；,宽搜基本框架F,r,队列初始化；,29,给出一个整数n（n2000）和k个变换规则（k15）规则：1个数字可以变换成另1个数字；规则中，右边的数字不能为零。例如：n=234，k=2规则为 2 5 3 6 234经过变换后可能产生出的整数为（包括原数）234 534 264 564求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。,应用产生数,给出一个整数n（n2000）和k个变换规则（k15）,30,【问题分析】本题考察了同学们三方面的能力：数的表示，如何处理；转换规则如何表示；队列的应用，包括入队、出队以及队的查找。,注意点：数以字符串的形式输入，为了计算方便，经过类型转换存入整型数组中；对数的比较也很困难，只能逐位比较，处理时用一个队列q，开始时队列q中只有n。,【问题分析】本题考察了同学们三方面的能力：,31,有10升油在10升的容器中，另有两个7升和3升的空容器，现要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油。,题解 三个容器可以看作三个变量 C10，C7，C3，每次倒油的可能性只有如下六种情况：,C10 向 C7 倒油 C10 向 C3 倒油,C7 向 C10 倒油 C7 向 C3 倒油,C3 向 C10 倒油 C3 向 C7 倒油,应用倒油,有10升油在10升的容器中，另有两个7升和3升的空容器，现要,32,从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态，许多是已经出现过的状态。例如初始状态（10,0,0）表示 C10=10，C7=0，C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,0）和（7,0,3）。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,10,3,7,0,3,7,6,4,6,4,9,1,9,1,2,8,2,8,5,0,7,0,7,4,3,4,3,1,6,1,6,0,7,7,0,5,2,5,0,0,3,3,3,0,0,3,3,0,0,3,1,2,1,2,3,0,0,0,1,1,2,2,3,5,6,7,8,9,10,11,12,13,14,15,16,17,C10,C7,C3,PRE,从一个容器状态（三个容器中油的容量）看，虽然有可能经,33,当倒油产生出第19个容器状态时已达到了题解的目的。这时只要根据pre中的状态号17可以回溯到第17个容器状态的pre值为15，依次可再获得13，11，9，7，5，2，1容器状态号，从而即可得到解题的倒油过程（共倒9次）,。,注意,从一个容