A* 在使用可接受的启发式算法时是否需要知道最优解成本？
Does A* need to know the optimal solution cost while utilizing an admissible heuristic?
我已经阅读了一些关于这个主题的计算器，以及关于 A* 的维基百科，但我仍然有点困惑。我认为这个 post 几乎完全向我解释了它：A* heuristic, overestimation/underestimation?
我唯一的困惑是，A* 是如何知道最优解的？似乎使用可接受的启发式算法，您可以抛出超过已知最佳解决方案的路径，因为启发式算法保证小于或等于。但是 A* 如何提前知道最优值？
如果您不知道最佳路径成本，此搜索是否有效并保证找到最佳解决方案？
A* 不知道最佳解决方案，启发式算法仅提供有根据的猜测，这有助于加快搜索过程。看到您已经阅读了一些理论解释，让我们在这里尝试不同的方法，并举例说明：
- 从绿色节点开始，A* 探索成本最小的节点 + 启发式（1.5 + 4 = 5.5，节点 'a'）。成本+启发式可以读作"how much until there plus how much I think is left to the goal"。换句话说，它是目标的估计总成本。所以我们 select 最小值是有道理的。节点 'd' 的成本较高 (2 + 4.5 = 6.5)，因此我们将其留在队列中。
- 通过扩展 'a' 个邻居，我们将 'b' 添加到队列中并计算其值，即 1.5 + 2 + 2 = 5.5（成本直到粗体显示，另一个术语是我认为还剩下多少）。它仍然比 'd' 的成本要好，所以我们继续探索这条路。请注意 'b' 中的启发式是 2，这意味着我们认为这是达到目标所需的额外成本...这显然是错误的，无法从 [=54= 到达那里] 成本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* 采取了错误的探索路径。
如果您正在寻找证据，这里有一份来自维基百科的非正式证明：
When A* terminates its search, it has found a path whose actual cost is lower than the estimated cost of any path through any open node. But since those estimates are optimistic, A* can safely ignore those nodes. In other words, A* will never overlook the possibility of a lower-cost path and so is admissible.
为了优化：
Suppose now that some other search algorithm B terminates its search with a path whose actual cost is not less than the estimated cost of a path through some open node. Based on the heuristic information it has, Algorithm B cannot rule out the possibility that a path through that node has a lower cost. So while B might consider fewer nodes than A*, it cannot be admissible. Accordingly, A* considers the fewest nodes of any admissible search algorithm.
您可能还想查看此视频：A* optimality proof。
它通过使用启发式方法遍历所有可能的 variants/chances 来实现。因此，您将在关闭列表中获得所有需要的 tiles/vertices/waypoints。
我已经阅读了一些关于这个主题的计算器，以及关于 A* 的维基百科，但我仍然有点困惑。我认为这个 post 几乎完全向我解释了它：A* heuristic, overestimation/underestimation?
我唯一的困惑是，A* 是如何知道最优解的？似乎使用可接受的启发式算法，您可以抛出超过已知最佳解决方案的路径，因为启发式算法保证小于或等于。但是 A* 如何提前知道最优值？
如果您不知道最佳路径成本，此搜索是否有效并保证找到最佳解决方案？
A* 不知道最佳解决方案，启发式算法仅提供有根据的猜测，这有助于加快搜索过程。看到您已经阅读了一些理论解释，让我们在这里尝试不同的方法，并举例说明：
- 从绿色节点开始，A* 探索成本最小的节点 + 启发式（1.5 + 4 = 5.5，节点 'a'）。成本+启发式可以读作"how much until there plus how much I think is left to the goal"。换句话说，它是目标的估计总成本。所以我们 select 最小值是有道理的。节点 'd' 的成本较高 (2 + 4.5 = 6.5)，因此我们将其留在队列中。
- 通过扩展 'a' 个邻居，我们将 'b' 添加到队列中并计算其值，即 1.5 + 2 + 2 = 5.5（成本直到粗体显示，另一个术语是我认为还剩下多少）。它仍然比 'd' 的成本要好，所以我们继续探索这条路。请注意 'b' 中的启发式是 2，这意味着我们认为这是达到目标所需的额外成本...这显然是错误的，无法从 [=54= 到达那里] 成本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* 采取了错误的探索路径。
如果您正在寻找证据，这里有一份来自维基百科的非正式证明：
When A* terminates its search, it has found a path whose actual cost is lower than the estimated cost of any path through any open node. But since those estimates are optimistic, A* can safely ignore those nodes. In other words, A* will never overlook the possibility of a lower-cost path and so is admissible.
为了优化：
Suppose now that some other search algorithm B terminates its search with a path whose actual cost is not less than the estimated cost of a path through some open node. Based on the heuristic information it has, Algorithm B cannot rule out the possibility that a path through that node has a lower cost. So while B might consider fewer nodes than A*, it cannot be admissible. Accordingly, A* considers the fewest nodes of any admissible search algorithm.
您可能还想查看此视频：A* optimality proof。
它通过使用启发式方法遍历所有可能的 variants/chances 来实现。因此，您将在关闭列表中获得所有需要的 tiles/vertices/waypoints。