我想实现A星算法，于是我参考了维基百科的相关内容。
看起来它在以下情况下可能会失败。假设有三个节点，A、B和C。
START -> A -> C -> GOAL | ^ \-> B路径成本如下：
START -> A : 10START -> B : 1B -> A : 1A -> C : 100C -> GOAL : 100显然，解决方案是START -> B -> A -> C -> GOAL，但如果启发式函数让我们在扩展B之前先扩展A会怎样呢？
我们的启发式成本如下（请注意，这些都是低估值）
A -> GOAL : 10B -> GOAL : 50当扩展A时，C的真实成本将高于B的启发式成本，因此B会在C之前被扩展。
这没问题，对吗？
我看到的问题是，当我们扩展B并将数据“A来自START，成本为10”替换为“A来自B，成本为2”时，我们没有同时更新“C来自A，成本为110”为“C来自A，成本为102”。维基百科的伪代码中似乎没有内容会向前传播更便宜的路径。现在想象另一个节点D，它可以以成本105到达C，它将错误地覆盖“C来自A，成本为110”。
我理解错了，还是维基百科需要修正？
回答：
如果你使用的是图搜索，即你记得访问过的节点并且不允许重新访问这些节点，那么你的启发式函数是不一致的。文章中提到，要使启发式函数一致，需要满足以下条件：
h(x) <= d(x, y) + h(y) 对于所有相邻节点x, y在你的例子中，假设h(B) = 50是不一致的，因为d(B -> A) + h(A) = 1 + 10 = 11。因此你的启发式函数是不一致的，A星算法在这种情况下将无法工作，正如你正确地注意到的那样，也正如维基百科文章中提到的：http://en.wikipedia.org/wiki/A%2a_search_algorithm#Properties。
如果你使用的是树搜索，即允许算法重新访问节点，将会发生以下情况：
将A和B添加到队列中，score(A) = 10 + 10 = 20，score(B) = 1 + 50 = 51。
从队列中选择A，因为它的分数最小。将C添加到队列中，score(C) = 10 + 100 + h(C)。
从队列中选择B，因为它现在是最小的。将A添加到队列中，score(A) = 2 + 10 = 12。
再次从队列中选择A，因为它现在再次是最小的。请注意，我们使用的是树搜索算法，因此我们可以重新访问节点。将C添加到队列中，score(C) = 1 + 1 + 100 + h(C)。
现在队列中有两个元素，C通过A的分数为110 + h(C)，C通过B和A的分数为102 + h(C)，所以我们选择通过B和A到达C的正确路径。
维基百科的伪代码是第一种情况，即图搜索。他们确实在伪代码下方明确指出：
备注：上述伪代码假设启发式函数是单调的（或一致的，见下文），这在许多实际问题中是常见的情况，例如道路网络中的最短距离路径。然而，如果假设不成立，关闭集中的节点可能会被重新发现并改进其成本。换句话说，如果保证存在解决方案，或者如果算法被调整为只有当新节点的f值低于之前任何迭代时才将其添加到开放集中，则可以省略关闭集（生成树搜索算法）。
