雙向廣搜

所謂雙向搜尋指的是搜尋沿兩個方向同時進行：正向搜尋：從初始結點向目標結點方向搜尋；逆向搜尋：從目標結點向初始結點方向搜尋；當兩個方向的搜尋生成同一子結點時終止此搜尋過程。

基本介紹

• 中文名：雙向廣搜
• 方法：兩個方向交替擴展
• 逆向搜尋：從目標結點向初始結點方向
• 主程式代碼：repeat

廣度雙向搜尋算法

廣度雙向搜尋通常有兩種方法：

1. 兩個方向交替擴展

2. 選擇結點個數較少的那個方向先擴展．

方法2克服了兩方向結點的生成速度不平衡的狀態，明顯提高了效率。

算法說明：

設定兩個佇列c:array[0..1,1..maxn] of jid，分別表示正向和逆向的擴展佇列。

設定兩個頭指針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)程式代碼如下

inc(head[st]);

取出佇列當前待擴展的結點c[st,head[st]]

for i:=1 to maxk do

begin

if tail[st]>=maxn then exit;

inc(tail[st]);

產生新結點;

check(st);{檢查新節點是否重複}

end;

check(st:0..1)程式代碼

for i:=1 to tail[st]-1 do

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

bool(st);{如果節點不重複，再判斷是否到達目標狀態}

bool(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;

print0(m)程式代碼

if m<>0 then begin print(c[0,m]^.f);輸出c[0,m]^.* end;

{輸出正方向上產生的結點}

print1(m)程式代碼

n:=c[1,m]^.f

while m<>0

begin

輸出c[1,n]^.*;

n:=c[1,n]^.f;

end

{輸出反方向上產生的結點}