1.1 廣度雙向搜尋的概念
所謂雙向搜尋指的是搜尋沿兩個方向同時進行：正向搜尋：從初始結點向目標結點方向搜尋；
逆向搜尋：從目標結點向初始結點方向搜尋；
當兩個方向的搜尋生成同一子結點時終止此搜尋過程。
1. 2 廣度雙向搜尋算法
廣度雙向搜尋通常有兩中方法：1. 兩個方向交替擴展
2. 選擇結點個數較少的那個力向先擴展．
方法2克服了兩方向結點的生成速度不平衡的狀態，明顯提高了效率。
算法說明：
設定兩個佇列c:array【0..1,1..maxn】 of jid，分別表示正向和逆向的擴展佇列。設定兩個頭指針head:array【0..1】 of integer 分別表示正向和逆向當前將擴展結點的頭指針。
設定兩個尾指針tail:array【0..1】 of integer 分別表示正向和逆向的尾指針。
maxn表示佇列最大長度。
算法描述如下：
1.主程式代碼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))
2.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;
3.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);{如果節點不重複，再判斷是否到達目標狀態}
4.bool(st:0..1)程式代碼:
for i:=1 to tail【1-st】 do
if c【st,tail【st】】^.*=c【1-st,i】^.* thenprint(st,tail【st】,i);
{如果雙向搜尋相遇（即得到同一節點），則輸出結果}
5.print(st,tail,k)程式代碼：
if st=0 then begin print0(tail);print1(k) end;
else begin print0(k);print1(tail) end;
6.print0(m)程式代碼：
if m<>0 then begin print(c【0,m】^.f);輸出c【0,m】^.* end;
{輸出正方向上產生的結點}
7.print1(m)程式代碼;
n:=c【1,m】^.f
while m<>0
begin
輸出c【1,n】^.*;
n:=c【1,n】^.f;
end
{輸出反方向上產生的結點}
