为什么A*算法不用遍历所有节点就找到最优路径？

Question

我理解如果启发式是可接受的，A* 不会访问每个节点来找到最佳路径。查看每个算法的可视化，A* 在到达目标节点后立即停止。那么，如果您还没有探索到目标节点的所有可能路径，您如何确定您的路径是最佳路径呢？高估每条成本路径如何确保最优解？

Answer 1

考虑 Dijkstra 算法，这是 A* 的一个特例，其中启发式始终为 0。Dijkstra 以距源最短距离的顺序访问节点，因此在它访问目标节点的那一刻，你知道这是最短的路径，因为所有未访问的节点都严格地远离，所以通过它们不可能产生更短的路径。

现在在 A* 中，您访问节点的顺序是它们与源的距离加上启发式的值。我们假设给定节点的启发式值不超过从该节点到目标的最短距离。当你第一次访问目标时，我们称此时源到目标的距离为d_t。考虑您尚未访问过的任何节点 v。你知道从源到那个节点的距离 d_v 加上启发式的值 h_v 大于 d_t （因为你按照那个值的顺序访问节点，所以所有未访问的节点具有更大的值）。另请注意，根据我们上面所做的假设，从 v 到 t 的最短距离大于或等于 h_v。由此得出，通过 v 从源到目标的距离将比 d_t 长，因此没有理由考虑该节点。因此 d_t 是从源到目标的最短路径。