毕业论文（设计）-A路径寻找算法的研究

《毕业论文（设计）-A路径寻找算法的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华东交通大学毕业设计（论文）题目：A窃路径寻找算法的研究A*AlgorithmFindingPath学院：软件学院专业：电子商务班级:姓名：学号:指导教师：完成日期:华东交通大学毕业设计（论文）任务书姓名学号毕业届別专业电了商务毕业设计（论文）题目A*路径寻找算法的研究指导教师学历研究牛职称副教授1、要求（作为评分标准）:（1）基本要求：1.深入了解A*算法的内部操作过程；2.了解A*算法如何在起点和终点间建立路径；3.设计以砖块环境为背景的小游戏程序来运用A*算法；4.掌握A*算法在图论屮次短路径中寻找的灵活运用；5.比较A*算法和其它几种启发式搜索算法的优劣；6.学习使用一些常

2、用工具软件，包括文字处理工具、压缩工具、图像制作工具、动画制作工具、网页制作工具、多媒休处理工具等。（2）创新性要求：1.研究A*算法的应用，广泛阅读相关论文，分析A*算法的改进算法；2.设计合理的佔价函数，提高A*算法的搜索效率，对A*算法进行新的改进。2、进度安排:•第一周：审题，调研，了解课题任务。查阅相关资料，学习人工智能相关技术；•第二周：查阅外文资料，完成相关资料的翻译；•第三周：完成开题报告；•第四〜六周：学习各种路径搜索技术，重点研究A*算法；•第七周：对小游戏模拟程序进行总体设计，对功能模块进行划分，完成数据结构的设计；•第八〜九周：完成小游戏程序的各功能模块的设

3、计，实现A*算法设计思想；•第十周：开始写毕业论文；•第十一〜十二周：边写论文，边调试、充实、完善游戏软件；•第十三周：按照毕业设计撰写规范的要求修改毕业论文，完成毕业论文；•第十四周：提交毕业论文，进行毕业答辩。指导教师签字：2009年11刀22L1系、部意见：题H及工作量符合本科培养要求是否是新题□是□否系、部主任签字：年月口题目发出FI期2009年12月1H设计（论文）起止时间年3M8日一年6月12H学院意见：同意发布题日□是□否毕业设计领导小组组长签章:华东交通大学毕业设计(论文)开题报告书课题名称A*路径寻找算法的研究课题来源导师指定课题类型设计导师学生姓名学号专业电子商

4、务一、开题报告内容：1、文献综述(1)•搜索算法的介绍和分类搜索算法称为“通用算法”，在算法常见的几大块，比如图论、数论、动态规划、计算几何、字符串等领域屮都被广泛应用，同时在人工智能屮占有重要的地们。但是由于它巨人的局限性和自身灵活性，也被认为是最难学难用的算法之一。搜索可分为H口搜索和启发式搜索，盲口的算法种类比较多，有纯随机搜索、广度优先搜索、深度优先搜索，迭代加深搜索、迭代加宽搜索，柱型搜索。启发式搜索包含，贪心搜索，A*搜索和ID*搜索。(2).搜索算法中的剪枝剪枝满正确性、准确性和高效性三个原则，优秀的剪枝往往可以很人程度上地加快一个算法的搜索速度，一般包含极端法、调整

5、法和数学法三种；极端法广泛地应用各种捜索算法的剪枝中，它的基本思想是能过对当前结点进行理想式，通过否定这样的“理想情况”来避免对当前结点的扩展；调整法的基本思路是通过对子树的比较前年重复子树和明显不是最有“前途”的子树；数学方法主要是针对一些具体的问题利用专门知识进行剪枝，例如，在图论中借助连通分量，数论中借助模方和的分析等。(3)路径寻找问题图论中的Dijkstra算法也可以进行最短路的寻找，但是当点比较多而边比较少的稀疏的图中，并不是最好的选择，而其他的方法，比如双向广搜索就在时间和空间上都优于它，如果在广搜索加上合理的启发式，即A*搜索，会更快！通过我写的两个小程序的比较和验

6、证发现，在无障碍物的地图屮搜索路径，用哈曼顿距离作为启发式，可以大减少算法运行过程屮点扩展的总数，而能找到最短的路径，而利用Dijkstra的每次找离起点最近的点扩展的思想，总扩展的点大大多于前者，从而算法运行速度也慢了很多，而在有障碍物的地图屮，前者虽然很快求解路径，但并不一定是最短路径，而后者仍可保证最短路径，假如我们定义g(n)为当前点到起始点的距离，h(n)为到终点的最短哈曼顿距离，而用f(n)=g(n)+h(n)作为我们算法的估价函数，我们会发现算法运行速度会高于后者而低于前者，但是我们可以得到一条最短•路径，这便是A*算法的特长所在，即保证算法的准确性又保证高效率！(4

7、)在阅读一些信息学竞赛国家队集训论文后，总结出可以快速度提高搜索效率的优化方法有：a.数据的有序化，比如用搜索解经典的装箱问题一一n个不同体积的物体放个一个体积为V的箱子，使得箱子刚好放满，如果先将不同物体按体积人小排序后再进行搜索，会提前找到最优解b.选择搜索对象，比如公交汽车的调度农安排问题，如果选择汽车作为对彖则每辆车对应不同的时间，而如果选择路径作为对象则对应的是不同的汽车，可以预见这种方法搜索过程中汽车会越来越少，该搜索树越深，枝条便会越少。C.搜索的策略选