路网寻径中的a星算法改进

《路网寻径中的a星算法改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级ＵＤＣ缩县岸中钟策义考硕±学位论文蘇巧尋径申的Ａ晏證法欢进学位申请人姓名：张强申请学位学生类别＇：全巧劍硕壬申请学位学科专业：计义机染燒结拘指导教师姓名：舊非到教援射学位论文ＭＡＳＴＥＲＳＴＨＥＳＩＳ硕±学位论文路Ｐ瞬Ｓ中的Ａ星ｌ＾法改进论文做张强指导教师：Ｓ非副類Ｓ学科专化：计研究方向：路由脱华中！制学院２０１６年５月位论文ｍａｓｔｅｒｓＴＨＥＳＩＳＩｍｐｒｏｖｉｎｇＡＳｔａｒＳｅａｒｃｈ

2、ｉｎＲｏａｄＮｅｔｗｏｒｋｓＡＴｈｅｓｉｓＳｕｂｍｉｔｔｅｄｉｎＰａｒｔｉａｌＦｕｌｆｉｌｌｍｅｎｔｏｆｔｈｅＲｅｕｉｒｅｍｅｎｔｑＦｏｒｔｈｅＭ．ＳＤｅｇｒｅｅｉｎＣｏｍｐｕｔｅｒＳｙｓｔｅｍＡｒｃｈｉｔｅｃｔｕｒｅＢｙＺｈａｎｉａｎｇＱｇＰｏｓｔｒａｄｕａｔｅＰｒｏｒａｍｇｇＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＣｅｎｔｒａｌＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙＳｕｐｅｒｖｉｓｏｒ：ＦｅｉＧｅＡｃａｄｅｍｉｃＴｉｔ

3、ｌｅ：ＡｓｓｏｃｉａｔｅＰｒｏｆｅｓｓｏｒＳｉｎａｔｕｒｅ知么ｇＡｒｏｖｅｄｐｐＭａｙ．２０１６巧壬学位论文？ＭＡＳＴＥＲＳＴＨＥＳＩＳ华中？＊范大学学位论文原创柱声明和使用授城明居食Ｉ牲声巧本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或。集体己经发表或撰写过的研巧成果对本文的研巧做出贡献的个人和集体，均己在文中Ｗ明确方式标明。本声明的法律结果由本人承担。作者签名

4、；日期年＜：（月日学侄冷文化扶使用援权术学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定：，即研巧生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并向国家有关部口或机构送交论文的复印件和电子版，允许学位论文被査阅和ｉ借阅，可ｔ＾ｌ；学校可＾公布学位论文的全部或部分内容允许采用影印、缩印或其它复制手段保存、汇编学位论文。（保密的学位论文在解密后遵守此规定）保密论文注释：．在本学位论文属于保密年解密后适用本授权书。：本学位论文不属于保密范围非保密论文

5、注释，适用本授权书。作者签名：ｉ來爲导师签名：曰期：如／知／月曰曰期八年／月曰＂＂本人己经认真阅读ＣＡＬＩＳ商校学位论文全文数据库发布章程，同意将本人的＂＂＂＂学位论文提交ＣＡＬＩＳ高校学位论文全文数据库中全文发布，并可按章程中的一规定享受相关权益。同意论文提巧后滞后：□半年；□年；□二年发布。作者签名：／＾＼｜＾导师签曰额Ｉ曰期茄年曰巧壬学位论文？ＭＡＳＴＥＲＳＴＨＥＳＩＳ巧要随着经济的发展，城市的地理信息数据呈爆炸式増长且城市路网的结构也变得日益复

6、杂。能否从复杂的城市路网中几乎实时地找出从出发地到目的地的最短路线一越发受到老百姓的关注。Ａ星算法作为种经典的启发式寻路算法，广泛用于城市交通寻路。随着时代的前进，多种改进Ａ星算法已被人们提出。其中Ｗ二叉堆存储结构代替传统ＯＰＥＮ表的线性存储结构的改进令人瞩目，虽效率提升明显但逐渐＇难Ｗ满足用户需求。本文在此背景下对上述算法展开了研巧。本文首先对图和图捜索算法相关知识进行了叙述一－，着重介绍本文研巧对象Ａ星算法，对其进行分析并指出其瓶颈。接着简单介绍了已被人提出的Ａ星算法改进方案，本文

7、提出了。基于对上述改进方案的研巧并结合较为成熟多核多线程技术两种算法改进方案。第一种方案是节点并行扩展及ＯＰＥＮ表分治并行査找最小代价值节点。该方案让节点扩展时可Ｗ在邻接节点代价值计算、节点是否在ＯＰＥＮ表和ＣＬＯＳＥ表中等耗时读操作上由多个子线程并行进行，而ＯＰＥＮ表添加节点或更改节点代价值、ＣＬＯ化表添加节点等写操作由主线程串行进行。同时，为了减少査找ＯＰＥＮ表中＂＂最小代价值节点的时间，基于分治思想，提出将ＯＰＥＮ表分成多个节点更少的表，由多线程并行实现二叉堆存储，每个线程找出单

8、个表的最小代价值节点后交由主线程得出全局的最小代价值节点。另一种方案是双向并行运行寻径。该方案提出开后两个线程同时分别从起始节ＰＥＮ表一点和目标节点分别朝对方寻径，两个线程各独自拥有Ｏ但共用个ＣＬＯＳＥ一表且对此表进行同步处理，当其中个线程从其独自拥有的ＯＰＥＮ表中找到的最ＬＯＳＥ一小值节点放入ＣＬＯＳＥ表中时，若发现该节点己存在于Ｃ表中并被另个线