双向广度优先搜索算法

广度双向搜索的概念

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

广度双向搜索算法

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

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.