A-Star

求解最短路径最有效的直接搜索方法
公式表示为： f(n)=g(n)+h(n)
f(n) 是从初始状态经由状态n到目标状态的代价估计
g(n) 是在状态空间中从初始状态到状态n的实际代价
h(n) 是从状态n到目标状态的最佳路径的估计代价
路径搜索问题，状态就是图中的节点，代价就是距离
FGH示意图如下所示（图中格子左下角为G值，右下角为H值，左上角为F值）：

使用了两个状态表，分别称为Open表和Closed表。
Open表由待考察的节点组成，
Closed表由已经考察过的节点组成。

（1） 如果相邻节点既不在Open表中，又不在Closed表中，则将它加入Open表中；
（2） 如果相邻节点已经在Open表中，并且新的路径具有更低的代价值，则更新它的信息；
（3） 如果相邻节点已经在Closed表中，那么需要检查新的路径是否具有更低的代价值，如果是，那么将它从Closed表中移出，加入到Open表中，否则忽略

欧氏距离里的距离计算：

曼哈顿距离（Manhattan distance）

曼哈顿距离是：起点到终点的要穿越的行和列的单位距离的总和。
欧式距离是起点和终点的直线距离。