为什么可接受的启发式保证最优性？

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.

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