algorithm - A* 搜索的完整性

Question

我一直在阅读关于 A* 的完备性的文章，我知道如果它有一个有限的分支因子它就一定是完备的，但是为什么当每条边的权重都大于 0 时它也必须是完备的？

Answer 1

如果图具有有限分支因子并且每条边权重都大于零，则 A* 终止，这是不正确的。

例如，考虑具有顶点 0、1、2、3 ...和单个顶点 *。令i和i+1之间的边的权重为1/2^i，令0和0之间的边的权重为* 为 2。令启发式为 0，因此 A* 退化为 Dijkstra 算法。

那么 A* 将不会(在有限时间内)找到从 0 到 * 的路径——它将沿着自然数探索路径，因为距离 0 到 n 总是小于 2。所以尽管这个图有有限的分支因子和正边权重，A* 没有找到解决方案。

该定理的正确表述是:“如果一个图有一个有限的分支因子，并且所有权重都大于某个 ε>0，那么 A* 是完备的。”证明很简单:如果从开始到结束的路径的权重为 d，那么在最坏的情况下，所有顶点距离 <= d 都在结束节点之前被访问。但是它们最多可以有有限多个，因为从起始节点到每个节点的路径最多可以包含 d/ε 个顶点。