论文部分内容阅读
随着计算机网络技术和地理信息技术的发展,GIS技术得到了广泛的应用。网络分析是GIS研究的热点和难点。最短路径分析是GIS中网络分析的一项重要的功能,它等价于图论中的节点间求解最短路径问题。最短路径算法的要求是速度快,内存占用少,即尽可能降低算法的时间复杂度和空间复杂度。随着代数学的发展,各种算法不断出现。
Dijkstra算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径;其主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。因此有人提出了启发式搜索算法。启发式搜索是指优先搜索特定信息节点的算法;算法的创新之处在于选择下一个被搜索节点时引入了已知路网的信息,对当前节点距目标点的距离进行评估,作为该节点属于最优节点可能性的评价指标,具有最优目标函数的候选节点作为下一个路径节点得到优先选择。[1]A*算法就是一种经典的启发式搜索算法,许多文献都对A*算法进行了研究。
本文从数据结构和算法本身对A*最短路径算法做了优化和改进,使之搜索效率得到提高,本文的研究工作包括:
1、详细介绍了目前所流行的各种最短路径算法;详细分析了A*算法的基本思路,研究了经典的A*算法及其实现。
2、分析了传统的A*算法的不足,对A*算法的估价函数进行了改进:提出在估价函数中引入距离和方向两个要素,并且将距离和角度进行归一化处理,避免了距离方向单位不统一的问题。对以往算法open表中的节点排序的无序性,使用二叉堆排序方法进行优化,提高了节点的搜索效率。
3、对优化的A*算法进行实验,以C#和Arcengine9.3为开发环境,采用海南省交通图,分别取不同的路段,与其他算法的实验结果进行了对比。