A*算法中可接受和一致启发式的使用方法

Question

A*算法中可接受和一致启发式的使用方法

algorithma-starheuristics

3

有没有简单易懂的解释，为什么在A*算法中必须使用可接受的启发式和为什么“应该”使用一致的启发式？

- Geminus

2个回答

0

这只是为了让你说找到的结果是“最优”的，你可以使用任何启发式算法，但要证明找到的结果是最优的会更困难。

例如，当你高估到目标节点的距离时，实际距离可能比估计值小。因此，即使存在更好的解决方案，找到的结果仍可能被标记为“最优”。

- Enermis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

可接受的

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

为什么我们需要可接受性？

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

如果我们认为成本会超过实际成本，我们可能会走更昂贵的路径。路径A的预期成本可能高于路径B的预期成本，但路径A的实际成本可能更低。这意味着我们将首先探索非最优路径B。

如果一个启发式算法不可行，我们理论上甚至可能永远无法到达目标（或者至少在到达目标之前我们会探索整个可能空间）。虽然这在合理的启发式算法中不太可能发生，但是可能会创建一种启发式算法，其中我们认为离目标越远，到达目标的成本就越低，并且当远离目标时，预期剩余成本的降低速度比实际成本更快。以一个简单（有限）的例子为例：heuristic = 100000000 - 2 * actual。

一致性

我们做的任何移动都不应该减少预期总成本。换句话说，任何移动所减少的启发式算法值都不应该超过该移动的成本。

预期的总成本（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，则不可接受，因为会有一些n使得t(n) < 10。如果每个移动都至少花费10，那么这将是既可接受又一致的。

h(n) = 0：对于正成本而言，它不能花费少于0来到达目标，因此是可接受的。由于启发式永远不会减少，所以是一致的。但并不特别有用。这相当于Dijkstra's algorithm。

h(n) = t(n) / 2：由于期望成本低于实际成本，因此是可接受的。由于移动成本始终至少是该移动的预期成本的两倍（如果远离目标还会增加h(n)），因此任何移动都将增加总预期成本，因此是一致的。