我知道如果启发式是可以接受的，A *不会访问每个节点以找到最佳路径 . 查看每个算法的可视化，A *一到达目标节点就会停止 . 那么，如果您没有探索到目标节点的所有可能路径，您如何确定您的路径是最佳路径？过高估计每个成本路径如何确保最佳解决方案？
考虑Dijkstra算法，这是A *的特殊情况，其中启发式始终为0. Dijkstra按照距离源最短距离的顺序访问节点，因此当它访问目标节点时，您知道它是最短路径，因为所有未访问的节点都是严格的距离，所以通过它们不可能产生更短的路径 .
现在在A *中，您按照它们与源的距离加上启发式的值的顺序访问节点 . 我们假设给定节点的启发式值不会在此时调用从源到目标的距离 d_t . 考虑您尚未访问的任何节点 v . 您知道从源到该节点的距离 d_v 加上启发式 h_v 的值大于 d_t （因为您按照该值的顺序访问节点，因此所有未访问的节点都将该值更大） . 另请注意，根据我们上面的假设，从 v 到 t 的最短距离大于或等于 h_v . 由此得出，通过 v 从源到目标的距离将长于 d_t ，因此没有理由考虑该节点 . 因此 d_t 是从源到目标的最短路径 .
d_t
v
d_v
h_v
t
1 回答
考虑Dijkstra算法，这是A *的特殊情况，其中启发式始终为0. Dijkstra按照距离源最短距离的顺序访问节点，因此当它访问目标节点时，您知道它是最短路径，因为所有未访问的节点都是严格的距离，所以通过它们不可能产生更短的路径 .
现在在A *中，您按照它们与源的距离加上启发式的值的顺序访问节点 . 我们假设给定节点的启发式值不会在此时调用从源到目标的距离
d_t. 考虑您尚未访问的任何节点v. 您知道从源到该节点的距离d_v加上启发式h_v的值大于d_t（因为您按照该值的顺序访问节点，因此所有未访问的节点都将该值更大） . 另请注意，根据我们上面的假设，从v到t的最短距离大于或等于h_v. 由此得出，通过v从源到目标的距离将长于d_t，因此没有理由考虑该节点 . 因此d_t是从源到目标的最短路径 .