广度优先搜索.ppt

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

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

2、ueue:arr;front,rear:integer;5广度优先搜索动画队列的基本操作操作静态数组(A,f,r)建立空队列测试队列是否为空入队(insert)出队(dele)尾插法F:=0;r:=0F>rR:=r+1;a[r]:=x;Iff=0thenf:=1;X:=a[f];f:=f+1;和约定有关6广度优先搜索动画深度、广度优先搜索在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。7广度优先搜索动画深度、广度优先搜索初始状态对应根结点，目标状态对应目标结点。问题的一个

3、解就是一条从根结点到目标结点的路径。对“搜索树”的搜索算法类似于树的遍历，通常有两种不同的实现方法：广度优先搜索(BFS)深度优先搜索(DFS)8广度优先搜索动画广度优先搜索BFS每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。9广度优先搜索动画广度优先搜索一般来说，BFS使用队列来实现。BFS一般用来求最优解。在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及由父状态转换过来所执行的操作。DataOPPre10广度优先搜索动画广度优先搜索算法初始状态入队op:=1对队首状态进行操作op

4、，得到新状态；检查此状态是否出现过，如未出现则将此状态入队；如果此状态为目标状态，则输出；如所有操作都已完成，则队首出队，否则op:=op+1，返回(3)。11广度优先搜索动画广度优先搜索算法描述ProgramBfs；初始化，初始状态存入OPEN表(即队列)；队列首指针head:=0;尾指针tail:=1；repeat指针head后移一位，指向待扩展结点；forI=1tomaxdo{max为产生子结点的规则数}beginif子结点符合条件thenbegintail指针增1，把新结点存入列尾；if新结点与原已产生结点重复then删去该结点（取消

5、入队，tail减1）elseif新结点是目标结点then输出并退出；end;end;until(head>=tail);{队列空}12广度优先搜索动画初始化LIST取消在N中结点的所有标记;标记结点s1245369781pred(1)=0next:=1order(next)=1LIST:={1}next11245369781113广度优先搜索动画在LIST中选择结点iLIST在广度优先搜索中，i是在LIST中的第一个结点12453697811next11114广度优先搜索动画如果结点i和一条可进入弧关联…LIST选择一条可进入弧(i,j)1

6、2453697811next1211标记结点jpred(j):=i2Next:=Next+1order(j):=next把j添加到LIST2215广度优先搜索动画如果结点i和一条可进入的弧关联…LIST选择一条可进入弧(i,j)124536978311next2311标记结点jpred(j):=i2Next:=Next+1order(j):=next把j添加到LIST225516广度优先搜索动画4如果结点i和一条可进入的弧关联…LIST选择一条可进入弧(i,j)124536978311next2311标记结点jpred(j):=i2Nex

7、t:=Next+1order(j):=next把j添加到LIST225534317广度优先搜索动画4如果结点i和一条可进入的弧关联…LIST从LIST删除结点i124536978311next231122255343118广度优先搜索动画4选择结点iLIST在LIST上的第一个结点变成了结点i124536978311next2311222553431219广度优先搜索动画54如果结点i和一条可进入的弧关联…LIST124536978311next231222553432选择一条可进入弧arc(i,j)标记结点jpred(j):=iNext:

8、=Next+1order(j):=next把j添加到LIST45420广度优先搜索动画54如果结点i和一条可进入的弧关联…LIST124536978311next