CVBB ACM Team

A*算法与寻找最短路径的Dijkstra算法有相似之处。（不如说A*其实是Dijkstra的改版） A*算法的应用场景仅限寻找起始状态到目标状态之间的最短路（Dijktra能找到起始状态到所有节点的最短路）。

A*算法最特别之处就是估价函数F(n)=G(n)+H(n)
其中F(n)表示起始状态经过状态n到目标状态的估计代价
G(n)表示起始状态到状态n的最小代价
H(n)表示状态n到目标状态的估计代价
与Dijkstra算法一样，所有的状态（点）可分为三类:
黑色：已经确定了起始状态到其的最短路
灰色：即将访问
白色：尚未访问
从起始状态开始（起始状态标黑），将其能到达的所有状态标灰，确定他们的G值（暂时）、H值，并算出F值。
接下来重复一下操作：

1. 寻找灰色状态中F值最小的，成为当前状态
   
2. 当前状态标黑(即G值已确定)
   
3. 对于当前状态能到达的状态：
   1. 如果它是黑色，则略过。
   2. 如果它是白色，计算它的G、H、F值，并标灰，把当前状态作为其父状态。
   3. 如果它是灰色，检查G值能否更新，若能，则更新G、F，并将其父状态改为当前状态。
4. 若目标状态被标黑，则最短路径已找到。
5. 若目标未黑而已没有灰色状态，则路径不存在。

Dijkstra仅以最短路径(即A*中的G)为优先搜索的判断依据；A*加入了H(n)更关注到目标状态的最短路。
Dijkstra可应用于抽象的图模型，而A*因为需要构建H(n)估价函数，若图比较抽象，则构建有困难。

有几种不同的构建方法。

1. 直线距离。
2. 曼哈顿方法，即在瓦块图中，水平距离加垂直距离。