A*算法

    技术2022-05-13  16

    很早以前做最短路径算法研究的时候就看过A*算法,本以为它的作用仅限于这一领域,后来才知道原来A*算法在整个搜索类算法中占有很重要的地位,甚至BFS都只能算是它的特例。下面就以A*算法在最短路径算法中的应用的一段描述来简要介绍下它。

    特别需要注意的是估价函数h(i)的两个特性。

     

    A*算法和 Dijkstra算法极其相似,其实我觉得 Dijkstra算法就是h(i)=0的A*算法。

    Like the Dijkstra algorithm, the A* algorithm maintains a set S of candidate nodes (nodes which have yet to be selected as the next closest node to the origin) and applies a best-first method to select from this list the next node to expand/scan. When viewed from a myopic perspective, A* is exactly the same as Dijkstra’s However, A* also includes a forward-looking component, which is an estimate of the length to complete the path to the destination from a specific node.

     

    最短路径算法中,我们通常就把g(i)设置成源点到点i的实际距离,h(i)设置成点i到目标点的欧几里德距离。

    When node i is placed on the candidate list S, the A* algorithm establishes a temporary distance label with a function consisting of two parts: d(i)=g(i) + h(i) where g(i) is the estimated length of the shortest path from the origin s to node i, and h(i) is the estimated length of the shortest path from i to the destination t. One can think of the estimated completion costs, h(*), as a type of penalty, where nodes closer to the destination are penalized less than nodes that are further away from the destination.  The h(*) component of the node label helps direct the search space towards the destination, whereas the Dijkstra algorithm tends to expand the search space uniformly in all directions

     

    这两点很关键,一般文章中都不会提到。如果要保证解是最优的,h(i)必须要满足第一点。

    A*算法:h(*)的特性  Admissible: for every node i, h(i) does not exceed the actual shortest path distance from i to destination t. if h(i) is admissible, then A* is an optimal

    algorithm. Consistent: for every arc (i,j), h(*) satisfies the triangle inequality: h(i) ≤ l(i,j) + h(j) and h(t)=0. If h(*) is consistent, every node enters set S at most once


    最新回复(0)