城市公交多路径改进搜索算法的研究及应用

《城市公交多路径改进搜索算法的研究及应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代号：10255学号：2081074城市公交多路径改进搜索算法的研究及应用ResearchandApplicationofanImprovedMulti-·pathSearchingAlgorithmonCityPublicTransportationNetwork学科专业：计算机系统结构作者：郑小飞指导教师：冯向阳答辩Et期：2011年1月13日东华大学计算机科学与技术学院CollegeofComputerScienceandTechnologyDonghuaUniversity东华大学硕士学位论文东华大学学位论文原创性声明途奇自苔台d

2、杜击旺IIIIIIIIIUHlllLLIHIHIIY2135481本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中己明确注明和引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。学位论文作者签名：黑f5hZ日期：z。}f年／月东华大学硕士学位论文版权使用授权书东华大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关

3、部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在——年解密后适用本版权书。本学位论文属于不保密囹。学位论文作者签名：踟小仁日期：乙Dff年f月}弓日指导教师签名：羁幻即日期：Ⅻ、1年1月I弭城市公交多路径改进搜索算法的研究及应用摘要城市公交网最优出行路径选择是城市公共交通中的一项重要研究内容，直接影响到城市居民的日常工作，学习，生活和出行效率。本文作者在分析当前国内外多路径搜索算法的基础上，针对大

4、型城市公交网，提出了一种建模方法，并基于该模型提出一种结合A术算法和背离路径思想的改进算法。本文作者的主要研究工作和创新点如下：1)相关搜索算法的分析与研究。结合A木算法与背离路径思想，提出和实现了一种根据预前知识反馈确定潜在一条和多条最佳路径的搜索算法。2)针对大型城市公交网，提出一种建模的方法，包括该模型的数据存储结构。3)提出一种合理构造预前知识反馈函数的方法，使算法在不损失最优解的情况下获得较高的搜索效率。4)基于本文的研究结果，设计和实现了针对大型城市公交网多路径搜索的改进算法，并通过实验对本文提出的改进算法与A木算法的搜索效率进行

5、了比较。把背离路径思想引入A木搜索算法，并通过公交站点地理座标位置信息构建知识评估函数的做法，类似研究鲜有报道。实验证明，本文作者提出的多路径搜索改进算法在执行效率上均比Dijkstra算法和A木算法有显著提高。关键词：公交网，最短路径，A木算法，背离路径，多路径搜索ResearchandApplicationofOptimumMulti’pathSearchingAlgorithmonCityPublicTransportationNetworkABSTRACTOptimalrouteselectiononcitypublictranspo

6、rtationnetworkforgoingoutisoneofimportantresearchcontentinCPT(CityPublicTransportation)，andaffectsdirectlyefficienciesofdailywork，study,livingandgoingoutofcityresidents．Basedonanalysisavariantofmulti．pathsearchalgorithmsindoorandoutdoorofChinaatpresent，amethodofmodelinghasb

7、eenproposedforlargescaleCPTnetwork，therefore，animprovedalgorithminwhichA水algorithmandideaofthedeviationpathhavebeencombinedwitheachotherhasbeenpresentedtoo．Theprimaryresearchworkandinnovationsmadebyauthorofthispaperaresummarizedasthefollowings：1)Analysisandresearchofrelevan

8、tsearchingalgorithms．Introductionandimplementationofanimprovedalgorithmwhichcombin