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

发布时间：2020-07-06 17:49

【摘要】：随着经济的发展,最优路径应用领域渐广,如路网导航、游戏行业、物流行业等。其中,路网导航备受广大学者的关注。随着路网数据的日益庞大,常规寻路算法的寻路性能稍显不足,不能快速地解决在庞大的路网中寻找任意两点间路径的问题。当前使用较广的寻路算法为分层算法。分层的思想是将详细路网中权重较高的节点和路径段抽象成一个新的交通路网,通过合理地切换详细路网和新路网使得寻路算法获得较好的时空性能。虽然分层算法优化了在庞大的地图数据中寻路的性能,但是其寻路的质量较A*算法相比有所下降。针对这个问题,本文借鉴了分层的思想、小世界网络模型和路由理论等理论,给出了一种在保证路径质量的前提下提升寻路效率的寻路策略：基于小世界模型的启发式寻路算法(Heuristic path finding algorithm based on small world model,简称 HPAS算法)。第一,路网分区。借鉴于分层算法中分层的思想和小世界网络模型,通过对交通路网进行聚类分析,将聚类结果中的各个簇划分成不同区。第二,设置边界路由节点和内部路由节点,并将相邻路由节点之间的最优路径预存到缓存中。借鉴路由理论中的外部网关协议中路由器的功能,将各区中符合条件的节点设置成边界路由节点或内部路由节点,相邻路由节点之间的路径可通过预处理阶段求解出来并进行缓存。第三,寻路阶段。利用A*算法在各个分区中的边界路由节点和内部路由节点之间寻找最优路径。实验由路径计算模块、缓存模块、地图数据库存取模块和用户请求处理模块等组成。通过对美国东西部路网数据的测试表明,不同粒度的聚类在不同程度上提高了HPAS算法的寻路效率。但是较大粒度的聚类也会在一定程度上加大了所求解的路径长度与最短路径长度之间的偏差。仿真实验结果表明在不同的一级划分中平均路径长度与最优路径长度的偏差仅为0.03%。通过HPAS算法与A*算法、双向A*算法和基于层次结构的A*算法在寻路效率和路径质量上的实验数据的对比,可以看出改进型A*算法在地图规模较大的情况下表现出来较好的性能。
【学位授予单位】：华中师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495

【相似文献】

相关期刊论文 前10条

1 蒋恺;;浅谈游戏中自动寻路算法的实现与应用[J];中国新通信;2018年02期

2 郭晓利;田俊辉;;游戏中自动寻路算法的改进研究[J];福建电脑;2017年03期

3 蒯锐;洪金敏;;自动寻路A*算法的应用及优化设计[J];上海应用技术学院学报(自然科学版);2014年02期

4 梁毅;周刚;;基于定位点和路径复用的大型多人在线游戏寻路算法[J];计算机应用;2010年12期

5 赵清松;;游戏开发中一种新的高效寻路算法——B~*寻路算法[J];程序员;2010年08期

6 邓先习;丁顺利;杜蕊;;基于二元堆的A*算法及其在游戏地图寻路中的应用[J];福建电脑;2008年08期

7 李建元;师军;曹菡;汪西莉;;一种分层寻路算法中的域值放弃策略[J];计算机应用;2007年02期

8 蔡方方;杨士颖;张小凤;刘东平;;双层A~*算法在游戏寻路方面的研究[J];微型电脑应用;2010年01期

9 芦雨;;寻路[J];中国研究生;2019年05期

10 高天寒;刘文成;;面向3D场景智能寻路技术综述[J];计算机工程与应用;2017年01期

相关会议论文 前10条

1 徐一;杨静;任志刚;杨迅幸;;基于学习的烟花算法[A];2018中国自动化大会(CAC2018)论文集[C];2018年

2 熊薇薇;吴怀宇;;一种改进的角点检测算法[A];中国计量协会冶金分会2009年年会论文集[C];2009年

3 陶丽;张自力;丁晓明;;一种适用于动态重构的联盟形成算法[A];2008年计算机应用技术交流会论文集[C];2008年

4 张兰平;;谈小学一年级算法多样化的优化[A];中华教育理论与实践科研论文成果选编（下）[C];2007年

5 杨红斌;;计划量算法的优化[A];第四届全国医院药剂科建设与管理学术研讨会论文集[C];2012年

6 许伦辉;傅惠;徐建闽;;基于分形维数的交通流预测模型及算法研究[A];2003年中国智能自动化会议论文集（下册）[C];2003年

7 林克旺;;基于分层网络实现高效的自稳定的选举算法[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（下册）[C];2006年

8 徐英钟;高震;李波;;基于禁忌搜索的蚁群算法求解旅行商问题[A];第四届中国智能计算大会论文集[C];2010年

9 叶衍;楼荣生;何永保;;自然联结的优化算法[A];第十二届全国数据库学术会议论文集[C];1994年

10 赵唯;;晶粒度评级的改进算法[A];中国图象图形科学技术新进展——第九届全国图象图形科技大会论文集[C];1998年

相关重要报纸文章 前10条

1 北京商报记者 郭秀娟 姚倩;九安医疗“调结构”寻路[N];北京商报;2019年

2 本报记者 路虹;内外承压，土耳其经济寻路难[N];国际商报;2019年

3 本报记者 崔吕萍;制造业寻路，问道葛红林[N];人民政协报;2019年

4 本报通讯员 张小寒;寻路“未来村”[N];威海日报;2018年

5 本报记者 谢雷鸣;寻路欧洲：打开另一端市场的方式[N];中国贸易报;2018年

6 本报记者 赵娜;连续创业者寻路知识付费：“内容+服务”机会几何？[N];21世纪经济报道;2018年

7 本报通讯员 闫宝明 v斌宏;一心寻路为穷亲[N];甘肃经济日报;2018年

8 中国出版传媒商报记者 江海;寻路县级店举办书展新径[N];中国出版传媒商报;2018年

9 记者 孙磊;寻路中国：从主题之变看发展之变[N];杭州日报;2018年

10 新华社记者 强勇;“创”中寻路 “新”中求机[N];黑龙江日报;2017年

相关博士学位论文 前10条

1 段琦;基于寻路行为的公共设施内导向标识服务能力的优化研究[D];天津大学;2015年

2 李江涛;车载导航路网的胞式化寻路与密度自适应[D];清华大学;2015年

3 王冰;人工蜂群算法的改进及相关应用的研究[D];北京理工大学;2015年

4 王艳娇;人工蜂群算法的研究与应用[D];哈尔滨工程大学;2013年

5 李美安;普适分布式互斥算法及应用[D];电子科技大学;2007年

6 王小根;粒子群优化算法的改进及其在图像中的应用研究[D];江南大学;2009年

7 白仲添;鸡胚神经管发育早期鳃运动神经的轴突寻路[D];兰州大学;2011年

8 刘婷;改进人工蜂群算法及其在多用户检测中的应用[D];天津大学;2013年

9 邱剑锋;人工蜂群算法的改进方法与收敛性理论的研究[D];安徽大学;2014年

10 肖建元;保几何结构算法在等离子体物理中的应用[D];中国科学技术大学;2017年

相关硕士学位论文 前10条

1 李德福;基于小世界模型的启发式寻路算法研究[D];华中师范大学;2015年

2 詹海波;人工智能寻路算法在电子游戏中的研究和应用[D];华中科技大学;2006年

3 程振兴;分布式应急救援系统寻路算法研究及仿真实现[D];北京化工大学;2016年

4 李晓阳;性别、寻路策略、任务难度与地图类型对室内寻路行为的影响[D];陕西师范大学;2016年

5 吴小玲;基于游客寻路行为的景区导向标识系统评价研究[D];南京师范大学;2015年

6 刘伟;三维高程地形中的多对象协同寻路[D];兰州大学;2006年

7 荆东星;人工神经网络在游戏寻路中的应用研究[D];长沙理工大学;2010年

8 余帅;即时战略游戏中基于势场的交互寻路方法[D];河北大学;2014年

9 甄怡;商业综合体建筑布局的易读性与“寻路”[D];同济大学;2007年

10 王庆稳;基于寻路理论的网络用户信息浏览行为研究[D];西南大学;2009年

本文编号：2743936