当启发式算法总是低估时，证明A*算法的最优性

Question

我了解为什么A*算法在启发式函数始终低估时总是给出最优路径，但是我无法为其创建正式证明。

据我所知，对于每条被考虑的路径，随着其深入，f(n)的准确性会增加，直到目标状态达到，此时它的准确率为100%。同时，由于估计值小于实际代价，没有错误的路径被忽略，从而导致寻找最优路径。但是我应该如何为此创建一个证明呢？

- user972616

Answer 1

证明的主要思想是当A*找到一条路径时，它已经找到了一条估价比其他可能路径的估价更低的路径。由于估价是乐观的，可以安全地忽略其他路径。

另外，只有满足以下两个条件，A*才是最优的：

1. 启发式函数是可接受的，因为它永远不会高估成本。

2. 启发式函数是单调的，即如果 h(n_i) < h(n_{i + 1})，那么 real-cost(n_i) < real-cost(n_{i + 1})。

你可以通过假设相反并展开影响来证明最优性是正确的。

假设A*给出的路径在使用可接受和单调启发式函数时不是最优的，并考虑这在涵义上意味着什么（很快你就会发现自己达到了矛盾），因此，你的原始假设被缩小到了荒谬的程度。

从这个结论中，你可以得出结论，即你的原始假设是错误的，也就是说，在满足上述条件的情况下，A*是最优的。Q.E.D.

- pcalcao

---

我认为当数据单调递增或单调递减时，算法可以更有效地运行，但这不是必须的。你能告诉我你获取这个信息的来源吗？ - user972616

如果你在对一个闭合集使用A算法，那么这是必要的。从维基百科（还有其他来源）得知：“如果启发式函数是可接受的，也就是说它从不高估到达目标的实际最小成本，那么如果我们不使用封闭集，A算法本身就是可接受的（或最优的）。如果使用了一个封闭集，那么启发式函数f必须也是单调的（或一致性），才能使A*算法是最优的。” - pcalcao

抱歉，pcalcao，但根据您的定义，如果$h(n_1) < h(n_2)$意味着$h^*(n_1) < h^*(n_2)$，其中$h(n)$和$h^*(n)$是启发式估计和真实最优成本。这个定义从哪里来？通常，单调性被定义为对于所有$n'$，$h(n) \leq c(n,n') + h(n')$，其中$n'$是状态空间中任何节点$n$的后代。我没有看到从这个定义到你的定义的必要蕴含。所有可以做的就是将此定义推广到一致性，然后到可接受性，但不是到您的属性，就我所知。 - Carlos Linares López

单调/一致的启发式并不意味着h(a) < h(b)就意味着realCost(a) < realCost(b)，实际上有些一致的启发式违反了这个属性。正如Carlos所说，它意味着h(a) <= c(a, b) + h(b)。之所以称为“单调”，是因为只有对于任何路径v0 -> v1 -> ... -> vn，成本函数f(vi)=g(vi)+h(vi)（其中g(vi)是沿路径v0 -> v1 -> ... -> vi从源顶点v0到vi的距离）沿路径单调递增，即对于任何0 <= i <= j <= n，f(vi) <= f(vj)时，该属性才成立。 - Noble Mushtak

这是我在评论中关于“当且仅当”语句的源代码（向下滚动到“定理1.1”和“一致和单调启发式等价性”处）：https://www.sciencedirect.com/topics/computer-science/consistent-heuristic - Noble Mushtak

Answer 2

考虑到完成最佳路径的最后一步。为什么A*要选择这条路径？换句话说，为什么A*必须避免选择到达目标的次优路径？提示：这就是启发式函数需要是可接受的原因。请注意，选择次优路径是可以的，只要它没有完成路径（为什么？）。这应该能让您对如何构建证明有一些初步的想法。

- Scott Hunter