A算法的改进课程设计毕业设计.docx

A算法的改进课程设计毕业设计.docxA*最短路径算法的改进
课程设计的目的
本课程设计是学习《数据通信与通信网技术》课程必要的教学环节。由于该课程是 专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方 法，课程设计训练也就成为了一个重要的教学环节节点信息，减小内存使用空间。实验结果表明，改进后的A* 算法的搜索效率得到了明显的提高。最经典的最短路径搜索算法是Dijkstra算法，属于 遍历搜索，它简单易用并总能搜索到最短路径。但是当网络中节点数较多时,该算法 搜索的结点数量会很大,效率非常低。因此有人提出了启发式搜索算法，如：局部择优 搜索法、最好优先搜索法、A*算法等。启发式搜索就是在状态空间中，对每一个搜索 的位置进行评估，得到最好的位置,从而在这个位置进行搜索直到搜索到目标为止。目 前在路径优化领域，最流行的启发式搜索算法当属由Har, tN订sson, Raphael等人首 先提出的A*算法。它利用启发函数来估计任意点到目标点的远近程度，从而减少搜 索空间，提高搜索效率。许多文献都对A*算法进行了研究，并且都提岀在估价函数中 引入距离和方向两个要素。但是距离和方向的单位是不统一的，所以在利用时会出现一 些问题，本文针对这一问题进行了研究,并对估价函数进行了改进。另外,为了进一步提 高算法的运行效率，本文在算法运行结构上，采用k- d树空间索引结构，降低内存存储 空间。实验结果证明了改进后算法的合理性和可行性。
设计的过程与分析
A*算法是建立在Dijkstra和BFS (最好优先搜索)算法基础上的。它的整体框架采 用遍历搜索法，但是它采用了启发函数来估计地图上任意点到目标点的费用，从而可 以很好地选择搜索方向。A*算法引入了当前节点j的启发函数f*( j),当前节点j的启 发函数定义为：f*(j)=g(j)+h*(j) (1)其中g(j)是从起点到当前节点j的实际费用的 量度，h*(j)是从当前节点j到终点的最小费用的估计。
注意到若h *(j) = 0,即没有利用任何全局信息，这时A*算法就变成了普通的 Di jkstra算法。因此普通的Di jkstra算法可 看作A*算法的特殊情形。h* (j)要满足 相容性条件：即不能高于节点j到终点的实际最小费用。可以证明，如果估价函数满足 相容性条件，且原问题存在最优解，则A*算法一定能够求出最优路径°A*算法的优 点在于利用启发函数，使搜索方向更加智能的趋向于终点，所以其搜索深度较小，搜索 的节点数少，故占用存储空间少，如图1所示。
图1 A*算法与Dijkstra算法搜索区域对比
A*算法的估价函数A*算法的关键在于设计一个合适的启发函数。有文献对其 特点进行了分析，认为启发函数f* (j)值是非递减的，只要能够满足相容性条件即估 价函数h* ( j)小于节点j到目标点的实际费用，它生成的路径一定是最优的。许多文 献都在估价函数的构造中引入了距离和方向两个要素，即：h*(j) = wl* L+w2*如图2 所示。
其中L表示当前节点到终点的欧氏距离，表示起点到当前节点的线段与当前节点到终 点的线段的夹角即SjE,有文献也用到了中间节点与关联节点的线段和关联节点与终点 的线段夹角NjEowl和w2分别是距离和角度的加权值,wl和w2的取值范围分别为055- 0. 65和0. 35-0. 45o但距离和角度的单位不统一的问题不能忽略，即使角度的单位为弧 度、距离的单位为千米，它们之间也很有可能出现距离值远大于角度值(即L)的情况, 特别是在大区域路径规划过程中，问题更明显。
而当L时，方向不再有约束力，而使得估价函数失去意义。
A*算法的运行结构当构造合适的估价函数后就要考虑算法的运行，目前大多数方 法是将全部数据读入到内存当中，然后搜索最短路径。从理论上讲，A*算法可以通过 搜索更少的节点完成最短路径的搜索。但是算法运行时，必须要考虑两个问题:一是数 据读取的速度。即使可以很快地将数据读入到内存中，我们也还要考虑第二个问题，即 系统内存的大小。如果系统内存足够大，在算法运行过程中，也将会出现对同一节点进 行重复的搜索，从而降低算法的运行效率。针对数据的读取问题，有学者提出了基于限 制区域的A*算法,减小数据的加载量。但是由于A*算法本身就是一种有损算法，这种 方法很有可能搜索不到最短路径，特别是在考虑道路属性信息和交通限制信息时。
关联节点j
改进的A*算法
A*算法估价函数的改进针对A*算法估价函数所出现的问题，我们将距离和角 度进行归一化处理,即首先计算当前节点所有关联节点相应的距离和角度值，然后求它 们的平均值即L,从而使得估价函数变为：h* (j) = wl* L + w2* (5)其中：L= L/L (6)=/(7)归一化处理以后，只考虑