基于小世界模型的启发式寻路算法研究

《基于小世界模型的启发式寻路算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、＊分类号密级ＵＤＣ编号半中仰捉义考硕±学位论文基子小难界巧型巧名义乂导洛义法巧免学位申请人姓名；車德珠；全巧？申请学位学生类别！巧壬申请学位学科专业；计义机条娩结柏指导教师姓名；刘巧乂援ｕＳｓ耻学位论文＇ｖＭｇ／ＭＡＳＴＥＲＳＴＨＥＳＩＳ＾＾硕±学位论文基于小世界模型的后发式寻路算法研究论文作者：李德福指辩狮：刘明教授学科专业：计算机系瓣吉构研究方向：计算机网络华中师范大学计算机学院２０１５年５月硕

2、壬学位论文ＭＡ押战．ＳＴＨＥＳＳ？ＩＨｅｕｒｉｓｔｉｃａｔｈｆｉｎｄｉｎｐｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｓｍａｌｌｗｏｒｌｄｍｏｄｅｌＡＴｈｅｓｉｓＳｕｂｍｉｔｔｅｄｉｎＰａｒｔｉａｌＦｕｌｆｉｌｌｍｅｎｔｏｆｔｈｅＲｅｑｕｉｒｅｍｅｎｔＦｏｒｔｈｅＭ．ＳｉＣｕｔｅｒＳｃｉｅｎｃｅＤｅｇｒｅｅｎｏｍｐＢｙＬｉＤｅｆｕＰｏｓｔｒａｄｕａｔｅＰｒｏｒａｍｇｇＣｅｎｔｒａｌＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ

3、Ｓｕｐｅｒｖｉｓｏｒ：ＬｉｕＭｉｎｇＡｃａｄｅｍｉｃＴｉｔｌｅ：Ｐｒｏ色ｓｓｏｒＳｉｎａｔｕｒｅ／（／（ｇｌｒｏｖｅｄ＾￡ｐ５．２０１５硕壬学位论文ＭＡ－？ＳＴＥＲＳＴＨＥＳＩＳ华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研巧成果。除文中己经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文

4、中Ｗ明确方式标明。本声明的法律结果由本人承担。？？：Ｈ期作者签名又俸踩：＞沒６月学位论文版权使用授权书良学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定；，Ｐ研究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并向国家有关部口或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅；学校可Ｗ公布学位论文的全部或部分内容，可ｉｌ、ｌ允许采用影印缩印或其它复制手段保存、汇编学位论文。（保密的学位论文在解密后遵守此规定）。保密论文注释：本学

5、位论文属于保密，在年解密后适用本授权书。非保密论文注释：本学论文不属于保密范围，适用本授权书作者签宇师签名：＼曰期：月＞日９化年月Ｗ（７＆＂＂本人己经认真阅複ＣＡＬＩＳ商校学位论文全文数据库发布章程，同意将本人的＂＂＂＂学位论文提交ＣＡＬＩＳ高校学位论文全文数据库中全文发布，并可按章程中的规定享受相关权益一。同意论＾提交后滞后；口半年；口年；口二年发布。作者签名：导师株曰期：月＾日曰期：年＾（）＾７／硕去学位论文＇？ＭＡＳＴＥＲＳＴＨＥＳＩＳ摘要随着经

6、济的发展，最优路径应用领域渐广，如路网导航、游戏行业、物流行业等。其中，路网导航备受广大学者的关注。随着路网数据的日益鹿大，常规寻路算法的寻路性能稍显不足，不能快速地解决在庞大的路网中寻找任意两点间路径的问题。当前使用较广的寻路算法为分层算法。分层的思想是将详细路网中权重较高的节点和路径段抽象成一个新的交通路网，通过合理地切换详细路网和新路网使得寻路算法获得较好的时空性能。虽然分层算法优化了在庞大的地图数据中寻路的性能，＊但是其寻路的质量较Ａ算法相比有所下降。针对这个问题，、小

7、世界网络模型和路由理论等理论本文借鉴了分层的思想，一种在保证路径质量的前提下提升寻路效率的寻路策略给出了：基于小世界模型的后发式寻路算法（Ｈｅｕｒｉｓｔｉｃａｔｈｆｉｎｄｉｎａｌｏｒｉｔｈｍｂａｓｅｄｏｎｓｍａｌｌｗｏｒｌｄｍｏｄｅｌ，简称ｐｇｇＨＰＡＳ算法一）。第。，，路网分区借鉴于分层算法中分层的思想和小世界网络模型通过对交通路网进行聚类分析，将聚类结果中的各个簇划分成不同区。第二，设置边界路由节点和内部路由节点，并将相邻路由节点之间的最优路径预存到缓存中。借鉴

8、路由理论中的外部网关协议中路由器的功能，将各区中符合条件的节点设置成边界路由节点或内部路由节点，相邻路由节点之间的路姪可通过预处理阶段求解出Ｈ＊来并进行缓存。第，寻路阶段。利用Ａ算法在各个分区中的选界路由节点和内部路由节点之间寻找最优路径。实验由路径计算模块、缓存模块、地图数据库存取模块和用户请求处理模块等组成。通过对美国东西部路网数据的测试表明，不同粒度的聚类在不同程度上提高了一ＨＰＡＳ算法的寻路效