本科生毕业设计（论文）基于a算法的路径寻找

《本科生毕业设计（论文）基于a算法的路径寻找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学号：上海建桥学院本科生毕业设计（论文）基于A*算法的路径寻找学院：商学院专业：国际经济与贸易班级：B16-2姓名：阮晨阳指导老师：史小宏完成日期：2016年11月基于A*算法的路径寻找基于A*算法的路径寻找摘要启发式搜索算法的有很多种类，其中一种就是A*搜索算法。在状态空间对每一个可能的位置进行判断，并且根据一定的判断标准得出最优化的位置，然后以这个位置作为开始继续搜索到终点目标位置，以上就是启发式搜素的基本的定义。对于每次都要选取最小估价的节点，应该用到最小优先级队列（也叫最小二叉堆）。可以直接使用。当然不要忘了重载自定义节点的比较操

2、作符。A*算法的特点：A*算法在理论上是时间最优的，但是也有缺点：在理论上最差的情况下，它的空间增长将有可能是指数级别的。这一搜索算法的的好处就是可以将很多的不需要的冗余的路径略去，从而使得时间和空间的效率大大提升。它的主要的组成部分为OpenList,CloseList和估价函数。他可以应用在路由的路径查找，地图上路径查找。关键词：启发式算法，搜索路径，A*算法，估价函数-IV-基于A*算法的路径寻找BasedonthepathoftheA*algorithmtofindAbstractHeuristicsearchalgorithm,

3、therearemanytypes,oneofwhichisA*searchalgorithm.Thejudgeinthestatespaceofeverypossiblelocation,andobtainedoptimallocationaccordingtocertaincriteria,andthentocontinuesearchingtotheendofthislocationasthetargetlocation,theaboveisthebasicdefinitionofheuristicsearch.Foreachnod

4、emustselectaminimumvaluation,shouldbeusedinaminimumpriorityqueue(alsoknownastheleastbinaryheap).Canbeuseddirectly.Ofcoursedonotforgettheoverloadedself-definednodeoperationcharacter.A*algorithmcharacteristics:A*algorithmistheoreticallyoptimaltime,butitalsohasdisadvantages:

5、intheorytheworstcase,thegrowthofitsspacewillbepossibletotheindexlevel.Thebenefitsofthesearchalgorithmcanbealotofunwantedredundantpathomitted,makingtimeandspaceefficiencyisgreatlyenhanced.ItsmaincomponentsOpenList,CloseListandvaluationfunctions.Hecanbeappliedtotheroutingpa

6、thsearchpathtolocateonthemap.Keywords:Heuristicalgorithm,thesearchpath,theA*algorithm,thevaluationfunction-IV-基于A*算法的路径寻找目录引言11研究背景和意义21.1背景及意义21.2本文研究内容32路径寻址和开发工具42.1路径寻址的方法介绍42.1.1模拟42.1.2最短路径问题42.1.3Dijkstra算法42.2开发工具——Eclipse53基于搜索算法的机器人路径寻址73.1广度优先算法（BFS）73.2深度优先搜寻（

7、DFS）73.3A*算法74A*算法仿真系统设计114.1路径寻址系统概述114.2对用户界面进行模块设计114.2.1主窗口界面114.2.2绘画过程代码114.2.3工具栏代码124.2.4按钮代码134.2.5状态栏代码144.3对算法实现进行设计144.3.1路径组成函数和搜索逻辑设计144.3.2节点判断函数及属性函数的设计165仿真实验结果的比较及界面UI185.1SWING技术介绍185.2仿真实验及结果比较185.2.1g(n)的改变对结果的变化185.2.2基于h(n)的变化对结果的影响246结束语306.1总结30-I

8、V-基于A*算法的路径寻找6.2实验存在的问题和改善30参考文献31发表学术论文情况32致谢33-IV-基于A*算法的路径寻找引言现实世界中有许许多多的不同的网络构成，交通网络，通信网络，计算