网络的k最短路分析及其在交通中的应用

《网络的k最短路分析及其在交通中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：U491密级：公开UDC：单位代码：10424学位论文网络的K最短路分析及其在交通中的应用张建勇申请学位级别：硕士学位专业名称：交通运输规划与管理指导教师姓名：刘法胜职称：教授山东科技大学二零零六年五月论文题目：网络的K最短路分析与应用作者姓名：张建勇入学时间：2003年9月专业名称：交通运输规划与管理研究方向：交通信息一体化指导教师：刘法胜职称：教授论文提交日期：2006年5月论文答辩日期：2006年6月授予学位日期：ANALYSISANDAPPLICATIONOFKSHORTESTPATHSINTHEN

2、ETWORKADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyZhangJianyongSupervisor:ProfessorLiuFashengCollegeofInformationandElectricalEngineeringMay2006声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献

3、和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：2006年5月AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknow

4、ledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date:20065摘要今天的社会已经成为网络社会，在今天的自然科学中，网络研究也成为重要课题。交通网络分析的重点是路径分析，而路径分析的核心为最优路径算法。最短路径算法是最优路径算法中的一个经典问题,它在实际生产生活中有广泛应用。在许多情况下，不仅仅要考虑最短路也要考虑次短路、次次短路，即K最短路问题。K最短路算法涉及很多领域，如在交通

5、工程、通信、人工智能等方面有重要的实际意义。本文在系统总结和分析经典最短路算法、动态规划方法的基础上，对联网收费交通网络中的多路径问题进行了深入细致的研究，得出了适用于交通网络多路径分析及模拟的高效、快速的K最短路算法。这一算法按长度递增顺序给出K最短路路径排列。算法的复杂度为Om(nlgnmlg)k。在给定的网络中，通过添加标识站对两顶点之间K最短路径识别，本文既给出标识站的数目、位置的确定方法，又给出了整个网络中添加标识站的总方案数的计算方法。通过路径伸展系数，采用启发式搜索算法标定高速公路网的路径伸展系数

6、的大小，从而确定高速公路网有效多路径搜索范围，利用基于动态规划法的K最短路算法搜索给定路网上任两站点之间的有效多路径。最后对山东省联网收费高速公路网络的K最短路问题进行具体分析。关键词：动态规划法；K最短路径；标识站；路径伸展系数；有效多路径1山东科技大学硕士学位论文AbstractABSTRACTResearchonthenetworkisbecomingtheimportanttopicintodaynaturalsciences,whenmodernsociety'salreadybecomethenetwo

7、rksociety.Thekeypointofthetransportationnetworkanalysisisthewayanalysis,andthealgorithmofthebestrouteisthecoreofthewayanalysis.Theshortestpathalgorithmisaclassicalproblemofthebestroutealgorithm,whichhaswidespreadapplicationinmanyaspects.K-shortestpathalgorithm

8、involvesmanydomains,whichissignificantfortrafficengineering,communicationsystem,artificialintelligenceandsoon.Basedonthesystematicsummarizationandanalysisoftheclassicalshortestalgo