基本内容

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为： f(n)=g(n)+h(n),

其中f(n) 是节点n从初始点到目标点的估价函数，

g(n) 是在状态空间中从初始节点到n节点的实际代价，

h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

估价值与实际值越接近，估价函数取得就越好。

例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny) *(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。

conditions of heuristic

Optimistic (must be less than or equal to the real cost)

As close to the real cost as possible

主要搜索过程：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->

While(OPEN!=NULL)

{