很早以前做最短路径算法研究的时候就看过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
