algorithm - 在 A* 中使用可接受的和一致的启发式

Question

有人可以简单和/或直观地解释为什么您必须在 A* 中使用可接受的启发式算法以及为什么您“应该”使用一致的启发式算法吗？

Answer 1

Admissible

我们认为实现目标所需的成本不会超过实际成本。

为什么我们需要准入？

如果任何预期成本小于实际成本，则意味着最优路径的预期成本总是小于或等于其真实成本，这将小于某些非最优路径的真实成本。由于我们总是首先探索具有最低预期总成本的节点，当我们达到目标时我们只会查看真实成本，因此我们永远无法通过非最佳路径到达目标。

如果我们认为它的成本高于实际成本，我们实际上最终可能会选择一条成本更高的路径。路径 A 的预期成本可能高于路径 B 的预期成本，但路径 A 的实际成本可能更低。这意味着我们将首先探索非最佳路径 B。

如果启发式算法 Not Acceptable ，理论上我们可能永远甚至无法达到目标(或者至少我们会在到达目标之前探索整个可能的空间)。虽然这不太可能通过合理的启发式方法实现，但可以创建一种启发式方法，我们认为离目标越远成本越低，并且当远离目标时，预期剩余成本比实际成本下降得更快目标。作为一个简单(有限)示例:heuristic = 100000000 - 2 * actual。

Consistent

我们采取的任何行动都不应降低预期的总成本。换句话说:所做的任何移动都应该减少启发式，不超过该移动的成本。

预期总成本 (f(n)) 是预期剩余成本 (h(n))加上到目前为止的成本(g(n))。例如，我们可能认为达到目标的总时间是 10 分钟。行驶5分钟后，如果我们认为总时间(包括行驶的5分钟)是11分钟也可以，但我们不应该认为总时间是9分钟。

注意:对于剩余成本，我们只考虑我们认为需要多长时间。实际需要多长时间可能会有所不同。

除上述之外，当我们已经达到目标时，一致的启发式算法还需要将预期剩余成本设为 0。

一致的启发式也是可以接受的(但不一定相反)。这是从上面得出的。

为什么我们需要一致性？

如果我们继续移动(朝向或远离目标)，我们希望成本增加。否则，在我们最终找到最佳路径之前，我们最终可能会偏离目标并探索一大堆没有希望的路径。

注意:如果启发式是可接受的但不一致，我们将不会找到通往目标的非最佳路径，但找到最佳路径可能需要一段时间。

例子

h(n) = 启发式，即从 n 到目标的预期(剩余)成本
g(n) = 从开始到 n 的成本(到目前为止)
t(n) = 从 n 到目标的真实(剩余)成本

h(n) = 10(h(goal) = 0 除外):如果移动成本小于 10，则 Not Acceptable ，因为在 t(n) < 10 时会有一些 n。自移动到目标后不一致将涉及将启发式从 10 减少到 0，但这样做的移动成本将低于 10。但是，如果每个移动成本至少为 10，这将是可接受的和一致的。

h(n) = 0:可接受，因为(对于正成本)达到目标的成本不能低于 0。一致，因为启发式永远不会减少。虽然不是特别有用。这相当于 Dijkstra's algorithm .

h(n) = t(n)/2:可接受，因为预期成本低于真实成本。一致，因为移动的成本总是至少是该移动的预期成本的两倍(如果偏离目标，它也会增加 h(n))，因此任何移动都会增加总的预期成本。