[转] 搜索之双向BFS

转自:http://www.cppblog.com/Yuan/archive/2011/02/23/140553.aspx

如果目标也已知的话,用双向BFS能很大程度上提高速度。

单向时,是 b^len的扩展;

双向的话,2*b^(len/2)  快了很多,特别是分支因子b较大时。

至于实现上,网上有些做法是用两个队列,交替节点搜索 ×,如下面的伪代码:
    while(!empty()){

扩展正向一个节点

遇到反向已经扩展的return

扩展反向一个节点

遇到正向已经扩展的return

}

但这种做法是有问题的,如下面的图

[转] 搜索之双向BFS

求S-T的最短路,交替节点搜索(一次正向节点,一次反向节点)时

Step 1 : S –> 1 , 2

Step 2 : T –> 3 , 4

Step 3 : 1 –> 5

Step 4 : 3 –> 5   返回最短路为4,错误的,事实是3,S-2-4-T

我想,正确做法的是交替逐层搜索,保证了不会先遇到非最优解就跳出,而是检查完该层所有节点,得到最优值
也即如果该层搜索遇到了对方已经访问过的,那么已经搜索过的层数就是答案了,可以跳出了,以后不会更优的了。
当某一边队列空时就无解了。

优化:提供速度的关键在于使状态扩展得少一些,所以优先选择队列长度较少的去扩展,保持两边队列长度平衡。这比较适合于两边的扩展情况不同时,一边扩展得快,一边扩展得慢。如果两边扩展情况一样时,加了后效果不大,不过加了也没事。

无向图时,两边扩展情况类似。有向图时,注意反向的扩展是反过来的 x->y(如NOIP2002G2字串变换)

例题:HDU 1195

AC Code:http://www.cnblogs.com/hate13/p/4621894.html

上一篇:论文阅读 - Matrix Factorization Techniques for Recommender Systems


下一篇:5、JavaScript进阶篇②——函数、事件、内置对象