双向搜索
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
图与树 搜索算法 |
---|
分类 |
相关主题 |
双向搜索算法是一种图的遍历算法,用于在有向图中搜索从一个顶点到另一个顶点的最短路径。算法同时运行两个搜索:一个从初始状态正向搜索,另一个从目标状态反向搜索,当两者在中间汇合时搜索停止。在很多情况下该算法更快,假设搜索一棵分支因子b的树,初始节点到目标节点的距离为d,该算法的正向和反向搜索复杂度都是O(bd/2) (大O符号),两者相加后远远小于普通的单项搜索算法(复杂度为O(bd))。
在A*搜寻演算法中,双向搜索的启发式函数可以定义为:正向搜索为到目标节点的距离,反向搜索为到初始节点的距离。
Ira Pohl (1971)第一个设计并实现了双向启发式搜索算法。Andrew Goldberg和其他人解释了双向搜索版的戴克斯特拉算法的正确完结条件。[1]
参考
- ^ Efficient Point-to-Point Shortest Path Algorithms (PDF). [2018-07-04]. (原始内容存档 (PDF)于2018-06-18).
- de Champeaux, Dennis; Sint, Lenie, An improved bidirectional heuristic search algorithm, ACM期刊, 1977, 24 (2): 177–191, doi:10.1145/322003.322004.
- de Champeaux, Dennis, Bidirectional heuristic search again, ACM期刊, 1983, 30 (1): 22–32, doi:10.1145/322358.322360.
- Pohl, Ira, Bi-directional Search, Meltzer, Bernard; Michie, Donald (编), Machine Intelligence 6, Edinburgh University Press: 127–140, 1971.
- Russell, Stuart J.; Norvig, Peter, 3.4 Uninformed search strategies, Artificial Intelligence: A Modern Approach 2nd, Prentice Hall, 2002.