广度优先搜索陈鹏ppt课件

广度优先搜索引入问题——whyqueue搜索——广度优先搜索队列的维护什么是队列？队列•队列是限定在一端进行插入，另一端进行删除的特殊的线性表。•删除的一端称为队首，插入的一端称为队尾。•具体事例：排队买票，后来的人排在队尾（插入），队首的人离开（删除）。队列的特点•线性•队头读队尾写•先进先出队列的定义•静态—数组Typearr=array[1..n]ofinteger;queue=recordvec:arr;front,rear:integer;end;Varq:queue;Varqueue:arr;front,rear:integer;队列的基本操作操作静态数组(A,f,r)建立空队列测试队列是否为空入队(insert)出队(dele)尾插法F:=0;r:=0FrR:=r+1;a[r]:=x;Iff=0thenf:=1;X:=a[f];f:=f+1;和约定有关深度、广度优先搜索•在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。深度、广度优先搜索•初始状态对应根结点，目标状态对应目标结点。问题的一个解就是一条从根结点到目标结点的路径。•对“搜索树”的搜索算法类似于树的遍历，通常有两种不同的实现方法：–广度优先搜索(BFS)–深度优先搜索(DFS)广度优先搜索•BFS每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。广度优先搜索•一般来说，BFS使用队列来实现。•BFS一般用来求最优解。•在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及由父状态转换过来所执行的操作。DataOPPre广度优先搜索算法1.初始状态入队2.op:=13.对队首状态进行操作op，得到新状态；4.检查此状态是否出现过，如未出现则将此状态入队；5.如果此状态为目标状态，则输出；6.如所有操作都已完成，则队首出队，否则op:=op+1，返回(3)。广度优先搜索的程序框架procedurebfs;beginhead:=0;tail:=1;data[tail].data:=初始状态;data[tail].op:=0;data[tail].pre:=0;flag:=false;repeatinc(head);whiledata[head]还可以扩展dobeginnew:=op(data[head].state);ifnew已经出现thencontinue;inc(tail);data[tail].data:=new;data[tail].op:=op;data[tail].pre:=head;ifnew是目标状态thenbeginflag:=true;break;end;end;until(tail=head)orflagifflagthenoutputelsewriteln('NoAnswer');end;DFSorBFS搜索方式时间空间适用问题DFSO(ck)O(k)必须完全遍历或不要求解的深度最小BFSO(cd)O(cd)解靠近根或要求解的深度最小k表示树的深度；d表示解的深度；d≤k从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：队列应用请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。从列表中可以看出出口关卡号（17）的被访问路径最短的是：(17)←(16)←(19)←(18)←(1)←开始关卡（最短路径）I：=1；WHILENO[I]17DOI:=I+1;REPEATWRITE(‘(‘,NO[I],’)’);WRITE(‘←’);I:=PRE[I];UNTILI=0；编一个程序，找出一条通过迷宫的路径。这里有黑色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。迷宫问题010000001000010001100000111001100000000000011入口→→出口大小：85入口:21出口84则路径如(2)**********....*入口$$$$****.****$**...**.$$**..***.$***...**.$$****.****$**...**..$*└──出口(1)(2)迷宫问题---找出一个从入口到出口的最短路径（八个方向）01110111101010100100111101110011100110000110011011111111111011101111110101010110100111111011100111110011000110110011011111111111总行数：0——m+1,总列数：0——n+18个方向表示可以用数组说明：10121131041-150-16-1-17-108-11如何记录探索的踪迹？——队列序号123456X123332…Y123144…pre012233…如何防止重复探索：将迷宫中的0替换为-1队列中入队、出队情况如下表：迷宫问题sq[1].x:=1;sq[1].y:=1;sq[1].pre:=0;front:=1;rear:=1;mg[1,1]:=-1;whilefront=reardox:=sq[front].x;y:=sq[front].y;forv:=1to8doI:=x+z[v].x;j:=y+z[v].y;ifmg[I,j]=0thenrear:=rear+1;sq[rear].pre:=front;sq[rear].x:=I;sq[rear].y:=j;mg[I,j]:=-1;if(i=m)and(j=n)thenprint;front:=front+1;打印最短路径：打印最短路径：Procedureprint(varsq:sqtype;rear:integer);begink:=rear;repeatwriteln(‘(‘,sq[k].x,’,’,sq[k].y,’)’);k:=sq[k].pre;untilk=0;end;迷宫问题•其实本题也可以用深度优先搜索来做，但是正如前面所说的，因为要求最优解，深度优先搜索需要将整个搜索树都搜索完。•宽度优先搜索搜到的第一个解一定是最优解，所以找到解后就可以停止了。应用现要找出一条从A到H经过城市最少的一条路径。广度优先遍历:A具体过程如下：（1）将城市A入队，队首、队尾都为1。（2）将队首所指的城市所有可直通的城市入队（如何判断？），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。AH宽搜基本框架F,r,队列初始化；Whilef=rdo取队首；扩展+判重+入队；给出一个整数n（n2000）和k个变换规则（k≤15）规则：①1个数字可以变换成另1个数字；②规则中，右边的数字不能为零。例如：n=234，k=2规则为2→53→6234经过变换后可能产生出的整数为（包括原数）234534264564求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。应用——产生数【问题分析】本题考察了同学们三方面的能力：①数的表示，如何处理；②转换规则如何表示；③队列的应用，包括入队、出队以及队的查找。注意点：①数以字符串的形式输入，为了计算方便，经过类型转换存入整型数组中；②对数的比较也很困难，只能逐位比较，处理时用一个队列q，开始时队列q中只有n。有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）和（7,0,3）。123456789101112131415161718191037037646491912828507074343161607705250033300330031212300011223567891011121314151617C10C7C3PRE当倒油产生出第19个容器状态时已达到了题解的目的。这时只要根据pre中的状态号17可以回溯到第17个容器状态的pre值为15，依次可再获得13，11，9，7，5，2，1容器状态号，从而即可得到解题的倒油过程（共倒9次）。注意,从一个容器中向另一个容器中倒油,人操作是很直观的,对编程来说则必须考虑:1)有没有油可倒?2)究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已经满了.广度优先搜索的局限•对于BFS而言，当求解步骤较长时，由于需要存储全部的扩展结点，很容易造成空间不够的情况。•对于这种情况，往往会通过剪枝减去不可能的状态，节约空间；或者在容许的情况下使用循环队列；或者采用别的方法来解决问题。1．假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。2．设有数2，3，5，7，13，运算符号为+，—，*，且运算符无优先级之分，如2+3*5=25，3*5+2=17。现给出任意一个整数n，要求用以上的数和运算符，以最少的运算次数产生出n。训练黑白棋问题•棋盘由4*4方格阵列组成，共8白，8黑，每一步可将任意2个相邻方格中的棋子互换位置。给定：初始状态，目标状态，计算：最少交换次数