A算法估价函数分析及其改进探讨.docx

本文格式为Word版，下载可任意编辑A算法估价函数分析及其改进探讨 A算法估价函数分析及其提升探讨 来源:中国硕士论文网- 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*算法有了大幅的降低，说明该提升具有实际应用价值 — 7 —。