artificial-intelligence - A* 在启发式仅可接受但不一致时重新打开

Question

这里给出了我遵循的 A* 伪代码:

我的问题是:当找到目标状态时，我们如何确定我们可以返回？与所有其他 CLOSED 状态一样，它们可以从新的 OPEN 状态重新打开。因此，如果我有一个从 OPEN 获得的状态，并且我发现我可以从该状态采取更好的路径到达 CLOSED 目标，那么我至少应该更新它的值。难道我们不应该等到所有州都关闭了吗？

Answer 1

之所以可行，是因为:

• 启发式仍然是可接受的，这意味着启发式成本h(n)节点 n必须始终小于或等于真实(未知)剩余成本 h*(n) : h(n) <= h*(n)对于所有 n .
• 你总是弹出节点n总成本最低f(n) = g(n) + h(n)关闭 OPEN , 其中g(n)是迄今为止到达 n 所经过的路径的成本.

所以，假设你刚刚弹出了一个节点 n关闭 OPEN结果是目标状态。您肯定知道(由于第二点)OPEN 中的每个其他节点总计大于或等于 f -分数。由于第一点，您还知道这些 f -OPEN 中所有这些其他节点的分数没有高估；他们肯定不会好转。它们要么完全正确，要么低估了成本。你肯定知道他们永远不会彻底击败 n不再，所以你刚刚找到的路径是n至少会是一条最佳路径(尽管它可能不是唯一最佳路径)。