from : http://baike.baidu.com/view/614354.html?tp=9_11
广度双向搜索的概念
所谓双向搜索指的是搜索沿两个方向同时进行:
正向搜索:从初始结点向目标结点方向搜索;
逆向搜索:从目标结点向初始结点方向搜索;
当两个方向的搜索生成同一子结点时终止此搜索过程。
广度双向搜索算法
广度双向搜索通常有两种方法:
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
{输出反方向上产生的结点}
分享到:
相关推荐
双向广搜在竞赛中是很有战斗力的,比单向的广搜快很多
# pyqt5 八数码拼图游戏 广度优先搜索(bfs)、双向广搜(dbfs)、A*搜索求解 1. pyqt5制作可视化窗口,qss美观ui; 2. 自定义导入图片,生成3、4、5阶八数码拼图; 3. 可以点击移动小方块进行游戏; 4. 可以选择使用...
八数码问题,广度优先搜索,用C++实现。 八数码问题即: 一个3*3的格子,其中8个小方格里各有个数字, 另外一个格子是空的,它临近的数字可以移动到这个空格子里。 给定一个八数码的起始状态,和一个终止状态,通过...
完整的双向广搜八数码程序,可以运行,并且时间基本上控制在1ms之内
递归和排列 BFS BFS和队列 状态图搜索:八数码问题 BFS与A*算法 双向广搜 DFS DFS和递归 回溯与剪枝:八皇后 迭代加深搜索 IDA
这个就才一点点,帮助理解下就行。。我资源里有其他更详细的
《算法竞赛入门到进阶》的第 4 章“搜索技术”,讲解了递归、BFS、DFS 的原理,以及双向广搜、A*算法、剪枝、迭代加深搜索、IDA*的经典例题,适合入门搜索
《算法竞赛入门到进阶》的第 4 章“搜索技术”,讲解了递归、BFS、DFS 的原理,以及双向广搜、A*算法、剪枝、迭代加深搜索、IDA*的经典例题,适合入门搜索
自己写的八数码求解的C#程序 使用双向广搜算法求解
双向广搜 迭代加深 优先队列搜索,过最少的门救人,建图 A*搜索 图论 差分约束 Intervals bellman_ford Intervals SPFA 出纳员的雇佣 不等式组 图论 割边 图染色 拓扑 树 欧拉路径) 割点+统计删除后剩下多少...
北京地铁导航所用到的文件,此文件是我和同学一条一条的录入的,如果大家用到我们录入的文件请注明出处!...代码请到我的CSDN博客中寻找(博文:双向广搜的DIJKSTRA算法--简易的北京地铁导航实现,作者:五十风)
当前的 世界已进入一个网络信息社会,信息通讯技术的发展,已经使互联网络成为一个全球性 的辐射面更广、交互性更强的新型媒体,不同于广播电视等传统媒体只能进行单向性的 信息传播,而是可以与媒体的接受者进行...
leetcode全ac ...双端队列广搜,双向DFS) 字符串高级,包括(KMP,后缀树,AC自动机,后缀数组) 数据结构高级,包括(红黑树,B+树,线段树,区间树,树状数组,splay, treap, 并查集,可持久化数据结构, KD树)
11.2.4 双向链表 420 11.2.5 结构中的位字段 423 11.3 结构与函数 424 11.3.1 结构作为函数的变元 424 11.3.2 结构指针作为函数变元 425 11.3.3 作为函数返回值的结构 426 11.3.4 修改程序 430 11.3.5 ...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...
精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后附录提供快速索引,即查、即学、...