双向广度优先搜索算法.ppt

双向广度优先搜索算法
什么叫双向广度优先搜索
所谓双向搜索指的是搜索沿两个方向同时进行:
正向搜索:从初始结点向目标结点方向搜索;
逆向搜索:从目标标结点向初始结点方向搜索;

广度双向搜索通常有两种方法:
1. 两个方向交替扩展
2. 选择结点个数较少的那个方向先扩展.
方法2克服了两方向结点的生成速度不
平衡的状态,明显提高了效率。
数据结构的建立
设置两个队列c:array[0..1,1..maxn] of node,分别表示正向和逆向的扩展队列。
设置两个头指针head:array[0..1] of integer 分别表示正向和逆向当前将扩展结点的头指针。
设置两个尾指针tail:array[0..1] of integer 分别表示正向和逆向的尾指针。
maxn表示队列最大长度。
算法描述
主程序代码
repeat
  {选择节点数较少且队列未空、未满的方向先扩展} 
  if (tail[0]<=tail[1]) and not((head[0]>tail[0])or(tail[0]>=maxn))
then expand(0);
  if (tail[1]<=tail[0]) and not((head[1]>tail[1])or(tail[1]>=maxn))
then expand(1);
{如果一方搜索终止,继续另一方的搜索,直到两个方向都终止}
  if not((head[0]>tail[0])or(tail[0]>=maxn))
then expand(0);
  if not((head[1]>tail[1])or(tail[1]>=maxn))
then expand(1);
Until ((head[0]>tail[0])or(tail[0]>=maxn)) And ((head[1]>tail[1])or(tail[1]>=maxn))
算法描述
expand(st:0..1)程序代码如下:
  取出队列当前待扩展的结点c[st,head[st]]
inc(head[st]); I:=1;
    while (i<=maxk) and (tail[st]<maxn) do
    begin
       inc(tail[st]);
     产生新结点;
      check(st);{检查新节点是否重复}
inc(i);
    end;
算法描述
check(st:0..1)程序代码:{检查节点,如果不重复,则判断是否相遇}
  i:=1; flag:=true;
while flag and (I< tail[st]) do begin
      if c[st,tail[st]].*=c[st,i].* then
begin flag:=false; dec(tail[st]);exit end;
inc(I);
end;
   if flag then encounter(st);{判断是否相遇}
算法描述
encounter(st:0..1)程序代码:
  for i:=1 to tail[1-st] do
    if c[st,tail[st]].*=c[1-st,i].*
then  print(st,tail[st],i);
     {如果双向搜索相遇(即得到同一节点),则输出结果}
算法描述
print(st,tail,k)程序代码:
if st=0 then begin
print0(tail); print1(k);
end;
      else begin
print0(k); print1(tail)
end;
writeln(c[st,tail[st]].dep+c[1-st,tail[k]].dep-1)
close(f);
halt;
算法描述
print0(m)程序代码:
  if m<>0 then begin
print0(c[0,m].f);
输出c[0,m].*
end;
{输出正方向上产生的结点}