algorithm - A*(A星)算法解释

Question

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

我理解 A Star 只考虑朝向目标节点的边。例如，如果将 A Star 算法应用于英国的道路网络，目的地是邓迪，而我从伦敦开始，则只会检查向北的边。

这至少是正确的吗？

Answer 1

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

如果您的示例中的启发式方法使用节点的地理距离，则将首先检查通往北方的道路(因为它们的估计总成本很小)。但有可能在算法执行期间，这些道路从起点聚合了非常大的实际距离(可能是因为有很多弯道)。然后也可以检查通往南方的道路。因此，如果这比所有通往北方的弯曲道路都短(不考虑 GB 的实际路线图)，则可以向南走一点，然后一直向北走。

启发式的性质决定了算法的质量。如果启发式给出了距离的下限(即不可能以比启发式所说的更便宜的成本到达目标)，那么该路径实际上是最短路径。如果启发式不是下限，也可以允许其他路径(这可能是算法运行时间和路径质量之间的权衡)。启发式方法对最小成本的估计越好，您检查的错误方向就越少。 IE。如果启发式是不变的，你最终会得到一个普通的 Dijkstra 算法。如果启发式算法计算到目标的实际成本，您将只遵循最短路径，不会检查其他节点。