《毕业设计基于DIJKSTRA的最短路径搜索算法的优化及应用论文》由会员分享，可在线阅读，更多相关《毕业设计基于DIJKSTRA的最短路径搜索算法的优化及应用论文（49页珍藏版）》请在金锄头文库上搜索。
1、 毕业设计（论文）题 目 基于Dijkstra的最短路径搜索算法的优化及应用 姓 名 学 号 专业班级 指导教师 分 院 完成日期 摘 要最短路径分析是GIS地理网络分析功能中的一个关键问题。Dijkstra算法是计算最短路径的经典算法，是许多工程解决最短路径问题的理论基础。传统Dijkstra算法在求解节点间最短路径时，对已标识节点以外的大量节点进行了计算，从而影响了算法的速度。本文在对传统Dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做了处理，而不涉及到其他节点。因此，在优化算法中计算的节点数大幅减少，提高了算法的速度。本文通过实验和实际应用对改进后的算
2、法进行了验证。关键词：最短路径；Dijkstra算法；优化AbstractShortest path analysis is the key problem of network analyses， Dijkstra algorithm is a classic arithmetic for the shortest path. It is the academic foundation that many engineerings were solved in the shortest path issue. When a shortest path between nodes is sea
3、rched with Dijkstra algorithm，a lot of nodes away from lagged nodes are involved，so that the efficiency of Dijkstra algorithm is lowAn optimization algorithm is presented in this paper based on analysis of Dijkstra algorithmOnly these nodes that the neighbor of nodes in the shortest path are process
4、ed，and other nodes are not processed. Therefore，the number of processed nodes is largely reduced in the optimization algorithm，and efficiency of the optimization algorithm is improvedThe improved algorithm is proved to be correct and efficient by experiments and practical application.Keywords: the s
5、hortest path；Dijkstra algorithm；optimizationI目 录摘 要IAbstractII第1章概述11.1国内外最短路径算法概况11.1.1国内外最短路径研究的主流与方向11.1.2国内外主流算法及其简要展开21.1.2.1A*算法321.1.2.2遗传算法421.1.2.3Dijkstra算法31.1.3经典Dijkstra算法存在的问题41.2研究的意义41.3本文研究目标和内容4第2章Dijkstra经典算法研究62.1Dijkstra算法的原理及应用62.1.1Dijkstra算法原理62.1.2Dijkstra算法应用72.1.3Dijkstra算
6、法的优缺点102.2以Dijkstra算法为基础算法进行优化的原因122.2.1Dijkstra算法与其他主流算法的比较5122.2.1.1搜索速度比较122.2.1.2搜索成功率比较13第3章Dijkstra优化算法研究143.1多种Dijkstra优化算法的研究6143.1.1第一类优化算法减小算法中成功搜索的搜索范围143.1.2第二类优化算法改进算法的存储结构143.2本文对Dijkstra优化算法的研究153.2.1优化算法的目标153.2.2优化算法思路153.2.3优化算法描述163.2.4优化算法的特点203.3优化Dijkstra算法与原Dijkstra经典算法比较20第4章
7、优化Dijkstra算法的应用214.1优化算法在上海市物流中的实现214.1.1地图说明214.1.2属性数据库设计224.1.3算法实现234.1.4算法优化前后对比25第5章总结与展望265.1全文总结265.2展望26参考文献27附 录29致 谢35III第1章 概述1.1 国内外最短路径算法概况1.1.1 国内外最短路径研究的主流与方向最短路径这一重要问题早在20世纪初就已经得到人们的高度重视，当时也有许多科学家研究这一重要问题的求解方法。但直到1959年荷兰计算机科学家Edsger Wybe Dijkstra (迪杰斯特拉)才给出这一问题求解的基本思想，并给出了算法。当时的Dijk
8、stra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题。后来这个算法就成了众所周知的Dijkstra算法，也成为了一代经典。1 现今比较流行的最短路径规划算法主要有以下三类：第一类是基于图论理论的算法；如Dijkstra及其改进算法，Floyd算法等；第二类则是基于传统人工智能理论的算法，如A*机器改进算法，深度有限、宽度有限算法等；第三类则是基于智能控制技术的算法，如人工神经网络算法、遗传算法等。特别是近10年来，智能控制技术在路径规划问题中得到广泛的应用，人们的研究兴趣也逐渐从对前两类算法的改进转到了对第三类算法的进一步研究中。当前对于最短路径的相关研究主要包含两方面
9、。第一方面为最短路径问题（完全信息情况下）。在这种确定情况下最短路径问题的研究中，Bellman（1958）、Dijkstra（1959）和Dreyfus（1969）已发展出许多高效算法。这些算法已成为确定情况下的经典算法。在不确定的情况下最短路径问题的研究包含以下几个方面：Frank（1969）和Mirchandani（1976）研究了路段长度随机变化的且非时间独立的情况下的最短路径问题；Loui（1983）、Muethy和Sarkar（1996）考虑不同的费用函数研究最短路径问题，他们的结论是当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题；Hall（1986）、LiP
10、ing Fu和L.R.Rilett（1998）、Elise和Hani（2000）研究了路段长度随机变化且时间独立情况下的最短路径问题；Tomas和Rajeev研究了路段长度为区间范围的最短路径问题。21.1.2 国内外主流算法及其简要展开1.1.2.1 A*算法3A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)实际
11、值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。A*算法是人工智能中一种典型的启发式搜索算法，算法的创新之处在于选择了下一个被探索的结点时引入了已知的路网信息和目标点信息，对当前点与终点的距离进行评估，作为选择下一路径结点的依据。通用的A*算法可采用四方向，八方向，对于矢量路网则可采用遍历相连路径法进行路径探索。在城镇地价定级估价中，不考虑路网，可采用栅格八方向法。通过A*算法可以寻找任何一个因素因子与其它各点之间的最短路径。它不用遍历整个搜索空间，而是根据所选择的启发式函数朝着最有希望的方向前进。它的搜索速度虽然较快，理论上也能找到最优
12、解，但在实际应用过程中往往由于启发式函数选取不当而经常找不到最短路径，搜索的成功率并不是很高。1.1.2.2 遗传算法4遗传算法（Genetic Algorithms，简称GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。GA把每一个可能的解编码为一个向量，称为一个染色体，向量的每一个元素称为基因。所有染色体组成群体。并按预定的目标函数对每个染色体进行评价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体，计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度
13、低的染色体，留下适应度高的染色体。由于新群体的成员是上一代群体的优秀者，因而在总体上优于上一代。GA就这样反复迭代，直至满足某种预定的优化指标。上述GA的工作过程可用图1.1简要描述。Y问题的初始（侯选）解种群满足预定指标编码为染色体（向量）种群P（t）计算各染色体适应度通过遗传运算存优去劣种群P（t+1）复制交换变异种群P（t）种群P（t+1）解码染色体问题解答空间N图 1.1 遗传算法工作原理示意图1.1.2.3 Dijkstra算法Dijkstra算法的基本思想是，设置一个顶点的集合S，从源点S到集合中的各顶点的最终最短路径的权值均已经确定。算法反复选择具有最短路径估计的顶点 iVS，并
14、将i加入S中，对i的所有出边进行松弛（本文第2章节将对经典Dijkstra算法做详细研究）。1.1.3 经典Dijkstra算法存在的问题（1）原始Dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义NN的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存。（2）原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型。网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法。根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率。1.2 研究的意义随着社会的不断进步，最短路径算法在人们的日常生活显得越来越重要。每天开车去上
