发布时间 : 星期日 文章A算法估价函数分析及其改进探讨更新完毕开始阅读519772ec102de2bd960588a7
A算法估价函数分析及其改进探讨
来源:中国硕士论文网-www.masterlw.com
1 引言
A*算法是目前最流行的启发式搜索算法（Heuristic Search），该算法由Hart、Nilsson、Raphael 等人首先提出，该算法是建立在Dijkstra 算法的基础之上，创新之处在于探索下一个结点的时候，引入了已知的路网信息，特别是目标点信息，增加了当前结点有效评估，即增加约束条件，作为评价该结点处于最优路线上可能性的量度，因此首先搜索可能性较大的节点，从而减少了探索结点个数，提高了算法效率。
A*算法执行效率高低的关键在建立一个合适的估价函数,估价函数构造得越准确，则A*搜索的时间越短。经典A*算法在大范围地图情况下，搜索路径时存在很多不足，例如扩展节点空间比较大，运行时间比较长。本文针对这种情况，在详细分析估价函数特性的基础上，提出一种新的估价函数构造方法，对经典A*算法进行改进，提高了运行效率，并仿真验证结果的有效性。
2 估价函数
估价函数的任务就是估计待搜索结点的重要程度，给它们排定次序。评价函数f（x）可以是任意一种函数，如定义它是结点x 处于最佳路径上的概率，或是x 结点和目标结点之间的距离，或是x 格局的得分等等。一般来说，评价一个结点的价值，必须综合考虑两方面的因素：已付出的代价和将要付出的代价。在此，我们把评价函数f（n）定义为从初始结点经过n 结点到达目标结点的最小代价路径的代价估计值。
2.1 估价函数特性分析
在 A*算法中，结点n 的估价函数f（n）由以下公式给出： f （n） = g（n） + h（n）
g（n）是起始点到达n 的实际路径代价，h（n）就是n 到达目标点最短路径的启发函数。A*算法的估计函数具有以下一些性质： 1） 可采纳性
凡是一定能找到最佳求解路径的搜索算法称为可采纳的（admissible），数学上已严格证明A*算法是可采纳的。其充要条件是：对任意结点n,都有h（n） ≤ h' （n） , h‘（n）是n 到目标的实际最短距离。这时，也称h（n）是可采纳的。只有应用可采纳的h（n）的最好优先算法才是A*算法，否则只能算做A 算法。
2） 单调性
谓单调性就是指在A*算法中，如果对其估价函数中的h*（x）部分即启发性函数，加所以适当的单调性限制条件，就可以使它对所扩展的一系列节点的估价函数值单调递增（或非递减），从而减少对OPEN 表或CLOSED 表的检查和调整，提高搜索效率。
2.2 构造原则
通过对估价函数特性的分析，我们可以得出结论：启发函数h（n）必须可采纳，最好还具有单调特性，但单调特性不是必须的。
h（n）可采纳就一定能找到最短路径，但h（n）与实际值h’（n）不能差得太远。差得越远，A*最后的搜索拓扑就越接近一个完全的宽度优先搜索。最极端的情况：h（n）=0 时，A*就完全退化为宽度优先搜索。那么，h（n）要尽可能接近h‘（n）。理论上来说，h（n）=h’（n）是最好的，估计值就是实际值，但这在实际中是不可能达到的还有一点，关于启发函数h（n）的信息量问题，所谓h（n）的信息量，就是在估计一个结点的值时的约束条件，如果信息越多（或说约束条件越多），则估价函数越准，排除的结点越多，那么A*性能越好。宽度优先搜索之所以不可取，就是因为它的启发函数h（n）一点启发信息都没有。但是h（n）的信息越多，计算量就越大，耗费的时间也就越多。而一般的路径规划系统里通常要设置超时控制的代码，当内存消耗过大或用时过久就退出搜索。那么就应该适当的减小h（n）的信息量，即减少约束条件，但这样又会导致算法准确性下降，所以设计h（n）时需要根据具体应用环境来进行综合平衡设计。
2.3 常用的估价函数计算机硕士论文
在实际情况中，通常是使用 h（n）的实值函数，再通过试验优化。根据这些积累下来的经验合理地构造估价函数，可以得到更好的结果。常用的估价函数有以下几种：
设xi 的坐标为（x，y），终点xe 的坐标为（xe，ye）。 1） 曼哈顿距离
标准的估价函数是曼哈顿距离（Manhattan distance）即：两点在南北方向上的距离加上在东西方向上的距离。 2） 对角线距离
如果在搜索中允许对角运动，那么需要一个不同的启发函数。（4 east，4 north）的曼哈顿距离将变成8*D。然而，可以简单地以（4northeast）代替，所以估价函数应该是4*D。 3） 欧几里得距离
如果单位可以沿着任意角度移动（而不是网格方向），那么可以使用直线距离。
比较这三种常用的估价函数，计算两点间的欧几里得距离是最基本的，但是常常与实际情况相距甚远，对角线距离和曼哈顿距离在计算效率上比欧几里得距离高，对角线距离需要允许对角运动，在城市地图上的路径规划来说，曼哈顿距
离更加适用。
估价函数与搜索规模也有关系，我们通过求和后再乘以一个系数W 来适应： 还有一种比较常用的估价函数构造方法——加权A*算法：任一时刻的h`（n）决不会超过实际值h（n）的估计，其中h（n）为从网格上的方格移动到终点的实际移动耗费。因此考虑改变估价函数中的h`（n）在f（n）中的权重，减少h`（n）在估价函数中所占的比例，这里令f（n）=g`（n）+mh`（n） （m 为小于1 的正数）。A*算法中g`（n）与h`（n）的权重是均等的，两者为1:1 的关系；Dijkstra 算法中h`（n）的权重为0（m=0）。因此，对于Dijkstra 算法，当逐步加大h`（n）的权重时，增大m，计算时间被缩短，路径却被优化。本文的目标是找到平衡点，在保证路径最优的情况下，实现计算时间最短，同时满足A*算法的可接纳性。
3 新的估价函数
以上这些启发函数都具有相容特性，可以简化搜索所使用的数据结构，但它们相对来说都比较简单，仅仅考虑了距离而忽略了方向，在一些不太复杂的地图中使用价值比较高，但不太适用于地形复杂的地图。在地图比较复杂，范围比大的情况下，可以考虑引入方位和距离两方面的因素，提高启发函数的信息量，加快搜索的速度和准确程度，提高运行效率。
4 试验仿真和结果分析
仿真平台开发基于 PC 机，开发语言为C++，GUI 开发使用了开源的QT 工具包。Qt 是一个跨平台的C++图形用户界面应用程序框架。它提供给应用程序开发者建立艺术级的图形用户界面所需的所用功能。Qt 是完全面向对象的，很容易扩展，并且允许真正地组件编程。
为了使仿真结果准确，对于每一幅地图，各仿真十次，最后对仿真结果进行统计，取平均值作为最后结果。
从三种算法的仿真结果可以看出，从实验结果的总体情况看，这些算法基本反映了同一个问题，在搜索的过程中搜索结点个数A*和Dijkstra 都大于或等于改进的A*算法。这也直接导致另外一个参考数据——运行时间的排列问题。这两个主要的参数说明了算法的效率。
从表1和表2中可以发现，改进的A*算法搜索出的路径结点数少于传统的A*算法和Dijkstra算法，从搜索的时间上可以发现，改进后的A*算法一有明显提高。传统的A*算法是自始至终把起点和终点对当前搜索结点的影响等权化。而改进的A*算法，由于新的启发函数引入方位和距离两个因素，加大了启发的信息量，对比与经典A*算法来说，搜索的时间方面大大降低了，同时在搜索的扩展节点数目方面也大大减少。
三幅对比的路径搜索图中可以发现上述结果更加明显。传统的A*算法是自
始至终把起点和终点对当前搜索结点的影响等权化。而改进的A*算法，不仅考虑了权重问题而且考虑了方向问题，更像是一个人在城市里找路径。在开始走的时候，我们都会先朝着目标结点的方向走，考虑走的是不是最短路径更少一些，而当快到目的地的时候，就会考虑是走那条路更快到达目的地。从而更加考虑选择的路径的实际距离，也就是加大实际距离的权重。按照传统A*算法，我们也必然会走很多弯路最后才发现哪条路更好，也就会搜索更多的结点。
5 总结
本文要完成了对 A*算法中估价函数的特性分析，并提出了一种新的启发函数的构造方法，通过仿真是分析记过，可以看出：改进的A*算法不仅优化了路径轨迹，而且在路径计算时间和搜索扩展节点的数目上都比经典A*算法有了大幅的降低，表明该改进具有实际应用价值。