路径寻找算法的研究毕业设计论文.docx
《路径寻找算法的研究毕业设计论文.docx》由会员分享，可在线阅读，更多相关《路径寻找算法的研究毕业设计论文.docx（95页珍藏版）》请在冰点文库上搜索。
路径寻找算法的研究毕业设计论文
毕业设计（论文）
题目：
A*路径寻找算法的研究
A*AlgorithmFindingPath
毕业设计（论文）诚信声明
本人郑重声明：
所呈交的毕业设计（论文）是我个人在导师指导下进行的研究工作及取得的研究成果。
就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华东交通大学或其他教育机构的学位或证书所使用过的材料。
如在文中涉及抄袭或剽窃行为，本人愿承担由此而造成的一切后果及责任。
本人签名：
导师签名：
2010年6月9日
华东交通大学毕业设计（论文）任务书
姓名
樊斐佳
学号
20062110040126
毕业届别
2010
专业
电子商务
毕业设计（论文）题目
A*路径寻找算法的研究
指导教师
蔡体键
学历
研究生
职称
副教授
1、要求（作为评分标准）：
（1）基本要求：
1.深入了解A*算法的内部操作过程；
2.了解A*算法如何在起点和终点间建立路径；
3.设计以砖块环境为背景的小游戏程序来运用A*算法；
4.掌握A*算法在图论中次短路径中寻找的灵活运用；
5.比较A*算法和其它几种启发式搜索算法的优劣；
6.学习使用一些常用工具软件，包括文字处理工具、压缩工具、图像制作工具、动画制作工具、网页制作工具、多媒体处理工具等。
（2）创新性要求：
1.研究A*算法的应用，广泛阅读相关论文，分析A*算法的改进算法；
2.设计合理的估价函数，提高A*算法的搜索效率，对A*算法进行新的改进。
2、进度安排：
●第—周：
审题，调研，了解课题任务。
查阅相关资料，学习人工智能相关技术；
●第二周：
查阅外文资料，完成相关资料的翻译；
●第三周：
完成开题报告；
●第四～六周：
学习各种路径搜索技术，重点研究A*算法；
●第七周：
对小游戏模拟程序进行总体设计，对功能模块进行划分，完成数据结构的设计；
●第八～九周：
完成小游戏程序的各功能模块的设计，实现A*算法设计思想；
●第十周：
开始写毕业论文；
●第十一～十二周：
边写论文，边调试、充实、完善游戏软件；
●第十三周：
按照毕业设计撰写规范的要求修改毕业论文，完成毕业论文；
●第十四周：
提交毕业论文，进行毕业答辩。
指导教师签字：
2009年11月22日
系、部意见：
题目及工作量符合本科培养要求
是否是新题□是□否
系、部主任签字：
年月日
题目发出日期
2009年12月1日
设计（论文）起止时间
2010年3月8日—2010年6月12日
学院意见：
同意发布题目□是□否
毕业设计领导小组组长签章：
华东交通大学毕业设计（论文）开题报告书
课题名称
A*路径寻找算法的研究
课题来源
导师指定
课题类型
设计
导师
蔡体键
学生姓名
樊斐佳
学号
20062110040126
专业
电子商务
一、开题报告内容：
1、文献综述
（1）.搜索算法的介绍和分类
搜索算法称为“通用算法”，在算法常见的几大块，比如图论、数论、动态规划、计算几何、字符串等领域中都被广泛应用，同时在人工智能中占有重要的地们。
但是由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。
搜索可分为盲目搜索和启发式搜索，盲目的算法种类比较多，有纯随机搜索、广度优先搜索、深度优先搜索，迭代加深搜索、迭代加宽搜索，柱型搜索。
启发式搜索包含，贪心搜索，A*搜索和ID*搜索。
（2）.搜索算法中的剪枝
剪枝满正确性、准确性和高效性三个原则，优秀的剪枝往往可以很大程度上地加快一个算法的搜索速度，一般包含极端法、调整法和数学法三种；极端法广泛地应用各种搜索算法的剪枝中，它的基本思想是能过对当前结点进行理想式，通过否定这样的“理想情况”来避免对当前结点的扩展；调整法的基本思路是通过对子树的比较前年重复子树和明显不是最有“前途”的子树；数学方法主要是针对一些具体的问题利用专门知识进行剪枝，例如，在图论中借助连通分量，数论中借助模方和的分析等。
（3）路径寻找问题
图论中的Dijkstra算法也可以进行最短路的寻找，但是当点比较多而边比较少的稀疏的图中，并不是最好的选择，而其他的方法，比如双向广搜索就在时间和空间上都优于它，如果在广搜索加上合理的启发式，即A*搜索，会更快！
通过我写的两个小程序的比较和验证发现，在无障碍物的地图中搜索路径，用哈曼顿距离作为启发式，可以大减少算法运行过程中点扩展的总数，而且能找到最短的路径，而利用Dijkstra的每次找离起点最近的点扩展的思想，总扩展的点大大多于前者，从而算法运行速度也慢了很多，而在有障碍物的地图中，前者虽然很快求解路径，但并不一定是最短路径，而后者仍可保证最短路径，假如我们定义g（n）为当前点到起始点的距离，h（n）为到终点的最短哈曼顿距离，而用f（n）=g（n）+h（n）作为我们算法的估价函数，我们会发现算法运行速度会高于后者而低于前者，但是我们可以得到一条最短路径，这便是A*算法的特长所在，即保证算法的准确性又保证高效率!
（4）在阅读一些信息学竞赛国家队集训论文后，总结出可以快速度提高搜索效率的优化方法有：
a.数据的有序化,比如用搜索解经典的装箱问题——n个不同体积的物体放个一个体积为V的箱子，使得箱子刚好放满，如果先将不同物体按体积大小排序后再进行搜索，会提前找到最优解
b.选择搜索对象，比如公交汽车的调度表安排问题，如果选择汽车作为对象则每辆车对应不同的时间，而如果选择路径作为对象则对应的是不同的汽车，可以预见这种方法搜索过程中汽车会越来越少，该搜索树越深，枝条便会越少。
c.搜索的策略选择
1、在对同一个问题搜索求解时，往往会遇到不同策略的选取，而有时不论是效率还是准确性上都会相差甚远，所以很有必要在一个搜索求解前充分考虑不同策略选取的利与弊
（5）A*算法的介绍
启发式搜索其实有很多的算法，比如：
局部择优搜索法、最好优先搜索法等等。
当然A*也是。
这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。
象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。
这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。
最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。
这样可以有效的防止“最佳节点”的丢失。
其实A*算法也是一种最好优先的算法。
只不过要加上一些约束条件罢了。
由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！
我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。
A*算法是一个可采纳的最好优先算法。
A*算法的估价函数可表示为：
f'（n）=g'（n）+h'（n）
这里，f'（n）是估价函数，g'（n）是起点到终点的最短路径值，h'（n）是n到目标的最断路经的启发值。
由于这个f'（n）其实是无法预先知道的，所以我们用前面的估价函数f（n）做近似。
g（n）代替g'（n），但g（n）>=g'（n）才可（大多数情况下都是满足的，可以不用考虑），h（n）代替h'（n），但h（n）<=h'（n）才可。
可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。
我们说应用这种估价函数的最好优先算法就是A*算法
2、参考文献
a.《IntroductionToAlgorithms》第二版ThomasH.cormen,高等教育出版社
b.《算法艺术》刘汝佳清华大学出版社
c.《AlgorithmsinC》RobertSedgewick机械工业出版社
d.《搜索方法中的剪树优化》齐鑫奥林匹克信息竞赛国家队集训论文
e.《参数搜索的应用》汪汀奥林匹克信息竞赛国家队集训论文
f.《算法设计》张德福网络电子版
g.《计算机算法设计与分析》第三版王晓东电子工业出版社
二、方法及预期目的：
1、拟采用的研究方法（手段）
①查找文献
②比较求解同一问题的不同方法实现,
③分析A*在路径寻找时的利和弊及A*在其他方面的应用
④MFC实现A*寻路过程演示.
2、本课题要研究或解决的问题及预期目的
（1）研究的内容
本文研究搜索算法的实现方法和技巧，对一些常用和高效剪枝优化方法深入了解，并结合到A*算法在路径寻找中，通过对比，剖析A*算法的优良性质和不足的地方。
通过对问题求解的要求调整估价函数f（n）=g（n）+h（n）从而得到一个最适合的A*算法。
（2）预期目的
本设计的首要目的是运用已经学习到的搜索算法知识，自主实现两个寻找最短路径和经典8数码问题的A*算法，使得现有知识得到更好的巩固。
同时在实现中学习到更多新的知识，能更深入掌握搜索算法中剪枝，对象和搜索策略选择的运用，了解软件开发的全过程，为以后的学习与工作打下坚实的基础。
3、进度表
时间
主要任务
2010年1月—2010年1月
查阅资料与构思方案
2010年2月—2010年3月
总结A*搜索中的不同做估价函数及界面的构思
2010年3月—2010年4月
代码编写与调试
2010年4月—2010年5月
数据记录与答辩
三、指导老师意见
同意开题
指导教师签名：
日期：
2010年3月22日
华东交通大学毕业设计（论文）评阅书
（1）
姓名
樊斐佳
学号
20062110040126
专业
电子商务
毕业设计（论文）题目
A*路径寻找算法的研究
指导教师评语：
论文评分
评分项目
分值
评价参考标准
评分
总分
优
（≥）
良
（≥）
中
（≥）
及格
（≥）
不及格（＜）
完成任务书要求
30
27
24
21
18
17
学习与工作态度
20
18
16
14
12
11
研究水平与设计能力
20
18
16
14
12
11
开题报告、中英文翻译
10
9
8
7
6
6
论文撰写质量
10
9
8
7
6
5
学术水平与创新
10
9
8
7
6
5
是否同意设计（论文）参加答辩
□同意□不同意
指导教师签名：
2010年6月15日
评阅人评语：
论文评分
评分项目
分值
评价参考标准
评分
总分
优
（≥）
良
（≥）
中
（≥）
及格
（≥）
不及格（＜）
完成任务书要求
30
27
24
21
18
17
选题的价值与意义
10
9
8
7
6
6
研究水平与设计能力
20
18
16
14
12
11
开题报告、中英文翻译
10
9
8
7
6
6
论文撰写质量
20
18
16
14
12
11
学术水平与创新
10
9
8
7
6
5
评阅教师签名：
2010年6月15日
华东交通大学毕业设计（论文）评阅书
（2）
姓名
樊斐佳
学号
20062110040126
专业
电子商务
毕业设计（论文）题目
A*路径寻找算法的研究
答辩小组评语：
具体要求
优
良
中
一般
差
符合要求
答辩准备充分，论文题目与内容相符
语言精练能突出重点，思路清晰能准确表达。
论点正确，论文内容有一定难度
方法合理，论文内容工作量饱满。
结构严谨，论文有一定应用价值。
对前人工作有改进或有独特见解。
正面回答问题，不回避问题，不浪费时间，不狡辩。
回答问题有理论依据，基本概念清楚。
主要问题回答准确，深入。
等级
组长签字：
2010年6月15日
答辩委员会意见：
同意以上评定
等级
答辩委员会主任签字：
2010年6月15日（学院公章）
注：
答辩小组根据评阅人的评阅签署意见、初步评定成绩，交答辩委员会审定，盖学院公章。
“等级”用优、良、中、及、不及五级制（可按学院制定的毕业设计（论文）成绩评定办法评定最后成绩）。
华东交通大学毕业设计（论文）答辩记录
姓名
樊斐佳
学号
20062110040126
毕业届别
2010
专业
电子商务
题目
A*路径寻找算法的研究
答辩时间
2010-6-15
答辩组成员（签字）：
答辩记录：
记录人（签字）：
2010年6月14日
答辩小组组长（签字）：
2010年6月14日
A*算法的研究与设计
摘要
A*算法在计算机人工智能领域有着广泛的应用,本文主要研究在路径寻找中的应用,通过暴力搜索,贪心式搜索、纯启发式搜索之间的代码实现复杂度、空间和时间上的比较，介绍贪心和启发式搜索的结合搜索，即A*搜索的优点，并以直观的方式展现出来——在设计的寻路小游戏中，可以手动绘制障碍物地图，并在同一地图分别运行四种不同的算法，通过对各个算法结束遍历过的点进行染色直观地展示各算的耗时和最优解情况。
最后再进一步对A*搜索思想的研究，引出A*搜索的变形，IDA*搜索、B*搜索以及D*搜索。
相比A*搜索，IDA*可以节省更多的空间（比如IDA*可以解决A*无法实现的15数码问题），而D*搜索在障碍物不停变化的地图中通过动态估价可以避免每走一步就需要反复调用A*算法。
关键词：
路径寻找贪心搜索，启发式，A*搜索，IDA*搜索，D*搜索；
A*AlgorithmResearchandDesign
Abstract
A*algorithmpalyanimportantroleinthefieldofcomputerartificialintelligence，InthisPaper,WemainlystudyitsapplicationinPath-Finding,Let’sviewontheadvantagesanddisadvantagesofA*algorithmwhich’sComposedbyGreedysearchandHeuristicsearch,accordingtothecompareofviolencesearch,greedysearch,pureheuristic,andtheyhavedifferentcoderealizationofcomplexityandcomparisonofspaceandtime,IntheFindingpathgamewecandrawamapwithobstacles,andrunthefourdifferentalgorithmsonit,basedoneachendoftheergodicalgorithmpointafterdyeingvividlyrevealsthetime-consumingandcalculatetheoptimalsolution.
Finally,wemakeafurtherresearchonA*'sidea,andwealsocareabouttheVariationsofA*,suchas,theIDA*searchalgorithm,theB*searchalgorithm,andtheD*algorithm.ComparedwithA*,IDA*cansavemuchspacecost（forexample,IDA*cansolvethe15digitalgameproblem,butnotAstar）,andD*dowellinthemapwithobstaclesandconstantlychangingbydynamicevaluation,soitcanavoideachsteptocallA*algorithm.
Keyword:
FindingPath,GreedySearch,HeuristicSearch,A*Search，D*search
目录
1.1A*算法在路径寻找中的运用1
1.2何谓启发式搜索1
1.3A*算法原理2
1.4论文内容安排2
2.1最普通的暴力搜索3
2.2贪心搜索6
2.3纯启发式搜索8
2.4A*搜索9
2.5四种搜索在路径寻找中的比较11
3.1暴力搜索：
12
3.2贪心搜索：
12
3.3纯启发式搜索：
13
3.4A*搜索算法实现：
14
4.1问题描述15
4.2求解思路15
4.3算法实现15
5.1A*思想的总结17
5.2.A*的变形17
6.1系统介绍18
6.2界面设计18
6.3系统运行19
附录A.外文翻译-原文部分25
附录B.外文翻译-译文部分52
1绪论
20世纪末，随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，A*算法起着非常重要的作用，搜索算法，可以极大的提高搜索的效率和质量。
而一个低效的搜索算法，往往使得用户无法忍受。
A*算法在实际项目中有着非常多的应用。
在电子游戏的设计和开发中,随着硬件性能的不断升级,游戏的音效和视觉效果都得到了极大的提高和改善。
但人工智能技术的研究和应用还相对落后,因而游戏中非玩家角色的行为表现就显得很单调笨拙,严重影响游戏的品质。
因而近年来人工智能渐渐成为改善和提高游戏质量的热门研究课题,非玩家角色的行为既要聪明智能又要丰富多样。
在游戏软件中,人工智能是一个重要而又复杂的模块,而寻路算法是人工智能运用于电子游戏中的最基本问题之一。
1.1A*算法在路径寻找中的运用
A*算法实际上是一种基于广度优先搜索基础上的启发式搜索算法,通常采用估价函数:
f（n）=g（n）+h（n）对当前的搜索位置进行评估。
A*算法最缓慢的部分是在开启列表中寻找F值最低的节点,二叉堆方法通过对开启列表进行快速排序等,极大的优化了开启列表内节点元素的查找以及增删速度,一般在大多数场合会加快2～3倍,并且随着路径长度增加,搜索速度呈几何级数提升（10倍以上）。
在大地图上,只用一种网格密度进行寻路,通常或者很慢,或者走路不够真实。
分层寻路方法可极大地加快了A*搜索速度,它先在整个地图范围内使用低密度网格的宏观寻路方法,直至靠近目标对象后,再切换到高密度网格的微观寻路方法,一般游戏地图越大,A*搜索速度提高地越明显。
通过将A*搜索算法应用于掌机游戏Gauntlet的人工智能寻路系统后,实际验证和测试了改进和优化后的A*搜索极具时间效率和空间效率
1.2何谓启发式搜索
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。
这样可以省略大量无谓的搜索路径，提到了效率。
在启发式搜索中，对位置的估价是十分重要的。
采用了不同的估价可以有不同的效果。
我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
最佳优先搜索的最广为人知的形式称为A*搜索（发音为“A星搜索”）.它把到达节点的耗散g（n）和从该节点到目标节点的消耗h（n）结合起来对节点进行评价：
f（n）=g（n）+h（n）因为以g（n）给出了从起始节点到节点n的路径耗散，而h（n）是从节点n到目标节点的最低耗散路径的估计耗散值，因此f（n）=经过节点n的最低耗散解的估计耗散.这样，如果我们想要找到最低耗散解，首先尝试找到g（n）+h（n）值最小的节点是合理的。
可以发现这个策略不只是合理的:
倘若启发函数h（n）满足一定的条件，A*搜索既是完备的也是最优的。
如果把A*搜索用于Tree-Search,它的最优性是能够直接分折的。
在这种情况下，如果h（n）是一个可采纳启发式--也就是说，倘若h（n）从不会过高估计到达目标的耗散--A*算法是最优的。
可采纳启发式天生是最优的，因为他们认为求解问题的耗散是低于实际耗散的。
因为g（n）是到达节点n的确切耗散，我们得到一个直接的结论：
f（n）永远不会高估经过节点n的解的实际耗散.
1.3A*算法原理
A*（A-Star）算法是一种静态路网中求解最短路最有效的方法。
公式表示为：
f（n）=g（n）+h（n）,
其中f（n）是节点n从初始点到目标点的估价函数，
g（n）是在状态空间中从初始节点到n节点的实际代价，
h（n）是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h（n）的选取：
估价值h（n）<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。
但能得到最优解。
如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g（n）+sqrt（（dx-nx）*（dx-nx）+（dy-ny）*（dy-ny））；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。
明显优于Dijstra算法的毫无无方向的向四周搜索。
1.4论文内容安排
（1）第一章为论文绪论部分，主要讲述了A*算法在路径寻找中运用，何为启发式搜索，A*算法原理。
（2）第二章分别从代码实现复杂度、时间和空间上对比，介绍暴力搜索、贪心搜索、纯启发式搜索、A*搜索四种搜索算法在无障碍、有障碍地图中路径寻找中的应用
（3）第三章以上四类搜索算法的源码实现
（4）第四章为A*搜索在图论中第K短路径的应用
（5）第五章为A*算法的一些变形，及其思想总结
（6）第六章为系统设计
（7）第七章为总结和展望，对本次毕业设计进行总结，描述毕业设计中遇到的困难，自己对系统的不断探索，指出系统存在的不足，并对系统提出进一步的建议和方案。
2不同算法路径寻找中的对比
首先，我们来看一个大小为20*60的网格地图，有一起点S和终点E，如何以最快的速度找到一条从S到E的最短路径，在地图上加上障碍物之后又会有
升级会员 