雙向寬搜算法

in in in

雙向廣度優先搜尋算法
廣度雙向搜尋的概念
所謂雙向搜尋指的是搜尋沿兩個力向同時進行：正向搜尋：從初始結點向目標結點方向搜尋；逆向搜尋：從目標結點向初始結點方向搜尋；當兩個方向的搜尋生成同一子結點時終止此搜尋過程。
廣度雙向搜尋算法
廣度雙向搜尋通常有兩種方法：
1. 兩個方向交替擴展
2. 選擇結點個數較少的那個力向先擴展．方法2克服了兩方向結點的生成速度不平衡的狀態，明顯提高了效率。
算法說明：
設定兩個佇列c:array[0..1,1..maxn] of jid，分別表示正向和逆向的擴展佇列。
設定兩個頭指針head:array[0..1] of integer 分別表示正向和逆向當前將擴展結點的頭指針。
設定兩個尾指針tail:array[0..1] of integer 分別表示正向和逆向的尾指針。
maxn表示佇列最大長度。
雙向寬搜的套用：
{
題目來源：NOIP2002提高組試題
描述 Description
已知有兩個字串 A$, B$ 及一組字串變換的規則（至多6個規則）:
A1$ -> B1$
A2$ -> B2$
規則的含義為：在 A＄中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ …。
例如：A$＝'abcd'　B$＝'xyz'
變換規則為：
‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’
則此時，A$ 可以經過一系列的變換變為 B$，其變換的過程為：
‘abcd’->‘xud’->‘xy’->‘xyz’
共進行了三次變換，使得 A$ 變換為B$。
輸入格式 Input Format
A$ B$
A1$ B1$ \
A2$ B2$ |-> 變換規則
... ... /
所有字元串長度的上限為 20。
輸出格式 Output Format
若在 10 步（包含 10步）以內能將 A$ 變換為 B$ ，則輸出最少的變換步數；
否則輸出"NO ANSWER!"
樣例輸入：
abcd xyz
abc xu
ud y
y yz
樣例輸出：
3
題目類型：雙向廣搜
分析：很經典的搜尋，雙向進行，一種從初始狀態向目標狀態搜尋，另一種從目標狀態向初始狀態搜尋，哪一種的該層節點少就從哪一層向上 或向下搜尋，直到兩種搜尋相交，0ms暴爽，詳細解釋看下面
}
program NOIP2002p2;
type pp=record
d:longint;
s:string;
end;
var head,tail:array[1..2] of longint;
q:array[1..1000,1..2] of pp;
st:string;
a:array[1..10,1..2] of string;
i,j,tot,k:longint;
//init--------------------------
procedure init;//a[tot,1]記錄第tot－1個變換規則的A$字串，a[tot,2]記錄第tot－1個變換規則的B$字串，因為第一個是起始串和終止串
var x:longint;
s:string;
begin
tot:=0;
while not eof do
begin
inc(tot);
readln(s);
x:=pos(' ',s);
a[tot,1]:=copy(s,1,x-1);
a[tot,2]:=copy(s,x+1,length(s)-x);
end;
end;
//prepare-----------------------
procedure prepare;//準備工作：第一個佇列的頭指針指向第一個A$串，第二個佇列的頭指針指向第一個B$串，存儲變換次數的記錄均賦值為0
var i,j,k:longint;
begin
head[1]:=1; tail[1]:=1;
head[2]:=1; tail[2]:=1;
q[head[1],1].s:=a[1,1]; q[head[1],1].d:=0;
q[head[2],2].s:=a[1,2]; q[head[2],2].d:=0;
end;
//check-------------------------
procedure check(s1:string; t:longint);
var i:longint;
f:boolean;
begin
f:=false;
for i:=1 to tail[t]-1 do if q[i,t].s=s1 then f:=true;//檢驗前面的佇列中是否出現過相同的字元串
if f=true then dec(tail[t])//出現過，刪除掉擴展的節點
else//沒出現過的話，向另一個佇列中尋找是否有重合，有，即找到了目標，對頭成功，大功告成^-^,結束程式即可；沒有，接著搜唄！
begin
for i:=1 to tail[3-t] do
if q[i,3-t].s=s1 then
begin
writeln(q[tail[t],t].d+q[i,3-t].d);
close(input); close(output);
halt;
end;
end;
end;
//wide--------------------------
procedure wide(x:longint);
var s1:string;
i,j,t:longint;
begin
for i:=2 to tot do//從第二個變換規則開始枚舉A$或B$串
begin
t:=pos(a[i,x],q[head[x],x].s);//從父親節點的字元串中尋找可以變換的位置
if t<>0 then//找到後擴展節點
begin
repeat
inc(tail[x]);
q[tail[x],x].s:=q[head[x],x].s;
delete(q[tail[x],x].s,t,length(a[i,x]));//刪除掉需要更換的字元串
insert(a[i,3-x],q[tail[x],x].s,t);//插入變換後的字元串，當前串即為更新後的字元串
q[tail[x],x].d:=q[head[x],x].d+1;//變換次數加一
check(q[tail[x],x].s,x);//檢驗是否出現過相同的狀態
t:=t+pos(a[i,x],copy(q[head[x],x].s,t+1,length(q[head[x],x].s)-t)); {一個字元串中可能有多個可交s換串}
until pos(a[i,x],copy(q[head[x],x].s,t+1,length(q[head[x],x].s)-t))=0
end;
end;
inc(head[x]);
end;
//work--------------------------
procedure work;
begin
repeat
if (head[1]<=tail[1])and(q[tail[1],1].d<=10)and(tail[1]<=tail[2]) then wide(1);
if (head[2]<=tail[2])and(q[tail[2],2].d<=10)and(tail[1]>tail[2]) then wide(2);//儘量做到兩個佇列在數量上保持一致
until (head[1]>tail[1]) or (head[2]>tail[2]) or (q[tail[1],1].d+q[tail[2],2].d>10);//中止條件
end;
//main--------------------------
begin
init;
prepare;
work;
writeln('NO ANSWER!');
end.