广度优先搜索陈鹏

《广度优先搜索陈鹏》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、广度优先搜索引入问题——whyqueue搜索——广度优先搜索队列的维护什么是队列？队列队列是限定在一端进行插入，另一端进行删除的特殊的线性表。删除的一端称为队首，插入的一端称为队尾。具体事例：排队买票，后来的人排在队尾（插入），队首的人离开（删除）。队列的特点线性队头读队尾写先进先出队列的定义静态—数组Typearr=array[1..n]ofinteger;queue=recordvec:arr;front,rear:integer;end;Varq:queue;Varqueue:arr;front,rear:integer;队列的基本操作操作静态数组(A,

2、f,r)建立空队列测试队列是否为空入队(insert)出队(dele)尾插法F:=0;r:=0F>rR:=r+1;a[r]:=x;Iff=0thenf:=1;X:=a[f];f:=f+1;和约定有关深度、广度优先搜索在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。深度、广度优先搜索初始状态对应根结点，目标状态对应目标结点。问题的一个解就是一条从根结点到目标结点的路径。对“搜索树”的搜索算法类似于树的遍历，通常有两种不同的实现方法：广度优先搜索(BFS)深度优先搜索(DFS)广度优先搜索BF

3、S每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。广度优先搜索一般来说，BFS使用队列来实现。BFS一般用来求最优解。在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及由父状态转换过来所执行的操作。DataOPPre广度优先搜索算法初始状态入队op:=1对队首状态进行操作op，得到新状态；检查此状态是否出现过，如未出现则将此状态入队；如果此状态为目标状态，则输出；如所有操作都已完成，则队首出队，否则op:=op+1，返回(3)。广度优先搜索的程序框架procedurebfs;beginhead:=0;ta

4、il:=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;unt

5、il(tail=head)orflagifflagthenoutputelsewriteln('NoAnswer');end;DFSorBFS搜索方式时间空间适用问题DFSO(ck)O(k)必须完全遍历或不要求解的深度最小BFSO(cd)O(cd)解靠近根或要求解的深度最小k表示树的深度；d表示解的深度；d≤k从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：队列应用请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。从列表中可以看出出口关卡号（17）的被访问路径最短的是：(17)←(16)←(19)

6、←(18)←(1)←开始关卡（最短路径）I：=1；WHILENO[I]<>17DOI:=I+1;REPEATWRITE(‘(‘,NO[I],’)’);WRITE(‘←’);I:=PRE[I];UNTILI=0；编一个程序，找出一条通过迷宫的路径。这里有黑色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。迷宫问题010000001000010001100000111001100000000000011入口→→出口大小：85入口:21出口84则路径如(2)**********....*入口$$$$****.****$**...**.$$

7、**..***.$***...**.$$****.****$**...**..$*└──出口(1)(2)迷宫问题---找出一个从入口到出口的最短路径（八个方向）01110111101010100100111101110011100110000110011011111111111011101111110101010110100111111011100111110011000110110011011111111111总行数：0——m+1,总列数：0——n+18个方向表示可以用数组说明：10121131041-150-16-1-17-108-11如何记录探索的踪迹？

8、——队列序号123456X123332