use*_*975 6 language-agnostic algorithm
我被要求调查Dijkstra算法的改进.我一直在研究A Star算法,但我发现很多解释都使用了不熟悉的单词和数学符号.
我知道A Star只考虑目标节点的边缘.例如,如果将A Star算法应用于英国的道路网络,并且目的地是Dundee并且我在伦敦开始,则仅检查向北的边缘.
这至少是正确的吗？
A*使用启发式来猜测节点到目标的最小成本.因此,在选择节点时,您不仅要分析从该节点开始到该节点的成本,还要分析从节点到目标的可能成本.这允许忽略可能导致错误方向的路径.
如果示例中的启发式使用节点的地理距离,则将首先检查向北的道路(因为它们具有较小的估计总成本).但是在执行算法期间,这些道路可能会从一开始就聚集一个非常大的实际距离(可能是因为有很多曲线).然后还可以检查通往南方的道路.因此,如果这比通往北方的所有弯曲道路(不考虑GB的实际路线图)要短,那么可以向南走一点并向北直行.
启发式的本质定义了算法的质量.如果启发式给出距离的下限(即,不可能以比启发式说的更便宜的成本到达目标),那么路径实际上是最短路径.如果启发式不是下限,则也可以允许其他路径(这可能是算法运行时和路径质量之间的权衡).启发式算法估计最小成本越好,您检查的错误方向就越少.即如果启发式算法是常数,那么你最终会得到一个简单的Dijkstra算法.如果启发式计算目标的实际成本,则只会遵循最短路径,并且不会检查其他节点.