[TOC]
A* Algorithm
A*权衡从初始结点到任意结点n的代价g(n)、从结点n到目标点的启发式评估代价（heuristic estimated cost）h(n)。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。
启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。
- 一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A演变成Dijkstra算法，这保证能找到最短路径。
- Admissible heuristic: 如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条最短路径。h(n)越小，A扩展的结点越多，运行就得越慢。
- Consistent Heuristic: 定义一个启发式函数是一致的 (或称为单调的)，如果对于任何节点 $n$ 和它的任意子节点 $n^{\prime}$ 以及两者之间的边的成本 $c\left(n, n^{\prime}\right)$ ，都满足不等式 $h(n) \leq$ $c\left(n, n^{\prime}\right)+h\left(n^{\prime}\right)$ 。简单来说，这意味着估计的成本不应比从当前节点到其子节点的实际成本加上从子节点到目标的启发式成本更少。除了保证找到最优解外，还有助于提高搜索效率。
- 所有一致启发式都是可接受的，但并非所有可接受的启发式都是一致的。
- 一致启发式可以使用 Dijkstra 算法求出最短路径。
- 如果h(n)精确地等于从n移动到目标的代价，则A star将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A star会运行得很完美，认识这一点很好。
- 如果h(n)有时比从n移动到目标的实际代价高，则A star不能保证找到一条最短路径，但它运行得更快。
- 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A star演变成BFS算法。
Pseudocode
OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
current = remove lowest rank item from OPEN
add current to CLOSED
for neighbors of current:
cost = g(current) + movementcost(current, neighbor)
if neighbor in OPEN and cost less than g(neighbor):
remove neighbor from OPEN, because new path is better
if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
remove neighbor from CLOSED
if neighbor not in OPEN and neighbor not in CLOSED:
set g(neighbor) to cost
add neighbor to OPEN
set priority queue rank to g(neighbor) + h(neighbor)
set neighbor's parent to current
reconstruct reverse path from goal to start
by following parent pointers
