[科普中国]-双向搜索算法

双向搜索算法是一种图的遍历算法，用于在有向图中搜索从一个顶点到另一个顶点的最短路径。

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

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

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

图遍历图遍历问题分为四类：

遍历完所有的边而不能有重复，即所谓“一笔画问题”或“欧拉路径”；

遍历完所有的顶点而没有重复，即所谓“哈密顿路径问题”。

遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；

遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。

对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。

第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。

启发式算法与最短路径问题所谓的最短路径问题有很多种意思，在这里启发式指的是一个在一个搜索树的节点上定义的函数{\displaystyle h(n)}，用于评估从此节点到目标节点最便宜的路径。启发式通常用于信息充份的搜索算法，例如最好优先贪心算法与A*。最好优先贪心算法会为启发式函数选择最低代价的节点；A*则会为g(n)+h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。如果h(n)是可接受的（admissible）意即 h(n)未曾付出超过达到目标的代价，则A*一定会找出最佳解。

最能感受到启发式算法好处的经典问题是n-puzzle。此问题在计算错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。注意，上述两条件都必须在可接受的范围内。

本词条内容贡献者为:

黄伦先 - 副教授 - 西南大学