《广度优先搜索陈鹏ppt课件.ppt》由会员分享，可在线阅读，更多相关《广度优先搜索陈鹏ppt课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、广度优先搜索,引入问题why queue,搜索广度优先搜索队列的维护什么是队列？,队列,队列是限定在一端进行插入，另一端进行删除的特殊的线性表。删除的一端称为队首，插入的一端称为队尾。具体事例：排队买票，后来的人排在队尾（插入），队首的人离开（删除）。,队列的特点,线性队头读 队尾写先进先出,队列的定义,静态数组Type arr=array1.n of integer;queue=record vec:arr;front,rear:integer;end;Var q:queue;,Var queue:arr;front,rear:integer;,队列的基本操作,F:=0;r:=0,Fr,R:
2、=r+1;ar:=x;If f=0 then f:=1;,X:=af;f:=f+1;,和约定有关,深度、广度优先搜索,在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。,深度、广度优先搜索,初始状态对应根结点，目标状态对应目标结点。问题的一个解就是一条从根结点到目标结点的路径。对“搜索树”的搜索算法类似于树的遍历，通常有两种不同的实现方法：广度优先搜索(BFS)深度优先搜索(DFS),广度优先搜索,BFS每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。,广度优先搜索,一般来说，BFS使用
3、队列来实现。BFS一般用来求最优解。在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及由父状态转换过来所执行的操作。,广度优先搜索算法,初始状态入队op:=1对队首状态进行操作op，得到新状态；检查此状态是否出现过，如未出现则将此状态入队；如果此状态为目标状态，则输出；如所有操作都已完成，则队首出队，否则op:=op+1，返回(3)。,广度优先搜索的程序框架,procedure bfs;begin head:=0;tail:=1;datatail.data:=初始状态;datatail.op:=0;datatail.pre:=0;flag:=false;repeat inc(
4、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;,DFS or BFS,k表示树的深度；d表示解的深度；dk,从
5、入口（1）到出口（17）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：,队列应用,请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。,从列表中可以看出出口关卡号（17）的被访问路径最短的是：(17)(16)(19)(18)(1)开始,关卡（最短路径）,I：=1；WHILE NOI 17 DO I:=I+1;REPEAT WRITE(,NOI,);WRITE();I:=PREI;UNTIL I=0；,编一个程序，找出一条通过迷宫的路径。这里有黑色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。,迷宫问题,入口 出口,大小：8 5
6、 入口:2 1 出口 8 4 则路径如(2)*.*入口$*.*$*.*.$*.*.$*.*.$*.*$*.*.$*出口(1)(2),迷宫问题-找出一个从入口到出口的最短路径（八个方向）,总行数：0m+1,总列数：0n+1,8个方向表示可以用数组说明：,如何记录探索的踪迹？队列,如何防止重复探索：将迷宫中的0替换为-1队列中入队、出队情况如下表：,迷宫问题,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:
7、=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;,打印最短路径：,打印最短路径：Procedure print(var sq:sqtype;rear:integer);begin k:=rear;repeat writeln(,sqk.x,sqk.y,);k:=sqk.pre;until k=0;end;,迷宫问题,其实本题也可以用深度优先搜索来做，但是正如前面所说
8、的，因为要求最优解，深度优先搜索需要将整个搜索树都搜索完。宽度优先搜索搜到的第一个解一定是最优解，所以找到解后就可以停止了。,应用,现要找出一条从A到H经过城市最少的一条路径。,广度优先遍历:A,具体过程如下：（1）将城市A入队，队首、队尾都为1。（2）将队首所指的城市所有可直通的城市入队（如何判断？），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。,AH,宽搜基本框架,F,r,队列初始化；While f=r do 取队首；扩展+判重+入队；,给出一个整数n（n2000）和k个变换
9、规则（k15）规则：1个数字可以变换成另1个数字；规则中，右边的数字不能为零。例如：n=234，k=2规则为 2 5 3 6 234经过变换后可能产生出的整数为（包括原数）234 534 264 564求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。,应用产生数,【问题分析】本题考察了同学们三方面的能力：数的表示，如何处理；转换规则如何表示；队列的应用，包括入队、出队以及队的查找。注意点：数以字符串的形式输入，为了计算方便，经过类型转换存入整型数组中；对数的比较也很困难，只能逐位比较，处理时用一个队列q，开始时队列q中只有n。,有10升油在10升的容器中，另
10、有两个7升和3升的空容器，现要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油。题解 三个容器可以看作三个变量 C10，C7，C3，每次倒油的可能性只有如下六种情况：C10 向 C7 倒油 C10 向 C3 倒油 C7 向 C10 倒油 C7 向 C3 倒油 C3 向 C10 倒油 C3 向 C7 倒油,应用倒油,从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态，许多是已经出现过的状态。例如初始状态（10,0,0）表示 C10=10，C7=0，C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,0
11、）和（7,0,3）。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19,C10 C7 C3 PRE,当倒油产生出第19个容器状态时已达到了题解的目的。这时只要根据pre中的状态号17可以回溯到第17个容器状态的pre值为15，依次可再获得13，11，9，7，5，2，1容器状态号，从而即可得到解题的倒油过程（共倒9次）。注意,从一个容器中向另一个容器中倒油,人操作是很直观的,对编程来说则必须考虑:1)有没有油可倒?2)究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已经满了.,广度优先搜索的局限,对于BFS而言，当求解步骤较长时，由于需
12、要存储全部的扩展结点，很容易造成空间不够的情况。对于这种情况，往往会通过剪枝减去不可能的状态，节约空间；或者在容许的情况下使用循环队列；或者采用别的方法来解决问题。,1假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。2设有数2，3，5，7，13，运算符号为+，*，且运算符无优先级之分，如2+3*5=25，3*5+2=17。现给出任意一个整数n，要求用以上的数和运算符，以最少的运算次数产生出n。,训练,黑白棋问题,棋盘由4*4方格阵列组成，共8白，8黑，每一步可将任意2个相邻方格中的棋子互换位置。给定：初始状态，目标状态，计算：最少交换次数,
