今天在课堂上，我的教授向我们介绍了可接受的启发式，并指出它们保证了A*算法的最优性。
我请求他用一个极端的例子来解释以便更明显，但他没能做到。
请问有人能帮我解释一下吗？
回答：
我们有一份候选名单，对吗？
每个候选者都有一个ETC（预期总成本），从起始节点到达目标的成本（即到达该节点的成本 + 到达目标的预期剩余成本（启发式））。
如果预期成本与实际成本相同，我们将只选择最短路径上的节点（好吧，任何最短路径上的节点），而不是其他节点。因为我们选择最低的ETC，所以为什么我们只选择最短路径上的节点应该很明显——任何不在最短路径上的节点都会有更高的ETC。
如果ETC低于实际成本呢？我们总是选择最低的ETC，所以我们可能会选择不在最短路径上的节点。但我们永远无法通过非最短路径到达目标，因为：
- 最短路径的实际成本低于任何非最短路径
- 在目标处的ETC与通过该路径到达目标的成本相同（因为我们已经在目标处，预期剩余成本为0）
- ETC总是小于或等于任何路径上的实际总成本
- 因此，最短路径上的ETC严格小于通过非最短路径到达的目标处的ETC。
举个例子，假设我们有以下成本：（节点上方的/下方的成本是预期剩余成本，边的成本是实际成本）
0 10 0 100 0START ---- O ------ GOAL0 | | 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。
所以即使目标是一个候选者，我们也无法选择它，因为还有更好的路径存在。
