双向搜索

双向搜索算法是一种图的遍历算法，用于在有向图中搜索从一个顶点到另一个顶点的最短路径。算法同时运行两个搜索：一个从初始状态正向搜索，另一个从目标状态反向搜索，当两者在中间汇合时搜索停止。在很多情况下该算法更快，假设搜索一棵分支因子b的树，初始节点到目标节点的距离为d，该算法的正向和反向搜索复杂度都是O(bd/2) (大O符号)，两者相加后远远小于普通的单项搜索算法（复杂度为O(bd)）。

图与树
搜索算法
分类
  • 图算法
  • 搜索算法
  • 算法列表
相关主题

在A*搜尋演算法中，双向搜索的启发式函数可以定义为：正向搜索为到目标节点的距离，反向搜索为到初始节点的距离。

Ira Pohl （1971）第一个设计并实现了双向启发式搜索算法。Andrew Goldberg和其他人解释了双向搜索版的戴克斯特拉算法的正确完结条件。[1]


参考
  1. (PDF). [2018-07-04]. （原始内容存档 (PDF)于2018-06-18）.
  • de Champeaux, Dennis; Sint, Lenie, , ACM期刊, 1977, 24 (2): 177–191, doi:10.1145/322003.322004.
  • de Champeaux, Dennis, , ACM期刊, 1983, 30 (1): 22–32, doi:10.1145/322358.322360.
  • Pohl, Ira, , Meltzer, Bernard; Michie, Donald (编), 6, Edinburgh University Press: 127–140, 1971.
  • Russell, Stuart J.; Norvig, Peter, , 2nd, Prentice Hall, 2002.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.