基于改进a星算法的城市交通寻径的研究

《基于改进a星算法的城市交通寻径的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10385分类号：研究生学号：1201414015密级：基于改进A星算法的城市交通寻径的研究ResearchonUrbanTrafficRoutingBasedonImprovedA*Algorithm作者姓名：潘长安指导教师：刘韶涛副教授实际单位导师：专业学位类别：工程硕士专业学位领域：计算机技术工程领域研究方向：算法理论所在学院：计算机科学与技术学院论文提交日期：二○一五年六月十一日学位论文独创性声明本人声明兹呈交的学位论文是本人在导师指导下完成的研究成果。论文写作中不包含其他人已经发表或撰写过的研究内容，如参考他

2、人或集体的科研成果，均在论文中以明确的方式说明。本人依法享有和承担由此论文所产生的权利和责任。论文作者签名：签名日期：学位论文版权使用授权声明本人同意授权华侨大学有权保留并向国家机关或机构送交学位论文的复印件和电子版，允许学位论文被查阅和借阅。本人授权华侨大学可以将本学位论文的全部内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。论文作者签名：指导教师签名：签名日期：签名日期：摘要摘要随着网络时代的来临和城市规模的日益扩大，人们在出行之前，往往会查询出行的路线。现在各种各样的出行路线查

3、询系统很多，但是优质的出行路线查询功能还有待提高，还需要进一步对出行路线的路径搜索算法进行优化。A星算法是目前最广泛使用的城市出行路径搜索算法之一。它是一种启发式搜索算法，其采用的估价函数是：F(n)=G(n)+H(n)，其中G(n)表示从起始顶点到当前顶点的距离的实际值，H(n)表示从当前顶点到目标顶点的距离的估算值。两者相加的结果为估价函数的估价值，选择估价值最小的顶点作为下一步要选择的顶点，如此循环运行估价函数从而生成最优路径。本文结合实际应用，对标准A算法进行了以下两方面改进：使用最小二叉堆技术优化0PEN表的查找速度

4、，提高寻径效率。对于A星算法的估价函数，笔者在如下方面进行了改进：1.选择合适的启发函数。2.增加启发函数在估价函数中的比重。3.使用向量内积值改进启发函数在估价函数的比重。4.过滤内积值进一步优化估价函数。从而减少寻径过程中遍历的顶点数，在保证寻径质量整体不变的前提下，较大幅度的提高了寻径效率。本文在VisualStudio2010开发平台上，使用C++语言分别实现了标准A星和改进A星的路径搜索算法，在此基础上统计它们的寻径长度、寻径时间、寻径过程中遍历的顶点数量，以此验证改进后的A星算法的可行性和有效性。经过本篇论文第四章

5、仿真实验验证证明：以最小二叉堆存储OPEN表中的数据，使A星算法的寻径效率提高了10%。以经过过滤的向量内积值作为启发函数在估价函数中的比重值，使算法在寻径质量保持不变的同时，A星算法的寻径效率至少提高了5.2倍,遍历的顶点数至少减少了57%，极大的提高了寻径效率。经过仿真实验证明，优化后的算法达到了预期的效果。关键词：A星算法二叉堆估价函数向量内积内积值过滤IIIAbstractAbstractWiththeadventoftheinternetageandtheincreasingenlargementofurbansc

6、ale,peopleusuallylocatetheirtravelroutesthroughnetworkterminaldevicesbeforesettingoutontheirjourney.Atpresent,whilethereareavarietyoftravelroutequerysystems,thefunctionsofthesequerysystemsstillneedtobeimproved,ofwhichthepathsearchalgorithmfortravelroutesneedsfurthero

7、ptimization.Astarsearchalgorithmisoneofthemost-widely-usedurbantravelroutesearchalgorithmscurrently.Itisaheuristicsearchalgorithmandtheevaluationfunctionitemployedis:F(n)=G(n)+H(n),whereG(n)representstheactualvalueofthedistancefromthestartingnodetothecurrentnode,andH

8、(n)representsanestimatedvalueofthedistancefromthepreviousnodetothetargetnode.ThefigurethatG(n)andH(n)adduptoistheValueofvaluationfu