algorithm - 为什么可接受的启发式方法可以保证最优性？

Question

今天在类里面，我的教授向我们介绍了可接受的启发式，并声明它们保证了A* 算法 的最优性。

我让他用一个极端的例子来解释清楚，但他不能。

有人可以帮忙吗？

Answer 1

我们有候选人名单，对吧？

并且他们每个人都有一个 ETC(预期总成本)以从起始节点到达目标(即到达该节点的成本 + 到目标的预期剩余成本(启发式))。

现在，如果预期成本与实际成本相同，我们将只选择最短路径(好吧，任何最短路径)上的节点，除此之外别无其他。因为我们选择了最低的 ETC，所以我们只从最短路径中选择节点的原因应该很明显——任何不在最短路径上的节点都会有更高的 ETC。

如果 ETC 低于实际成本怎么办？我们总是选择最低的 ETC，所以我们最终可能会选择不在最短路径上的节点。但是我们永远无法通过不是最短路径的路径达到目标，因为:

• 最短路径的实际成本低于任何非最短路径
• 目标的 ETC 与通过该路径到达目标的成本相同(因为我们已经到达目标，预期剩余成本为 0)
• ETC 始终小于或等于任何路径上的实际总成本
• 因此，最短路径上的 ETC 严格小于通过非最短路径达到的目标的 ETC。

举个例子，假设我们的成本如下:(节点上方/下方的成本是预期的剩余成本，边上的成本是实际成本)

  0    10  0  100   0
START ---- O ------ GOAL
0 |                 | 100
  O ------ O ------ O
 100  1   100  1   100

很明显，我们将从访问顶部中间节点开始，因为 ETC 是 10 (10+0)。

然后目标将是一个候选人，ETC 为 110 (10+100+0)。

然后我们明确地依次选择底部节点，然后是更新的目标，因为它们的 ETC 都低于当前目标的 ETC，即它们的 ETC 是:100、101、102、102。

因此，即使目标是候选目标，我们也无法选择它，因为那里还有更好的路径。