请输入您要查询的百科知识:

 

词条 双向广搜
释义

广度双向搜索的概念

所谓双向搜索指的是搜索沿两个方向同时进行:

正向搜索:从初始结点向目标结点方向搜索;

逆向搜索:从目标结点向初始结点方向搜索;

当两个方向的搜索生成同一子结点时终止此搜索过程。

广度双向搜索算法

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

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]^.* then print(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

{输出反方向上产生的结点}

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2024/12/23 20:43:23