A* 算法是启发式搜索算法中的经典，经常应用于图搜索、路径搜索和规划中。这里以八数码问题状态空间图的搜索为例，初步介绍以A*算法为代表的启发式搜索。
搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略：广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。
为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A* 如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值。
一、启发性信息和估价函数
1.启发性信息：
启发式搜索是利用知识来引导搜索过程的，达到减少搜索范围的目标，使得尽量先走“最有希望的方向”，从而降低问题复杂度。这里就是要根据知识，设计启发性信息（启发函数），启发性信息可以：
1）帮助确定扩展节点的信息
2）有效地帮助决定哪些后继节点应被生成
3）能决定在扩展一个节点时哪些节点应从搜索树上被删除
启发性信息的设计至关重要，太弱可能就起不到效果，甚至退化为盲目搜索，太强就会可能导致找不到最优的解。
2.估价函数：
Evaluation Function：是一种对于节点“希望”的度量，表示这个节点在通向目标节点最佳路径上的“希望”或者概率，以此为指导选择优先扩展的节点。
估价函数的选取有很多方式：节点处于最佳路径上的概率；节点与目标节点集之间距离的度量或者差异的距离；根据状态优劣的打分等等。
注意：估价函数和之前提到的代价函数不一样，代价函数是预先知道的，而估价函数是根据知识预测得到的
二、启发式搜索过程（A和A*算法）
1.A算法
对于求解过程中，启发式搜索与盲目搜索的区别就在于对于OPEN表的重排，优先选择最优希望的节点扩展。
重排的依据就是：从起始节点到达该节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价，即
f(n)=g(n)+h(n)
2.A*算法
对于A算法中，g(n)和h(n)，尤其是h(n)该如何选择呢，选择如果超过实际代价太多，也就是太强，可能会找不到解；太弱就会在搜索过程中，扩展一些多余的节点，对于具体问题要根据具体知识进行设计。这里定义如果对于所有的n都有h(n)≤h* (n)，也称h(n)为h* (n)的下界，则是一种相对保守的搜索，但是这样是可纳的。
采用h*(n)的下界h(n)为启发函数的A算法，称为A* 算法。当h=0时，A* 算法就变为有序搜索算法。
上图中，f*(n)=g*(n)+h*(n)是从s经过n到g的最优路径的实际代价，而g(n)和h(n)就分别是对实际代价的估计！
所以在设计估价函数时，要尽可能的使得和h(n)逼近h*(n)，但又不超过h*(n)，这样得到的时完备可纳的，有时复杂度最小的，但是如何知道有没有超过h*(n)呢？感觉还是需要具体问题具体分析。
3.求解过程描述
搜索过程大致和盲目搜索一样，只是在OPEN表排序不同，其中涉及到的排序算法，去重算法等都会影响算法的效率。
对于上面图中“调整亲子关系和指针”：
1）如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f把它添入OPEN表，从j加一指向父辈节点i的指针。
2）如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值.。如果新的f值较小，则作以下几种操作：
a. 以此新值取代旧值
b.从j指向i, 而不是指向它的父辈节点
c.如果节点j在CLOSED表中, 则把它移回OPEN表
4.八数码问题设计估价函数
这里以之前提到的八数码问题为例：
1）估价函数1：f(n)=d(n)+w(n)
d(n)为n的深度
w(n)为不在位的棋子数
这样w(n)≤h*(n)，是满足A* 算法的限制条件，所有一定能找到最优解，但是这样设计估价函数并不是最优的。
2）估价函数2：f(n)=d(n)+p(n)
p(n)为不在位的棋子与其目标位置的距离之和
这样p(n)≤h*(n)，也是满足A* 算法的限制条件。
w(n)是不在位的棋子数，不够贴切，错误选用节点加以扩展，而p(n)是更接近于h*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋子在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数），也就是启发性信息更多了。
5.启发式搜索特点和实际工程应用
1）对于启发性信息：设对同一个问题定义了两个A* 算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) > h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。
2）在实际应用中理论上是设计接近、又总是≤h*(n)的h(n)，但是这种设计往往也要消耗大量的时间，如果h(n)本身设计的复杂，每次计算时消耗在h(n)上的复制度也就会增加，使得求解变慢。
3）对于搜索深度和启发性信息的权衡：
f(n) = g(n) + wh(n)
搜索图的浅层时，让w取较大值，突出启发式函数的作用，加速向纵深方向搜索。
搜索到较深的层次时，让w取较小值，以使g(n)所占权重大，并确保wh(n)≤h* (n)，引导搜索向横广方向发展，寻找到较短的解答路径。
