14.4八数码问题进一步讨论-双向广搜

广度优先搜索 八数码问题进一步讨论：

广搜一般用于状态表示比较简单、求最优策略的问题 优点：是一种完备策略，即只要问题有解，它就一定可以找到解 。并且，广度优先搜索找到的解，还一定是路径最短的解。 缺点：盲目性较大，尤其是当目标节点距初始节点较远时，将产 生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出 的状态，占用的空间大 深搜几乎可以用于任何问题 只需要保存从起始状态到当前状态路径上的节点 根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择

八数码问题 : 如何加快速度

1. 双向广搜(HDU能过） 从两个方向以广度优先的顺序同时扩展

2. 针对本题预处理 (HDU能过） 因为状态总数不多，只有不到40万种，因此可以 从目标节点开始，进行一遍彻底的广搜，找出全部有 解状态到目标节点的路径。

3. A* 算法(HDU能过） 八数码问题 : 如何加快速度 6 双向广度优先搜索(DBFS) DBFS算法是对BFS算法的一种扩展。 BFS算法从起始节点以广度优先的顺序不断扩展，直 到遇到目的节点 DBFS算法从两个方向以广度优先的顺序同时扩展， 一个是从起始节点开始扩展，另一个是从目的节点扩 展，直到一个扩展队列中出现另外一个队列中已经扩 展的节点，也就相当于两个扩展方向出现了交点，那 么可以认为我们找到了一条路径。 比较 DBFS算法相对于BFS算法来说，由于采用了双向扩展的方式，搜 索树的宽度得到了明显的减少，时间复杂度和空间复杂度上都有 提高！

比较 DBFS算法相对于BFS算法来说，由于采用了双向扩展的方式，搜 索树的宽度得到了明显的减少，时间复杂度和空间复杂度上都有 提高！ 假设1个结点能扩展出n个结点，单向搜索要m层能找到答案，那 么扩展出来的节点数目就是: (1-n m)/(1-n)

比较 DBFS算法相对于BFS算法来说，由于采用了双向扩展的方式，搜 索树的宽度得到了明显的减少，时间复杂度和空间复杂度上都有 提高！ 假设1个结点能扩展出n个结点，单向搜索要m层能找到答案，那 么扩展出来的节点数目就是: (1-n m)/(1-n) 双向广搜，同样是一共扩展m层，假定两边各扩展出m/2层，则总 结点数目 2 * (1-n m/2)/(1-n)

比较 DBFS算法相对于BFS算法来说，由于采用了双向扩展的方式，搜 索树的宽度得到了明显的减少，所以在算法的时间复杂度和空间 复杂度上都有较大的优势！ 假设1个结点能扩展出n个结点，单向搜索要m层能找到答案，那 么扩展出来的节点数目就是: (1-n m)/(1-n) 双向广搜，同样是一共扩展m层，假定两边各扩展出m/2层，则总 结点数目 2 * (1-n m/2)/(1-n) 每次扩展结点总是选择结点比较少的那边进行扩展，并不是机械 的两边交替。

DBFS的框架(1)