欢迎来到天天文库
浏览记录
ID:34874445
大小:19.71 MB
页数:64页
时间:2019-03-13
《基于小世界模型的启发式寻路算法研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、*分类号密级UDC编号半中仰捉义考硕±学位论文基子小难界巧型巧名义乂导洛义法巧免学位申请人姓名;車德珠;全巧?申请学位学生类别!巧壬申请学位学科专业;计义机条娩结柏指导教师姓名;刘巧乂援uSs耻学位论文'vMg/MASTERSTHESIS^^硕±学位论文基于小世界模型的后发式寻路算法研究论文作者:李德福指辩狮:刘明教授学科专业:计算机系瓣吉构研究方向:计算机网络华中师范大学计算机学院2015年5月硕
2、壬学位论文MA押战.STHESS?IHeuristicathfindinpgalgorithmbasedonsmallworldmodelAThesisSubmittedinPartialFulfillmentoftheRequirementFortheM.SiCuterScienceDegreenompByLiDefuPostraduateProramggCentralChinaNormalUniversity
3、Supervisor:LiuMingAcademicTitle:Pro色ssorSinature/(/(glroved^£p5.2015硕壬学位论文MA-?STERSTHESIS华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明:所呈交的学位论文,是本人在导师指导下,独立进行研究工作所取得的研巧成果。除文中己经标明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文
4、中W明确方式标明。本声明的法律结果由本人承担。??:H期作者签名又俸踩:>沒6月学位论文版权使用授权书良学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定;,P研究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并向国家有关部口或机构送交论文的复印件和电子版,允许学位论文被查阅和借阅;学校可W公布学位论文的全部或部分内容,可il、l允许采用影印缩印或其它复制手段保存、汇编学位论文。(保密的学位论文在解密后遵守此规定)。保密论文注释:本学
5、位论文属于保密,在年解密后适用本授权书。非保密论文注释:本学论文不属于保密范围,适用本授权书作者签宇师签名:\曰期:月>日9化年月W(7&""本人己经认真阅複CALIS商校学位论文全文数据库发布章程,同意将本人的""""学位论文提交CALIS高校学位论文全文数据库中全文发布,并可按章程中的规定享受相关权益一。同意论^提交后滞后;口半年;口年;口二年发布。作者签名:导师株曰期:月^日曰期:年^()^7/硕去学位论文'?MASTERSTHESIS摘要随着经
6、济的发展,最优路径应用领域渐广,如路网导航、游戏行业、物流行业等。其中,路网导航备受广大学者的关注。随着路网数据的日益鹿大,常规寻路算法的寻路性能稍显不足,不能快速地解决在庞大的路网中寻找任意两点间路径的问题。当前使用较广的寻路算法为分层算法。分层的思想是将详细路网中权重较高的节点和路径段抽象成一个新的交通路网,通过合理地切换详细路网和新路网使得寻路算法获得较好的时空性能。虽然分层算法优化了在庞大的地图数据中寻路的性能,*但是其寻路的质量较A算法相比有所下降。针对这个问题,、小
7、世界网络模型和路由理论等理论本文借鉴了分层的思想,一种在保证路径质量的前提下提升寻路效率的寻路策略给出了:基于小世界模型的后发式寻路算法(Heuristicathfindinalorithmbasedonsmallworldmodel,简称pggHPAS算法一)。第。,,路网分区借鉴于分层算法中分层的思想和小世界网络模型通过对交通路网进行聚类分析,将聚类结果中的各个簇划分成不同区。第二,设置边界路由节点和内部路由节点,并将相邻路由节点之间的最优路径预存到缓存中。借鉴
8、路由理论中的外部网关协议中路由器的功能,将各区中符合条件的节点设置成边界路由节点或内部路由节点,相邻路由节点之间的路姪可通过预处理阶段求解出H*来并进行缓存。第,寻路阶段。利用A算法在各个分区中的选界路由节点和内部路由节点之间寻找最优路径。实验由路径计算模块、缓存模块、地图数据库存取模块和用户请求处理模块等组成。通过对美国东西部路网数据的测试表明,不同粒度的聚类在不同程度上提高了一HPAS算法的寻路效
此文档下载收益归作者所有