文档介绍：重庆大学
硕士学位论文
交通网络中最短路径算法的研究
姓名:戴文舟
申请学位级别:硕士
专业:控制理论与控制工程
指导教师:柴毅
20040428
要摘应用。网络分析作为钪饕5墓δ苤唬诘缱拥己健⒔煌糜巍⒊鞘泄婊以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。最短路径问题是网络分析中最基本的问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。最短路径分析在汽车导航系统以及各种城市应急本文简述了有关地理信息系统的一些基本概念,包括地理信息系统概念、地理信息系统数据模型、地理信息系统数据的组织和管理、地理信息系统中的网络分析,概述了地理信息系统的发展和应用状况。针对城市交通道路网的特点,对基于城市道路网的最短路径分析的关键技术进行了研究和分析,着重分析研究了城市交通道路网的矢量地图表达、网络拓扑根据型缂扑愕氖导是榭觯油缃峁沟耐仄吮硎疽约癉惴ㄖ锌速搜索技术的实现入手,提出了一种基于椭圆限制区域的优化二叉堆优先级队列的改进型最短路径算法。此算法是在对城市交通网络空间分布特征进行统计分析的基础上,针对具体的起、终节点,设定合理的椭圆限制搜索区域,以减少算法的搜索规模;并且利用两点间直线段最短的原理,以当前节点的邻接点与当前点和终点连线夹角最大作为贪婪搜索策略。该算法能够有效降低算法性能够满足求解交通网络最短路径的要求,并能够延伸到其它管网如电力和光缆等的维护和抢修等应用领域。随着计算机及网络的普及和发展,蚱淝看蟮墓δ艿玫饺找婀惴汉蜕钊氲系统中有着广泛的应用。结构的提取和构建、最短路径算法的高效实现等关键技术。的时间复杂性,提高系统的运行效率。实际应用表明,该方法兼具灵活性和实用关键词:最短路径算法,,地理信息系统,网络分析重庆大学硕士学位论文中文摘要
,.,珼琻西琣,重庆大学硕士学位论文英文摘要、瓵瑃瑆,,.琣珿,、,琲,甀,..:.、
绪论课题的背景,简称是一种将空间位置信息和属性数据结合在一起的系统。随着计算机及网络的普及和发展,地理信息系统已形成了一门以应用为目的的信息产业,蚱淝看蟮墓δ艿玫酵及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,而网络分析中最基本最关键的问题是最短路径问题。它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。从网络模型的角度看,最短路径分析就是在指定网络中两结点间找一条阻碍强度最小的路径。根据阻碍强度的不同定义,间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等【俊W疃搪肪斗治鲈谑导手谐S糜谄档己较低骋约案髦殖鞘杏毕低车的抢修问题,通讯光缆的最快抢修问题有些系统一般要求计算出到出事点地最短路径应该在~内,在行车过程中还需要实时计算出车辆前方地行驶路线等。因此最短路径分析不仅应能表征实际的道路网,而且要有足够快的响应速度。具体对于基于某鞘锌焖傧赖度系统来说,当火灾发生时,准确确定报警点及着火点位置,自动通知火场周围有关单位,并快速生成通往火场的最短行车路线是系统中关键性的问题之一,高效率的实现可以提高消防补救的快速反应能力和整体指挥作战能力最短路径问题一直是计算机科学、运筹学、交通工程学、地理信息学等学科算机科学及运筹学领域,在算法的设计过程中只考虑了抽象网络的拓扑特性,力求通过各种新型的计算机数据结构和运筹学方法,从理论上减少算法的时间复杂度,而忽略了具体的网络可能具有的空间分布特性。而这一点正是描述交通网络网络空间分布特性对最短路径算法进行改进,以减少算法的搜索规模,提高算法运行效率,是本文所要探讨的闻题。最短路径问题是交通网络分析中的一个重要问题,也是交通地理信息系统地理信息系统广泛和深入的应用【【网络分析作为钪饕5墓δ苤唬诘缱拥己健⒔煌糜巍⒊鞘泄婊最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时匪警、儿鹁约医疗急救系统褂懈髦窒呗繁U衔侍配电网的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现,各具特色“。由于这些算法主要诞生于计结构的稀疏图与其它描述拓扑结构的平面图的根本区别所在。如何有效利用交通械囊桓鲅芯咳鹊恪K亲试捶峙洹⒙废呱杓萍胺治龅扔呕侍獾幕重庆大学硕士学位论文髀
。单源最短路径问题的算法有很多种,从早期的基于限制条件的深度优先搜索算法、基于有向无环图的动态规划法、基于邻接矩阵的算法【”、到最大相关边法、最大相关点法、基于邻接表的算法、算法】【“、基于超图数据结构的深度优先椭圆搜索算法】等。时间复杂度、易实现性等方面各具特色。其中,采用贪心的启