资源描述：
《广度优先搜索优化.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广度优先双向搜索 1.1广度双向搜索的概念所谓双向搜索指的是搜索沿两个力向同时进行：正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。1.2广度双向搜索算法广度双向搜索通常有两中方法：1.两个方向交替扩展2.选择结点个数较少的那个方向先扩展．方法2克服了两方向结点的生成速度不平衡的状态，明显提高了效率。 算法说明：设置两个队列c:array[0..1,1..maxn]ofjid，分别表示正向和逆向的扩展队列。设置两个头指针head:array[0.
2、.1]ofinteger分别表示正向和逆向当前将扩展结点的头指针。设置两个尾指针tail:array[0..1]ofinteger分别表示正向和逆向的尾指针。maxn表示队列最大长度。算法描述如下：1.主程序代码 repeat {选择节点数较少且队列未空、未满的方向先扩展} if(tail[0]<=tail[1])andnot((head[0]>=tail[0])or(tail[0]>=maxn))thenexpand(0); if(tail[1]<=tail[0])andnot((head[1]>=tail[1])or(
3、tail[1]>=maxn))thenexpand(1); {如果一方搜索终止，继续另一方的搜索，直到两个方向都终止} ifnot((head[0]>=tail[0])or(tail[0]>=maxn))thenexpand(0); ifnot((head[1]>=tail[1])or(tail[1]>=maxn))thenexpand(1); Until((head[0]>=tail[0])or(tail[0]>=maxn)) And((head[1]>=tail[1])or(tail[1]>=maxn))2.expan
4、d(st:0..1)程序代码如下: inc(head[st]; 取出队列当前待扩展的结点c[st,head[st]] fori:=1tomaxkdo begin iftail[st]>=maxnthenexit; inc(tail[st]); 产生新结点; check(st);{检查新节点是否重复} end;3.check(st:0..1)程序代码: fori:=1totail[st]-1do ifc[st,tail[st]]^.*=c[st,i]^.*thenbegindec
5、(tail[st]);exitend; bool(st);{如果节点不重复，再判断是否到达目标状态} 4.bool(st:0..1)程序代码: fori:=1totail[1-st]do ifc[st,tail[st]]^.*=c[1-st,i]^.*then print(st,tail[st],i); {如果双向搜索相遇（即得到同一节点），则输出结果}135.print(st,tail,k)程序代码：ifst=0thenbeginprint0(tail);print1(k)end; elsebeg
6、inprint0(k);print1(tail)end;6.print0(m)程序代码： ifm<>0thenbeginprint(c[0,m]^.f);输出c[0,m]^.*end;{输出正方向上产生的结点}7.print1(m)程序代码; n:=c[1,m]^.f whilem<>0 begin 输出c[1,n]^.*; n:=c[1,n]^.f; end{输出反方向上产生的结点}1.3例题与习题 例1：8数码难题： 283 123 164->8 4（用
7、最少的步数） 7 5 765程序如下：programnum8;constmaxn=4000;typejid=record str:string[9]; f:0..maxn; dep:byte; end; bin=0..1;varc:array[0..1,1..maxn]of^jid; head,tail:array[0..1]ofinteger; start,goal:string[9];procedureinit;vari,j:integer;begin
8、 start:='283164705'; goal:='123804765'; fori:=0to1do forj:=1tomaxndo new(c[i,j]); c[0,1]^.str:=start;c[0,1]^.f:=0;c[0,1]^.dep:=0; c[1,1]^.str:=
