《毕业论文--A算法演示系统》由会员分享，可在线阅读，更多相关《毕业论文--A算法演示系统（30页珍藏版）》请在金锄头文库上搜索。
1、河北农业大学 本科毕业论文(设计) 题 目： A*算法演示系统 学 院： 信息科学与技术学院 专业班级： 软件工程1002班 学 号： 学生姓名： 指导教师姓名： 指导教师职称： 讲师 2014 年 6月 1 日摘要本次课程设计的题目是“A星算法的演示系统”，A*算法在人工智能中是一种典型的启发式搜索算法,这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。本次课程设计要求能够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓演示出来。在对算法充分了解的基础上，演示算法的执行过程，就要涉及到图
2、像的绘制，而对于图像的编程，显然高级语言有其开发效率高的特点，java强大的运算和图形展示功能，使图像编程变得更加的简单和直观。本课题基于eclipse的java集成开发环境，设计并实现了A星算法的演示系统，展示A星算法如何进行启发式搜索和寻路的过程。实现了设置起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、重新寻路、添加默认障碍这些功能的操作。使用者能够通过自己的要求进行A星算法的演示和使用，本软件充分展示A星算法的执行过程。关键字：A*算法，启发式搜索，javaAbstractThe topic of the course design isA star algorith
3、m demo software, A * algorithm in artificial intelligence is A kind of typical heuristic search algorithm, this is A graphics in the plane ,have more than one node path, the algorithm of minimum through cost.it often be used in the game of mobile computing of NPC, or online games on mobile computing
4、 of BOT.The course design requirs to demonstrate the implementation process of the whole algorithm, can be single step demo, dynamic demonstration, the essence of the execution process of algorithm demo.on the basis of full understanding of the algorithm, Demonstrateing the algorithm implementation
5、process will involve the Graph drawing, and the programming on image, obviously a high-level language has the characteristics of its development of high efficiency, Java powerful computing and graphics display function, make the image programming more simple and intuitive.This project is based on ec
6、lipses Java integrated development environment, A star algorithm demo software was designed and implemented, showing how A star algorithm of heuristic search and pathfinding.Implements set the starting point and end point, barriers, clear obstacles, directly pathfinding, single step pathfinding, dyn
7、amic pathfinding, pathfinding again, add default barrier function of these operations.the user can use the software according to their requirments, the software fully shows the execution of A star algorithm.Keywords：AStar arithmetic ，heuristic search，java目录摘要1Abstract2目录31 需求分析41.1 编写目的41.2 背景41.2.1
8、 A*搜索算法介绍41.2.2 Dijkstra算法51.2.3 java语言介绍61.2.4 java图形化编程的知识81.3 任务概述81.4 运行环境规定91.5 其他A星软件的优劣9(1)软件一9(2)软件二102 概要设计112.1 界面设计112.1.1 软件的进入界面设计112.1.2 软件的进入界面的分析112.1.3 软件主题界面的设计122.1.4 软件主体界面的分析122.2 程序需要实现的功能133 详细设计143.1 类图的设计143.2 类之间的关系说明143.3 类图的分析153.4 程序的实现163.4.1 程序逻辑的设计163.3.2 找到link中结点的F值
9、最小的结点203.4.3 响应绘制方块paint的参数与getGraphics( )233.4.4 程序主体界面MyPanel中paint函数做的工作243.4.5 主体界面类做的工作243.3.6 鼠标监听mouseClicked OR mousePressed253.3.7 动态寻路的演示253.3.8 设置起点的工作253.3.9 设置终点的工作253.3.10 找不到路径的提示264 总结275 致谢286 参考资料291 需求分析1.1 编写目的A*算法作为为基本寻路算法常出现在游戏设计中，刚刚接触A*算法，难免初学者会产生迷惑，为了使算法的执行步骤更加的清晰，是算法的思路完整的展现
10、出来，此次课题的要求就是用图形化的方式，一步一步的展现A*算法的执行步骤，使想了解A*算法的人能够更清晰的理解此算法，等真正理解了，就会发现，原来游戏的寻路是这样的，从而也会是学习者有更大的兴趣深入其他算法的学习。1.2 背景1.2.1 A*搜索算法介绍A*在游戏设计中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法在说启发式搜索之前先提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解
11、问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序先查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态
12、空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说
13、详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) g(n)时，可以省略g(n)，而提高效率。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。像局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，并没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估
14、价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法，只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n) = g(n) + h(n)这里，f(n)是估价函数，g(n)是起点到节点n的最短路径值，h(n)是n到目标的最短路经的启发值。举一个例子，其实广度优先算法就是A*算法的
15、特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。游戏中速度和精确度之间的选择并不是全局的。在地图
