完整性的A *搜索

Question

我一直在阅读有关A *的完整性和我的理解，它必须是完整的，如果它有一个有限的分支因子，但为什么一定要还完成后，每个边的权大于0？

Answer 1

这不是真的，如果图形具有有限的支化因子和每个边缘的重量大于零，那么A *终止。

例如，考虑顶点0，1，2，3，图表......和一个顶点*。让i和i+1之间的边缘的权重为1/2^i和让0和*之间的边缘的权重是2。让启发式是0，所以A *退化成Dijkstra算法。

然后A *不会找到（在有限时间内）从0到*路径 - 这将探讨由于从0到n的距离沿自然数的路径总是小于2。所以尽管此图具有有限的分支因子和正边权重，A *未找到解决方案。

定理的正确的说法是：“如果有图有一个有限的分支因子和所有的权重比一些ε> 0，则A *是完整的更大。”证明很简单：如果从开始到结束的路径具有权重d，那么在最坏的情况下，所有顶点距离< = d都会在末端节点之前访问。但最多可以有很多，因为从起始节点到每个节点的路径最多可以由d /ε顶点组成。