A*算法
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)
{
从 OPEN 表中取估价值 f 最小的节点 n;
if(n 节点==目标节点) break;
else
{
if(X in OPEN) 比较两个 X 的估价值 f //注意是同一个节点的两个不同路径的估价值
if( X 的估价值小于 OPEN 表的估价值 )
更新 OPEN 表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个 X 的估价值 //注意是同一个节点的两个不同路径的估价值
if( X 的估价值小于 CLOSE 表的估价值 )
更新 CLOSE 表中的估价值; 把 X 节点放入 OPEN //取最小路径的估价值
if(X not in both)
求 X 的估价值;
并将 X 插入 OPEN 表中; //还没有排序
}
将 n 节点插入 CLOSE 表中;
剩余10页未读，继续阅读
资源评论
