A搜索和A*搜索的区别及优劣分析

在代价树的宽度优先搜索中，需要计算从初始状态节点到每个节点的代价信息（用函数g（n）表示，称为代价函数）。在贪心法搜索中，则用到了启发函数（用h（n）表示）。为了结合两者，引入f（n）=g（n）+h（n）。该函数称为评估函数或估价函数（evaluation function）。它既包含了节点n距离初始状态节点的实际距离g（n），也包含了该节点距离目标状态节点的启发估计距离h（n），也就是f（n）包含了从初始状态节点经过节点n到目标状态节点的总距离。

这样，把贪心法搜索中对于OPEN表中待扩展节点的选取策略由通过启发函数h（n）来选取改为通过评估函数f（n）来选取，就变成了A搜索。h（n）在f（n）中所占的比重越大，就代表着启发性越强。当f（n）中的h（n）项为0时，A搜索就可以看作是代价树的宽度优先搜索；而当f（n）中的g（n）项为0时，A搜索可以看作是贪心法搜索；如果两项都为0，即f（n）为0，就又可以看作是不考虑代价的宽度优先搜索了。

假如定义h*（n）为从节点n到目标状态节点的最短路径的实际代价（通常，这个值并不可能实际求出），而选用的h（n）是估计出的最小代价，判断估计出的h（n）是否总是小于或等于最短路径的实际代价h*（n）还是比较容易的，即判断h（n）≤h*（n）一般是可行的。比如在地图路径搜索问题中，选用两点之间的直线距离作为h（n），因为两点之间直线距离最短，所以可以判断h（n）≤h*（n）肯定成立。

如果A搜索中，h（n）≤h*（n）始终成立，那么就可以称为A*搜索。A*搜索结合了代价树的宽度优先搜索和贪心法搜索两者的优点，它使用评估函数f（n）来选取待扩展节点。

先来看一些和启发函数有关的概念。

（1）可采纳性（admissibility）。

启发函数的可采纳性是指启发函数永远不会高估到达目标状态节点的实际代价，即h（n）≤h*（n）。它能保证只要图中存在从初始状态节点到目标状态节点的最优路径，搜索算法就可以找到该路径。

（2）一致性（consistency）。

一致性也称为单调性（monotonicity），是指对于任一节点ni，如果可以到达nj，即nj是ni的后继状态节点，代价为cost（ni，nj），那么ni到终点的启发值h（ni）和其后继状态节点h（nj）到终点的启发值之差不能大于ni到nj的实际代价，即h（ni）-h（nj）≤cost（ni，nj），并且目标状态节点的启发值为0，即h（GOAL）=0。

如果启发函数满足一致性，那么就可以保证A*搜索每次选择的到当前节点的路径就是到该节点的最优路径，因此如果后面扩展到已经在OPEN表或CLOSED表中的某个节点时，可以直接丢弃该节点而不必处理，使得算法的实现更简单。

可以证明，处处满足一致性（单调性）的启发函数是满足可采纳性的，但是满足可采纳性并不意味着处处满足一致性，所以在图的A*搜索中，如果采用的是满足一致性的启发函数，就满足最优性，如果只是满足可采纳性，增加检查OPEN表和CLOSED表中的节点步骤，也可以满足最优性。所以，我们说所有的A*搜索算法都是可采纳的，是满足最优性的。

（3）信息度（informedness）。

哪种启发信息会更好？找到最短路径的能力更强？为了对不同的启发信息进行比较，引入了信息度的概念。

对于满足A*搜索要求的两个启发函数h1（n）和h2（n），如果对于状态空间的所有状态都满足h2（n）≥h1（n），那么就称h2（n）比h1（n）具有更高的信息度，信息度更高的启发函数能使得A*搜索算法搜索更少的状态，更快地找到最短路径。

从以上的分析可以知道，A*搜索和一般搜索的过程也是一样的，只是扩展节点加入OPEN表的方式不同——需要用到评估函数f（n）。

图3.11所示为代价树的宽度优先搜索、贪心法搜索和A*搜索的对比，深色方块表示已经扩展了的位置节点，对应的数字表示采用曼哈顿距离分别计算代价函数g（n）、启发函数h（n）以及评估函数f（n）时，各位置节点所对应的值。地图以左上角为（0，0），初始状态节点和目标状态节点坐标分别为（0，12）和（13，1）。(www.xing528.com)

图3.11　代价树的宽度优先搜索、贪心法搜索、A*搜索三种搜索对比

从图3.11中可以看到，代价树的宽度优先搜索探索过的节点最多、效率最低；贪心法搜索用了最小的搜索范围就找到了一条通向目标状态节点的路径，但是这并不是最短路径；A*搜索的搜索范围介于代价树的宽度优先搜索和贪心法搜索之间，它和代价树的宽度优先搜索一样可以保证找到的路径是最短路径。

下面，以八数码拼图游戏为例，分析A*搜索的应用方法，详细的Python实验代码讲解将在实验参考部分给出。

例3.3　八数码拼图游戏：设在一个3×3的方格棋盘上，摆放着8个数字1，2，3，4，5，6，7，8，还有一个方格是空的，空格旁边的数字可以移动到空格中，图3.12（a）所示为初始状态，图3.12（b）所示为目标状态，使用A*搜索来寻找移动数字，从而将棋盘从初始状态变到目标状态的路径，设计其评估函数。

图3.12　八数码拼图游戏（二）

解　参考第2章的内容，将数字的移动转换为空格的移动，这样能简化移动的规则。在第2章的介绍中，对于可以扩展的状态选取方案，选用的是和目标状态进行比较，统计和目标状态不一致的数字的个数。这里为了编程方便，将空格也作为一个数字进行了比较，还有许多方案中只统计1到8这8个数字是否在对应位置而不考虑空格位，计算值稍微有点区别。选不一致的个数最少的状态节点进行扩展，相当于计算和目标状态节点的差距，这其实就是一种启发函数。这里将它设为h1（n）（放错位置的数字的个数）。

由于h1（n）只估计了放错位置的数字的个数，该值比起从错误位置到正确位置要移动的步数肯定要小，即满足h1（n）≤h*（n），因而该启发函数是可采纳的。

将搜索的深度d（n）设为代价函数，即g（n）=d（n），于是可以得到评估函数为f（n）=d（n）+h1（n）。

接下来就是搜索的过程，如图3.13所示，其中粗箭头线即为搜索得到的路径。

图3.13　八数码拼图游戏使用A*搜索的过程

本题中，还可以选用另外一种启发信息，比如计算所有不在正确位置的数字到目标位置的移动步数或直接距离之和。这样，是否会有更好的信息度呢？在后面的动手实验中，可以通过修改启发函数进行验证。

这里还提供了另一种启发信息供实验验证。可以按顺时针方向计算每个非中心位置的数字，如果它后面所紧跟的数字与目标位置一致，则该数字计0分，否则计2分；如果中心位置的数字与目标数字一致，则计0分，否则计1分，将所有的和当作启发信息。