我已经阅读了一些关于这个话题的stackoverflow问题以及维基百科上的A*算法内容，但我仍然有点困惑。我认为这篇文章几乎完全解释了这个问题：A*启发式，过高估计/低估？
我唯一剩下的困惑是，A*如何知道最优解？看起来使用可接受的启发式时，可以抛弃那些超过已知最优解的路径，因为启发式保证小于或等于。但A*如何提前知道最优解呢？
如果不知道最优路径成本，这种搜索是否能工作并保证最优解？
回答：
A*并不知道最优解，启发式只是给出一个有根据的猜测，帮助加速搜索过程。既然你已经阅读了一些理论解释，我们在这里尝试用一个例子来解释这个问题：
- 从绿色节点开始，A*探索成本+启发式值最小的节点（1.5 + 4 = 5.5，节点’a’）。成本+启发式可以理解为“到目前为止的成本加上我认为到目标还需要多少”。换句话说，这是到目标的估计总成本。因此，选择最小值是有意义的。节点’d’的成本更高（2 + 4.5 = 6.5），所以我们只是把它留在队列中。
- 通过扩展’a’的邻居，我们将’b’添加到队列中并计算其值，即1.5 + 2 + 2 = 5.5（到目前为止的成本以粗体显示，另一个术语是我认为到目标还需要多少）。它仍然比’d’的成本好，所以我们继续探索这条路径。注意’b’的启发式值为2，这意味着我们认为这是到达目标所需的额外成本…这显然是错误的，从’b’到目标不可能只需成本2！但这对A*算法没有问题，因为我们是低估了实际成本。
- 扩展’b’，我们将它的邻居’c’添加到队列中，值为1.5 + 2 + 3 + 4 = 10.5。现在，记住’d’仍然在队列中？现在它的值最小（6.5），所以我们将’c’留在队列中并尝试’d’，因为它是一条更有希望的路径。这个决定之所以可能，是因为我们知道到达’c’的成本只有6.5，我们认为到目标还需要成本4。在这种情况下，启发式是正确的，这对A*算法也是可以的。
- 通过扩展’d’，我们将’e’添加到队列中，值为2 + 3 + 2 = 7。这里的启发式是正确的，我们已经知道这对A*是可以的。然后我们会探索’e’并找到目标。但假设我们有h(e) = 6，给’e’的值为2 + 3 + 6 = 11。这意味着’c’将是下一个最佳猜测（10.5），我们将尝试一条无望的路径！这意味着高估启发式是不可接受的，因为它会使A*选择错误的探索路径。
如果你在寻找证明，这里是维基百科上关于可接受性的非正式证明：
当A*终止搜索时，它已经找到了一条实际成本低于通过任何开放节点的路径估计成本的路径。但由于这些估计是乐观的，A*可以安全地忽略这些节点。换句话说，A*永远不会忽视低成本路径的可能性，因此是可接受的。
关于最优性：
假设现在另一个搜索算法B终止其搜索，其路径的实际成本不低于通过某个开放节点的路径估计成本。基于它拥有的启发式信息，算法B不能排除通过该节点的路径可能具有更低成本的可能性。因此，虽然B可能考虑的节点比A*少，但它不能是可接受的。因此，A*考虑的节点是所有可接受搜索算法中最少的。
你可能还想查看这个视频：A*最优性证明。
