双向广搜

所谓双向搜索指的是搜索沿两个方向同时进行：正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。

双向广搜方法

广度双向搜索通常有两种方法：

1. 两个方向交替扩展

2. 选择结点个数较少的那个方向先扩展．

方法2克服了两方向结点的生成速度不平衡的状态，明显提高了效率。

算法说明：

设置两个队列c:array of jid，分别表示正向和逆向的扩展队列。

设置两个头指针head:array of integer 分别表示正向和逆向当前将扩展结点的头指针。

设置两个尾指针tail:array of integer 分别表示正向和逆向的尾指针。

maxn表示队列最大长度。

双向广搜代码

算法描述如下：

主程序代码

repeat

{选择节点数较少且队列未空、未满的方向先扩展}

if (tail<=tail) and not((head>=tail)or(tail>=maxn)) then expand(0);

if (tail<=tail) and not((head>=tail)or(tail>=maxn)) then expand(1);

{如果一方搜索终止，继续另一方的搜索，直到两个方向都终止}

if not((head>=tail)or(tail>=maxn)) then expand(0);

if not((head>=tail)or(tail>=maxn)) then expand(1);

Until ((head>=tail)or(tail>=maxn)) And ((head>=tail)or(tail>=maxn))

expand(st:0..1)程序代码如下

inc(head);

取出队列当前待扩展的结点c[st,head

for i:=1 to maxk do

begin

if tail>=maxn then exit;

inc(tail);

产生新结点;

check(st);{检查新节点是否重复}

end;

check(st:0..1)程序代码

for i:=1 to tail-1 do

if c[st,tail^.*=c^.* then begin dec(tail);exit end;

bool(st);{如果节点不重复，再判断是否到达目标状态}

bool(st:0..1)程序代码

for i:=1 to tail do

if c[st,tail^.*=c^.* then print(st,tail,i);

{如果双向搜索相遇（即得到同一节点），则输出结果}

print(st,tail,k)程序代码

if st=0 then begin print0(tail);print1(k) end;

else begin print0(k);print1(tail) end;

print0(m)程序代码

if m<>0 then begin print(c^.f);输出c^.* end;

{输出正方向上产生的结点}

print1(m)程序代码

n:=c^.f

while m<>0

begin

输出c^.*;

n:=c^.f;

end

{输出反方向上产生的结点}