鉴于最短路径问题的并行算法研究

《鉴于最短路径问题的并行算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文最短路径问题的并行算法研究姓名：平晓慧申请学位级别：硕士专业：计算机应用技术指导教师：谭国真20051201大连理上人学硕士学位论文摘要近年来，随着智能交通系统、通信系统等的不断发展，网络出现了新的特性一动态特性和大规模特性。对于具有新特性的网络中的最短路径问题的研究具有重要的理论意义和应用价值。这两类问题与传统的最短路径问题比起来，更加复杂，计算量也更大。当网络规模很大时，求解更加复杂，计算时问和所需的存储空问也大大的增加。并行计算，为快速地求解动态网络和大规模网络中的最短路径

2、提供了一个有效的途径。本文首先对时间依赖网络与大规模网络的特性进行了深入研究。接下来，对于时间依赖网络，设计了结点分解型的并行方法来划分网络数据，并根据分而治之的思想，利用SPMD模式设计了分布式环境下求解时间依赖网络最短路径的细粒度并行算法，该算法能够有效求解时间依赖网络中多结点到任意给定目的结点的最优路径；对于大规模网络，利用网络树模型对网络进行戈0分，采用动态分配策略来对数据进行分配，并采用Master／Slave模式设计了求解大规模网络最优路径的粗粒度并行算法，该算法大大提高了计算效率，并降低了

3、大规模网络优化对内存的需求。最后，建立了基于PWl的PC集群并行计算平台，并对这两个最短路径并行算法的性能进行了实验测试，给出了算法的运行时间、加速比和效率，并讨论了负载平衡问题和提高并行性能的具体方法。实验结果表明，本文所设计的并行算法在解决动态网络和大规模网络中的最短路径问题上是非常有效的。关键词：最短路径；时间依赖网络；大规模网络；并行算法人连王早工大学硕上学位论文ResearchoilParallelAlgorithmsofShortestPathProblemsAbstractWithther

4、apiddevelopmentofintelligenttransportationsystemandcommunicationsystems，problemsintimedependentnetworksandlargescalenetworksbecomemoreandmoreimportant．Thestudyofthiskindofproblemisofmoreimportanceandismuchmorevaluableinrealapplications．Theseproblemsareve

5、rycomplexandcomputationallyintense．IfthesizeofthenetworkiSverylarge，itwilIbemoredifficulttosolveit．Furthermore，thecomputingtimeandtherequiredmemorywillincreasedramatically．Parallelprocessingprovidesaneffectivemethodtosolvelarge·scaledynamicshortestpathpr

6、oblems．Inthispaper，shortestpathproblemsindynamicnetworksandlargescalenetworksarestudied，andparallelcomputingandhighperformanceclustercomputingwhichisfocusedonareintroduced．Thenfortime—dependentnetwork，thenode-decomposingmodelisdevisedtodividethenetworkda

7、ta．Andaparallelalgorithmforcomputingshortestpathsintime-dependentnetworkispresented．ThealgorithmCancomputetheshortestpathfromeachnodetoagivendestination．Forlargescalenetwork，weusenetwork—treemodeltodividethenetworkdataandthedataisallocateddynamicly，Thena

8、parallelalgorithmforcomputingshortestpathsinlargescalenetworkisdevisedusingMaster／Slavemodel．Thisalgorithmgreatlyimporvesthecomputingefficiencyandreducesthememoryrequirementforlargescalenetworkoptimization．Finally，aparalle