广度优先搜索97439

《广度优先搜索97439》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、广度优先搜索算法一．宽度优先搜索的过程宽度优先搜索算法是最简便和常用的图形搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即1、从图中的某一顶点V0开始，先访问V0；2、访问所有与V0相

2、邻接的顶点V1，V2，......，Vt；3、依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；4、循此以往，直至所有的顶点都被访问过为止。5、这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。对同一层结点来说，一般按先生成先扩展的顺序进行，因此在数据结构上引入了“队列”结构。“队列”是一种线性表，具有先进先出的特点，对于它所有的插入和删除操作分别仅在队列尾和队列首进行。二、广度优先搜索算法描述：ProgramBfs；初始化，初始状态存入OPEN表；队列首指针head:=0;尾指针tail:=1；repeat指针head后移一位，指向待

3、扩展结点；forI=1tomaxdo{max为产生子结点的规则数}beginif子结点符合条件thenbegintail指针增1，把新结点存入列尾；if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）elseif新结点是目标结点then输出并退出；end;end;until(tail>=head);{队列空}三、广度优先搜索注意事项：1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。3、如果目标结

4、点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”第12页共12页不与深度成正比时，第一次找到的解不一定是最优解。4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。下面我们看看怎样用宽度优先搜索来解决八数码问题。例如　图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展２６个结点和生成４６个结点之后，才求得这

5、个解。此外，直接观察此图表明，不存在有更短走步序列的解。　　　　　　　　　　　　　　　　　　　图2　广度优先搜索图　　　　　　　　　　　　　　　　　　　　　　　　　程序实现算法：　　ProgramBFS；　　　建立数据库data；数据库赋初值；　　　设队列头指针H:=0；队列尾指针L:=1；　　　repeat　　　　取下一个H所指的结点；　　　　fori:=1tomaxdo{i为产生新结点规则编号}　　　　　begin　　　　　L增1，把新结点存入数据库队尾；记录父结点的位置；　　　　　if新结点与原有结点重复then　　　　　　删去该结点(L减1)　　　　　　else　

6、　　　　　　if新结点为目标结点then输出并退出；　　　　　end；　　　　end；　　　untilH>=L{队列为空}程序：第12页共12页program8no_bfs;{八数码的宽度优先搜索算法}ConstDir:array[1..4,1..2]ofinteger　　　　　{四种移动方向，对应产生式规则}=((1,0),(-1,0),(0,1),(0,-1));N=10000;TypeT8No=array[1..3,1..3]ofinteger;TList=recordFather:integer;　　　　　　　　　　　{父指针}dep:byte;　　{深度}X0,

7、Y0:byte;{0的位置}State:T8No;　　　　　　　　　　{棋盘状态}end;VarSource,Target:T8No;List:array[0..10000]ofTList;{综合数据库}Closed,Open,Best:integer{Best表示最优移动次数}Answer:integer;{记录解}Found:Boolean;{解标志}procedureGetInfo;{读入初始和目标节点}vari,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j