A *（星号）算法解释

Question

我被要求研究对Dijkstra算法的改进。我一直在研究A星算法，但我发现许多解释使用不熟悉的单词和数学符号。

我明白星只考虑目标节点的边缘。例如，如果将A Star算法应用于英国的公路网，并且目的地是邓迪，并且我在伦敦开始，则只检查北部边界。

这是否至少是正确的？

Answer 1

A *使用启发式来猜测节点到目标的最小成本。因此，在选择节点时，不仅要分析从开始到该节点的成本，还要分析从节点到目标的可能成本。这允许忽略可能导致错误方向的路径。

如果您示例中的启发式使用节点的地理距离，那么将首先检查北部的道路（因为它们的总体成本估计很小）。但是，在算法执行过程中，这些道路可能会从一开始就聚集一个非常大的实际距离（可能是因为有很多曲线）。然后还可以检查通往南方的道路。因此，如果这条路线比北方所有弯曲的道路（不考虑GB的实际路线图）短，那么可以往南走一点，然后直行。

启发式的本质定义了算法的质量。如果启发式给出了距离的下限（即不可能以比启发式算法更便宜的成本到达目标），那么路径确实是最短的路径。如果启发式不是一个下界，也可以允许其他路径（这可能是算法运行时间和路径质量之间的折衷）。启发式方法估计的最小成本越低，您将检查的错误方向越少。即如果启发式是恒定的，那么最终会得到一个普通的Dijkstra算法。如果启发式计算目标的实际成本，则只会遵循最短路径，并且不会检查其他节点。