A*算法是一种典型的启发式搜索算法，所谓启发，是指利用已知的全图信息，进行有方向性，有目的性的搜索。
设起始节点为 s(start），终点为g(goal)，首先从A算法出发。
一、评价函数
A算法的评价函数：f(n) = g(n) + h(n)
g*(n)：从s到n的最短路径的耗散值
h*(n)：从n到g的最短路径的耗散值
注意这里的带星号的都是最短路径
g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值
这样，我们可以使用f(n)对带扩展的节点进行评价。
二、伪代码
深搜广搜的基础，A算法的框架非常简单，要点是：维护一个优先级队列，反复弹出最小f的节点，之后遍历弹出节点的
周围节点，更新其f值。如果弹出了终点或者open表为空，即退出。
OPEN={s},f(s)=g(s)+h(s)
WHILE OPEN is not empty:
n=FIRST(OPEN)
IF goal==n: THEN EXIT
REMOVE (n,OPEN) AND ADD(n,CLOSED)
EXPAND(n), for all neighbor mi of n:
update f of mi
f=g(n,m)+h(mi)
ADD（mi,OPEN）,标记指针
OPEN表节点按照f值排序
三、具体实现：
针对不同的问题，可以有不同的方法，网上也有不同的模板，以地图网格搜索为例子。可以设定一个map类，一个node类，一个Astar类
node中的属性包括 x,y,father,G,H,F，更新父节点和f值的方法。Astar主要有 expand方法、寻找最小F值节点方法，以及findpath方法。
https://github.com/wenzong666/A_star-in-map_search.git
四、八数码问题中的A*
网格搜索中基本的A*较为直观。同样，在经典的八数码问题中，也可以应用A*算法。应用A*时，我们需要定义node,g,h。这个问题中，g（n）代表初始状态到现在状态所需的步数，h(n)为从该节点到最终节点必须至少要的步数的估计，或者说，h(n)为当前节点“不在位”的将牌数，如下图，当前状态的不在位数字为1 2 6 8，h(n)=4
八数码问题中，对给定任意一个初始状态，要先判断是否可解。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。逆序数为偶数的排列称为偶排列。由于最终的目标状态是：012 345 678 ，显然逆序数为0，为偶排列。可用此条件判断可解与不可解。
五、A*与A算法
A算法是一种启发式的搜索算法，根据搜索过程中选择节点的范围，分为全局择优和局部择优搜索算法。
全局择优即，从open表中所有节点中选择f最小的节点扩展，一般的A算法既是如此。取f=g，代价树的广搜。取f=d属于广度优先搜索
局部择优每次从刚生成的节点中选择最小f进行扩展。这种算法，如果取f=g，退化为代价树的深搜，如果f=d即为深搜。d代表深度。
估价函数的选择十分重要，A*算法既是在A算法基础上，对估价函数加以限制得到的。满足条件，则若有解一定能找到最优解，并提高了效率。
在A算法中，如果限制，
g(n)>0
h(n)≤h*(n)，则A算法成为A*算法。
A*算法是可纳性。（当路径存在，则必然在有限步内找到，并结束）
A*算法的最优性。即满足A*条件情况下，h(n)越大越好，越大说明启发信息越多，对于两个A*算法，如果一个算法所有节点的h(n)均大于另一个，则该算法拓展的节点必然是另一个的子集。（意味着扩展的节点更少）
六、A*算法的改进
A*算法中，对每次拓展的节点n，需要检查子节点是否在open，closed表中，
在open表中，要比较f值以决定是否修改父节点。在closed表中，需要比较f值决定是否修改父节点，以及其后继节点的父指针。
这样，导致多次重复扩展同一个节点，导致搜索效率下降。
如果每次扩展节点的时候，能够保证已经找到了最短的路径，那么就不必检查当前节点是否在closed表中，因为进入closed表的节点都找到了从起始点s到其本身的最短路径，
突破口：H值估计的要合理，即应该满足单调条件。什么意思？如下图，父节点的h <= 子节点的h+ c（父，子），才算合理，因为子节点又走了一段路，包含信息更多，子节点的h+ c（父，子）应该更接近父节点的h*。
对上述八数码问题，h为“不在位”的将牌数，易证满足单调条件。
则我们选取h时如果满足单调条件，那就非常不错了，如果不满足，我们也可以做一些适当的优化
一些结论：
OPEN表上任以具有f(n) < f*(s)的节点定会被A*扩展。
A*选作扩展的任一节点，定有f(n)≤f*(s)。
当h(n)恒等于0时，h为单调的。（暗示dijkstr算法，扩展一个节点时必然找到了这个最短路径）
前两条告诉我们，在open表中存在着一个分界点，f值小于它，则一定会被拓展，在这个领域内无关顺序，之后的一定不会扩展，但是，我们不知道这个分界确切的大小，但是，我们可以用 fm：到目前为止已扩展节点的最大f值 来代替它。因为该节点被扩展，它一定小于这个分界，所以可以暂时用它来分界。