数模相关方法

计算机技术与发展第20卷 第1期 20 No.1 Vol.2010年1月Jan. 2010COMPUTERTECHNOLOGYANDDEVELOPMENT
城市路网的最短路径并行求解
卢 照,师 军,于海蛟,方 昕
(陕西师范大学计算机科学学院,陕西西安710062)
摘 要:随着当前城市规模的不断扩大,交通网络变得越来越复杂,计算最短路径问题不仅要消耗大量的空间资源,同时也花费了更多的时间资源。为了提高最短路径求解的实时性,基于城市小区将复杂网络进行化简,在各个小区中寻找代表节点,将其他无关的节点看做透明的不参与计算,保持原有网络的特性。然后采用并行搜索算法及分层思想进行路径查询,并且在PC机群的并行环境下对其进行实现。实验结果表明,该方法在运行时间和内存空间分配都具有明显的优势,具有良好的实用性。
关键词:大规模网络;城市小区;网络划分;最短路径;MPI
中图分类号:TP393;O157.6 文献标识码:A -)--04
SolvingtheShortestPathNetwork
,YUHai2jiao,FANGXin
(Science,ShaanxiNormalUniversity,Xi’an710062,China)
Abstract:Withthecurrentscaleofurbanexpansionandtransportnetworkmorecomplex,thecomputationoftheshortestpathproblemwillconsumemoretimeandspatialresources.Inordertohaveamoreefficientreal-time,simplifythecomplexnetworkbasedonthecitycommunity.Tomaintaintheoriginalcharacteristicsofnetwork,ineverydistricttofindtherepresentativenode,andothernodesastrans2parenthasnothingtodo.Thendowayfindingusedlayeredcalculationofthoughtandparallelsearchalgorithms.TheexperimentationhasbeenimplementedinparallelPCenvironment.Theexperimentalresultsshowthattherunningtimeandmemoryspaceallocationhaveaobviousadvantage,andhavegoodpracticability.
Keywords:large-scalenetworks;citycommunity;networkdivision;theshortestpath;MPI
0 引 言
最短路径问题是图论中的一个经典问题,也一直是交通运输问题中应用的一个研究热点。从20世纪
50年代末期至今,约有几千篇论文讨论最短路径计
直接查询;五是采用并行算法[1]。19世纪80年代以来,国外许多专家学者对最短路径并行算法的实现方法进行了探讨,建立了串行标号设定算法和标号修正算法的各种不同并行实现方法,并在此基础上对比各种算法的性能及效率。目前,针对各种不同的串行最短路径算法而提出的并行算法大体可以分为两类:一类是不依赖于计算机类型的算法,包括Tseng等[2]、
Paige和Kruskal[3]、Chandy和Misra[4]提出的算法;另
算。对最短路径算法的研究热点,一是针对实际网络特征优化数据和算法运行结构,在时间复杂度不变的情况下尽可能地提高算法的运行效率;二是对网络特征进行限制,如要求网络中的边具有整数权值等,以便采用基数堆等数据结构设计算法的运行结构;三是采用有损算法,像限制范围搜索、限定方向搜索及采用层次空间推理方法的限制几何层次递归搜索;四是采用拓扑层次编码路径视图,对最优路径进行部分实例化编码存储,将部分最优路径计算转变为子图间路径的
一类是针对特定计算机类型的算法,包括Habbal等以及Dey和Srimani提出的算法。在有关最短路径并行算法研究的文献中,大部分都是针对全源最短路径问题,大体分为以下3种:基于标号设定的并行算法、基于标号修正的并行算法、动态规划方法。
对于大规模网络来说,由于网络规模较大,采用上述五种方法并不能显著改善算法的效率。要从根本上解决算法的效率问题,就必须对大规模网络进行化简,由于化简后的网络规模可以大幅度减小,最短路径的计算速度就可以大幅度提高。文中在此思想上提出:在对大规模交通网络进行化简的基础上,在PC机群
收稿日期:2009-05-06;修回日期:2009-08-17基金项目:国家自然科学基金资助项目(40471102)
作者简介:卢 照(1983-),男,山西运城人,硕士研究生,研究方向为并行算法、体系结构;师 军,副教授,研究方向为智能信息处理、并行计算。
Dijkstra最短路径算法优化策略_计算机软件及应用_IT/计算机_专业资料。数模相关方法2009 年 10 月 第 35卷 第 10期 北京航空航天大学学报 Journal of Beijing ...
Dijkstra最短路径算法的实现及优化_IT/计算机_专业资料。基于Dijkstra的算法分析Dijkstra 最短路径算法的实现及优化 施培港 厦门信息港建设发展股份有限公司 厦门市...
快速Dijkstra最短路径优化算法的实现_理学_高等教育_教育专区。运筹学资料测绘信息网www.othermap.com网友测绘人提供 快速 Di jkstra 最短路径优化算法的实现司连...
Dijkstra最短路径算法的优化和改进_天文/地理_自然科学_专业资料。随着计算机和...算法特点传统Dijkstra算法基于广度优先的搜索策略,从指定节点出发,通过权值迭 代...
、一 最短路径与 Dijkstra 算法 顶点 ( Vertex) 和边 ( Edge ) 为基础 , 采用顶点分区和 记录绝对地址来优化 Dijkst ra 算法的方法 。设 G = ( V , E...
Dijkstra最短路径算法优化_IT/计算机_专业资料。硕士论文 路径优化...算法分析传统 85JC?@&A 算法基于广度优先的搜索策略, 从指定节点出 图 (1 ...
G 施行优化 Djt 算法 , ,对,isakr则 可得从 到其余各节点的最短路径 , ...算法分析 图1非权图 负值 传统 Djt 算法基于广度优先 的搜索策略, isakr 从...
基于Dijkstra的最短路径算法的优化及应用_信息与通信_工程科技_专业资料。本科...(四)特点传统Dijkstra算法基于广度优先的搜索策略,从指定节点出发,通过权值迭代...
Dijkstra最短路径算法优化_天文/地理_自然科学_专业资料。Dijkstra最短路径算法,非常适合相关专业的学生。第25卷第 3期 2006年 8月文章编号: 1006 - 4869( ...
热门文档