计算机第一学期大作业(排版)

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

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

3、* search algorithm. The judge in the state space of every possible location, and obtained optimal location according to certain criteria, and then to continue searching to the end of this location as the target location, the above is the basic definition of heuristic search. For each node must selec

4、t a minimum valuation, should be used in a minimum priority queue (also known as the least binary heap). Can be used directly. Of course do not forget the overloaded self-defined node operation character.A * algorithm characteristics: A * algorithm is theoretically optimal time, but it also has disa

5、dvantages: in theory the worst case, the growth of its space will be possible to the index level. The benefits of the search algorithm can be a lot of unwanted redundant path omitted, making time and space efficiency is greatly enhanced. Its main components OpenList, CloseList and valuation function

6、s.He can be applied to the routing path search path to locate on the map.Key words:Heuristic algorithm, the search path, the A * algorithm, the valuation function目 录引 言11 研究背景和意义21.1 背景及意义21.2 本文研究内容32 路径寻址和开发工具42.1 路径寻址的方法介绍42.1.1 模拟42.1.2 最短路径问题42.1.3 Dijkstra算法42.2 开发工具Eclipse53 基于搜索算法的机器人路径寻址73.

7、1 广度优先算法（BFS）73.2 深度优先搜寻（DFS）73.3 A*算法74 A*算法仿真系统设计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.1 SWING技术介绍185.2 仿真实验及结果比较185.2.1 g(n)的改变对结果的变化185.2.2 基于h(n)的变化对结果的影响246

8、结束语306.1 总结306.2 实验存在的问题和改善30参 考 文 献31发表学术论文情况32致 谢33引 言现实世界中有许许多多的不同的网络构成，交通网络，通信网络，计算机网络，贸易网络等等。网络中有一个十分重要的部分就是寻找各个节点之间的路径，路径的存在是非常多的，而最有的路径一直是人们所期望的。因此涌现了许许多多的不同的搜索算法，但是不同的算法之间有着十分显著的差别，我们需要根据不同的情况来使用不同的策略。算法有两个十分重要的特性就是空间和时间连个度量，他们对程序的运行产生了十分巨大的影响。在不断的研究中，更加优秀和智能的搜索算法也在不断出现。1 研究背景和意义1.1 背景及意义搜索算

9、法他们大致上可以被分成两个大的类型，即深度优先搜索（DFS）和广度优先搜索（BFS）。深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。而广度优先算法则是尽可能的先寻找与节点相同的同一层的节点。类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2Vit，并均标记为已访问过，然后再

10、按照Vi1、Vi2Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率太低，在这里就要用到启发式搜索了。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。这些算法都无一例外的将启发式的函数应用在这些算法中，优化了他的搜索的过程得出一个相对比较好的结果，可是在应用到具体的搜索过程中选取每一个最佳的节点的方法和策略是不尽相

11、同的。比如局部的优化搜索算法，他的目的就是在他的搜索的过程中间得到有优化的节点然后将其他备选的可能的节点删去，这些节点通常是他的兄弟节点（即在同一层的节点）以及父节点。但是上述的过程中也有个问题就是这一搜索的过程可能被局限在一个小的局部能然后不停的循环使得在这个循环外的可能的更优化的节点无法进入到搜索的过程中来，最后往往导致一个局部的最优解而忽视了全局可能的优化解。而最好优先伐则灵活的多了，在他的搜索的过程中，他不会删除一个节点他会保留它除了这个节点没有了子节点成为了一个死的节点，他在比较的过程中引入了以前计算过的节点的不同估价值然后和当前的值进行了比较通过这一比较的过程得到了一优化的解。这样

12、就会有效地避免了局部的最优化的解产生，可以将全局的可能的优化的解都考虑进来。最好优先算法一个代表就是A*算法，但是它比起普通的最好优先算法，又有着些许的不同，他在搜索的过程中添加了一个约束性质的条件。在面对一些实际的问题中是，人们总是会要求找出状态空间内可以搜索到的最好的路径。也就是说他们希望可以用最少的时间和空间的代价得出最优化的解，而A*就是为了这些情况的出现而准备的。1.2 本文研究内容这次我们主要实现的是A*算法，他是启发式搜索算法的一种。使用它的估价函数产生不同节点的估价值对不同的路径进行评估，最后得出一个最好的路径。通过对于A*算法的应用，使得他可以在随意的设置的障碍物之间找到最好

13、的路径，从起点到达终点。由于障碍物时随意摆放的因此，可以显示他的智能化，而不是僵化的产生的一个最优化的路径，这在许多方面有个重要的应用，比如游戏和导航中，这些都需要智能化寻址。而不是僵化的指导方式。2 路径寻址和开发工具2.1 路径寻址的方法介绍2.1.1 模拟为了模拟现实中的情况，我们借用物理中的质点的概念，将物体缩小为一个方格（类似一个点），他的路径的搜索则是在一个由方格组成的途中绕开他的障碍物到达终点。2.1.2 最短路径问题最短路径问题是图论研究中的一个经典算法问题，他的目的就是最后产生起点到终点之间最短的路径。涉及到他的算法具体的逻辑的过程主要有下面几种：1已知了起点的求出最优化路径

14、问题。这一问题比较适合使用Dijkstra算法。2已知了终点未知的的最短路径问题，与上一个问题恰恰相反这是已知了终点的情况下得出最优化路径的问题。 这涉及到图论中无向图的原理，在这一理论中上述两个问题是等价，而在有向图的理论中前一个问题就是讲将已知的路径反向从而确定出起点的问题。3已知了起点终点的最优化路径问题这是为了找出这两个结点之间的各种路径选择的最好的解。这又被称为全局最短路径问题，他适合使用Floyd-Warshall算法。我们这次的模拟中是已知起始点，因此使用类似于Dijkstra算法比较相似的A*算法。2.1.3 Dijkstra算法戴克斯特拉算法（即是Dijkstra's

15、 algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉发明的。他的目的是为了解决邮箱途中某一个节点到其他的节点的有优化的路径的问题。比如说在一张有向图中一个节点表示一个超市，而有向图各边的权重则表示了每个路径的距离大小，这一个算法就是为了找出节点间即超时间最短的距离的大小。在算法的开始初始化一个每条边都有权重的有向图G，和G中的起点节点A。在这里我们将S 表示为一个集合，它包含了G中所有节点的集合。有向图中的一条边，我们可以将它表示成由两个节点组成的有序的元素对。（a,b） 表示从某一个节点a到b是相通的他们之间存在一条边e。然后我们将E表示为所有边的集合，而每天存在的边权重

16、书将由权重函数W:E（e>0）定义。那么我们就可以将W(a, b) 就是从顶点a到顶点b的消耗值，且他恒为正值。而每条边的消耗值就可以被理解成两个节点的距离的值。那么同理推得任意的两个节点间的路径的消耗值，就是连接这两个节点的路径的总的距离值的和。已知有S中有顶点m和n，而Dijkstra算法已算出这两节点m和n的最好的路径，通常就是最短的路径。同时这个算法也可以在有向图G中，通过点m找到他到其他相通的点的最短的路径值。Dijkstra算法的工作原理就是通过为每个存在的点n记录他可以找到的m到点n最短的路径，然后将这些路径相互之间进行比较。在初始化的时候，起点m的权重值设置为0，他的数学

17、表达是dm=0,要是存在一条边连接了m,n两个节点，那么dm就等价与w（m,n）,然后我们将其他存在的节点（包括了节点m无法直接到达的）的权重值设为了无穷，这就表示了目前我们并不知道节点m到这些节点的路径的存在和大小。（用数学表达就是说S中所有节点s除m和n 外 ds = ）。那就是说当我们结束了算法后，ds 中记录的应该是从m到n的最优的路径，一个特殊的情况是记录的值是无穷那么就表示就是这条路径并不存在。Dijkstra算法的搜索方式就是从一条边探索到另一条边上：比如，p与点n可以相通那么边（p,n）可以加到边（m,n）后面，那么这条路劲的长度就从w（m,n）变成了dp+w(m,n)。然后将

18、这条边和已经记录的 dv1比较，如果dv的值相对要小，那么就可以用新值来替代当前 dv1 中的值，这就是最基本查找路径的方式。这一不断搜索的过程一直循环到记录的dv是可以找到的最短的路径。Dijkstra算法算法通过不断比较和替换dv的值，在他达到最优化的值时，每一天存在的边都只会被比较一次。这一算法保留两个节点的集合P,Q。集合P的作用就是记录了已知的所有可能的边通过相互的边最终产生的最短路径的值dv他所代表的节点（因为在运算结束以前可能存在不同解），而集合 Q 将会记录剩下不在集合P中的节点。集合P初始状态应该是空集，在以后算法不停搜索的过程中每一次搜索的都有一个节点从 Q 被移动到P中。

19、而这个被选中的节点是 Q 中拥有最小的 du 值的顶点。当某一个节点s 从 Q 中转移到了P中，就相当于算法对每条可能的存在的相连的边 (u, v) 进行搜索。这点类似于对一颗树不停向下级子节点进行搜索，并将值记录在dv中。如果有已知信息可用来估计某一点到目标点的距离，则可改用A*搜寻算法，以减小最短路径的搜索范围。与最短路径问题相关最有名的一个问题是旅行商问题（Traveling salesman problem），此类问题要求找出恰好通过所有目标点一次且最终回到原点的最短路径。然而该问题为NP-完全的，因此旅行商问题不太可能具有多项式时间解法。由于本人能力有限，所以不探索TSP问题，希望以

20、后有时间继续研究。2.2 开发工具EclipseEclipse是著名的跨平台的自由集成开发环境（IDE）。Eclipse的基础是富客户机平台（Rich Client Platform，即RCP）。RCP包括下列组件：核心平台（启动Eclipse，运行插件）OSGi（标准集束框架）SWT（可移植构件工具包）JFace（文件缓冲，文本处理，文本编辑器）Eclipse工作台（即Workbench，包含视图（views）、编辑器（editors）、视角（perspectives）、和向导（wizards）Eclipse采用的技术是IBM公司开发的（SWT），这是一种基于Java的窗口组件，类似Java

21、本身提供的AWT和Swing窗口组件；不过IBM声称SWT比其他Java窗口组件更有效率。Eclipse的用户界面还使用了GUI中间层JFace，从而简化了基于SWT的应用程序的构建。Eclipse的插件机制是轻型软件组件化架构。在富客户机平台上，Eclipse使用插件来提供所有的附加功能，例如支持Java以外的其他语言。已有的分离的插件已经能够支持C/C+（CDT）、PHP、Perl、Ruby，Python、telnet和数据库开发。插件架构能够支持将任意的扩展加入到现有环境中，例如配置管理，而决不仅仅限于支持各种编程语言。Eclipse的设计思想是：一切皆插件。Eclipse核心很小，其它

22、所有功能都以插件的形式附加于Eclipse核心之上。Eclipse基本内核包括：图形API（SWT/Jface），Java开发环境插件（JDT），插件开发环境（PDE）等。3 基于搜索算法的机器人路径寻址搜索算法分为了广度优先算法(BFS) 和深度优先搜寻(DFS)这主要的两种，首先介绍些这两种算法的原理和优缺点。为了方便描述这一搜索的过程我将所有可能的点都认为一个树上的各个的节点。而起始点则是整棵树的父节点，终点则是树的某一个子节点，而寻求最短的路径则是找到一条路径具有最少的层数和权值，达到这个设定的子节点。3.1 广度优先算法（BFS）BFS算法试图找出一点与最初始的点最接近在一层内，但是

23、他不会连续两次访问同一个节点。他的最好的情况为o(bd)，最差的情况为o(bd)此处b-树的广度，d-树的深度。这个算法的好处是他一定可以找出一个解，并且解出步数将会小于DFS的步数，因为对于树来说，深度往往要比树的广度要打，但是这一算法将会大量的耗费内存，他会将他所有的可能的节点全部保存下来，因此他在算法效率上十分的笨重。BFS算法倾向于使用队列作为他的数据处理方式。3.2 深度优先搜寻（DFS）DFS算法与BFS的区别就是他将会对每个节点子节点优先进行搜索，这将会对具有很大广度的树来说更加有效率，它最好的情况为o(b*d)最坏的情况为 o(bd)。此处b-树的广度，d-树的深度。DFS对于

24、某些特殊的情况更加使用，因此它的使用范围相对BFS小点，但是它的优势就是BFS就会使用bd个空间用于存储节点，而DFS不会，它将大大节省空间。DFS更加倾向于使用堆债作为他的数据的处理方式。3.3 A*算法以上两种算法BFS肯定能找出答案，但是他会耗费大量的资源，DFS虽然效率更好但是他只是用某些特殊的情况，而且他有可能会在一个局部内死循环，从而得出一个局部的最优解，而不是全局的最优解。这里引入A*算法，A*算法更加的智能它引入了一个估价函数的机制，从而避免了局部最优解的局面。*的意思是他比起普通的算法更加的优化。对于A算法来说，他不会比较估价函数的值，而A*算法则会比较他们之间的值，从而得出

25、最好接，这就会将局部以外的可能更优的节点加入到搜索的过程中。这个函数式为f*(n)=g*(n)+h*(n)，最重要的是找出h*(n)的值如果无法计算出一个好的值，那么他的效率将会和上面说到算法一样低下，因此它最好的情况是O(b*d)最差的情况是O(bd)。此处g*(n)不是重点的原因是因为在其他的位置可能存在更好的解，这就会防止局部最优解的产生。A*搜寻算法，他可以应用在具有多个不同节点的路径的图上，同时求出一个最短路径的算法。它的最常见的应用是在游戏中NPC的移动方面，或者是在网络游戏中BOT的移动计算方面。上文中提到该算法像与Dijkstra算法的原理基本一致，目的是为找出一条最短的路径；

26、同时他也像BFS一样，进行启发式的搜索。在这个算法中引入了一个叫做估价值的概念，它的大致的原理如下：g(n)表示从起点到任意节点n的路径的距离长度，h(n)表示图中任意一个存在的节点n到目标节点的股价值的大小。 因此，A*算法的关于估价值的公式可以表示为下式：f(n)=g(n)+h(n)。 这个公式具有以下几个特殊的地方：如果h(n)为0，那么f(n)=g(n)，这种情况出现在求出起点到任意节点n的最短路径，这种情况下问题就类似于单源最短路径的问题，此时就可以应用Dijkstra算法。如果h(n)<=“n到目标的实际距离”， 那么不停比较这些值就可以最终产生出最优解。不过当h(n)的值越

27、来越小的时候，他所涉及到的需要计算的节点数目将会越多，此时的算法效率将会低下。比如当应用到几何型的网络中时，可以取两节点间直线距离（即是欧几理德距离）做为节点的估价值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样的话受到估价值h的影响个，在g值一定的情况下估价函数f会受到h的约束，f的值越小就意味着h的值也小，同时表示这个节点距离目标点就越近，这样话就是表示搜索到的每一个点就会产生一条最短路径。而这点明显和Dijstra算法在点四周漫无目的的以枚举的方式进行寻找就好很多，因为他对每个点进行了预判剔除了不必要的点，极大地提高了效率。这里需要提到h（

28、n）的一个属性他被称为信息性，他的意思是在估算一个节点的估价值的时候的约束条件，当一个节点的约束条件越多或者说他的信息性越多的话，他被剔除的可能性就越大，这样大量不需要计算的节点就会被排除，所以我们就可以说这个估价函数很好或者是这个算法更加优秀。这个特性使得它比广度优先算法优秀很多，因为他的h(n)为0，换句话就是它不具有信息性即启发性信息。但是在路径搜索的过程中，他往往要求了很高的实时性，h(n)的信息性越强，他的要求的计算量就会相对上升，使得他耗费的时间也就会越大。此时为了满足他的实时性，我们必须在一定程度上减少的h(n)的信息性，即减少节点的约束性的条件。但是他付出的代价就是准确性会降低

29、，这就是一个我们需要权衡的问题。简化的A*算法流程：搜索区域被划分成了方形网格。简化搜索区域，是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从A到B我们经过的方块的集合。一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。1.从起点开始，他会将其周围待处理的节点放入一个列表中。一开始只有一个，即是起点，但是之后就会多起来。表格内包含待检查的方格。2.寻找起点周围可到达的一切可通过的方格，放弃不可通过的方格。把这些可行的方格加入到列表中。为这些方格保存点A为这些方格的父方格。父方格很重要类

30、，类似于树中的父节点。3.从列表中删除点A，将其加入另一个表（称为关闭列表），这个列表中保存所有不需要再次检查的方格。接着重复以上步骤，找出每个可行的方格的表和关闭列表。类似于一棵树，寻找他的最小的路径。选择路径中经过哪个方格的关键是下面这个等式：F=G+H*G=从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。*H=从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的，H的值将会是不定的。此为最简单的方式。既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它父节点的G值，然后依照它相对父节点是对角线方向或者直角方向(非对角线)，分别增加和。例子中这个方法的需求会

31、变得更多，因为我们从起点方格以外获取了不止一个方格。H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向，然后把结果乘以10。这被称为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数，在那里你不能沿对角线方向穿过街区。很重要的一点，我们忽略了一切障碍物。这是对剩余距离的一个估算，而非实际值，这也是这一方法被称为启发式的原因。想知道更多？你可以在这里找到方程和额外的注解。F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的，

32、F被打印在左上角，G在左下角，H则在右下角。为了继续搜索，我们简单的从开启列表中选择F值最低的方格。然后，对选中的方格做如下处理：4，把它从开启列表中删除，然后添加到关闭列表中。5，检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其他无法通过的地形)，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节点。6，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用新的路径到达它的话，G值是否会更低一些。如果不是，那就什么都不做。以上就是A*算法的主要的过程，但是无法体现估价函数重要的价值。为了更加明了的解释

33、这格的重要性，我将用华容道作为例子来解释他的重要性。有一个3*3的方格81345276他最终的目的是变成12384765他将会使用两种不动估价函数，在附录中将会有这两种情况的图片使用了两种不同的估价函数f(n)good 和f(n)weak 都最终得到了结果但是f(n)good的估价函数效率更加高。我们通过更加深入的观察这些过程可以了解到为何f(n)weak 用了更多的步数才得到了结果，从一开始，搜索的步骤直接导向了有最终结果的那个分支。但是在f(n)weak 达到这个路径之前他多使用了4步才搜索到了这个具有最终解的分支。并且f(n)good 三个子节点的估价值远远高于f(n)weak的估价值是

34、的结果更加具有了区分度，更加容易得出具有答案的分支。再设计f(n)函数的时候，h(n)必须谨慎的设计，如果随意设置就会导致算法效率及其的低下。h(n)的值可以根据不同的应用的场景特殊设计。4 A*算法仿真系统设计4.1路径寻址系统概述建立一个可以自由画障碍物的程序，在起点到终点的过程中可以绕过障碍物。寻找一个最优的路径。并且可以保存及加载路径，一边可以用相互之间的比较。4.2 对用户界面进行模块设计4.2.1 主窗口界面使用JAVA的SWING技术搭建一个UI界面主要的程序入口为AStarDemo文件，他会负责加载各个窗体的组建AstarPanelastarPanel = newAstarPa

35、nel(15,15,60,40);StatusPanelstatusPanel = newStatusPanel();astarPanel.setStatusPanel(statusPanel);frame.setJMenuBar(newAStarMenuBar(astarPanel);frame.getContentPane().add(new ControlPanel(astarPanel), BorderLayout.NORTH);frame.setVisible(true);frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);以上代

36、码将astarPanel，statusPanel，AStarMenuBar，ControlPanel等相关的组建加入到UI中。4.2.2 绘画过程代码astarPanel作用是最主要他负责在界面上画出障碍物和画出计算出的路径，使得A*算法画出他算出的路径。并且可以显示出每个节点的相应的坐标。g2d.fillRoundRect(x, y , width, height, arc, arc);g2d.setComposite(TIPS_COMPOSITE2);g2d.setColor(TIPS_FG);g2d.drawString("Current grid num : ("

37、+ tipsPoint.getLocation().x + ", "+ tipsPoint.getLocation().y + ")", x + 15, y + 15);g2d.dispose();其上为显示坐标的代码在4.2.1中第一句画设置了一个60*40的表格而每个节点的大小为15pix*15pix的背景。publicvoidpaintComponent(Graphics g) super.paintComponent(g);fillBarrier(g);fillTargetAndSourceGrid(g);fillOpenList(g);fill

38、AStarPath(g);fillDrawData(g);drawGridLine(g);drawTips(g);以上代码的绘画逻辑是：图4.1 绘画代码逻辑4.2.3 工具栏代码AStarMenuBar的作用是显示菜单栏，它的基本显示的代码：enumMainMenuFile("File", 'F'),View("View", 'V'),Help("Help", 'H');publicSubMenu getSubMenus() if(subMenus=null)List<SubMe

39、nu>tmp = newLinkedList<SubMenu>();for(SubMenusubMenu : SubMenu.values()if(subMenu.getFatherMenu()=this)tmp.add(subMenu);subMenus = newSubMenutmp.size();subMenus = tmp.toArray(subMenus);returnsubMenus;他有三个主菜单组成使用，getSubMenus()方法得到下层的菜单。ControlPanel的作用是实现界面上的三个按钮通过调用不同的函数实现功能，三个函数是:startFind(

40、)这是算法开始的入口，是最重要的函数他将调用他的一个find()方法实现他的路径搜索。clearPath()清理路径clearMap()清理障碍物，起原理同上个函数4.2.4 按钮代码存在三个按钮JButtonstartButton = new JButton("Start");JButtonclearButton = new JButton("ClearPath");JButtondrawButton = new JButton("ClearMap");这三个按钮分别触发三个函数实现各自的功能publicvoidclearPath(

41、) currentDrawIndex = 0;astarMap.clearOpenList();此步将路径清除的同时将数据清理，避免对下次计算产生影响publicvoidclearMap() for (int i = 0; i <drawData.length; i+) for (int j = 0; j <drawDatai.length; j+) drawDataij = -1;rebuildAstarMap();此步将节点的绘图信息清空，然后重新画出新的图（即是空的图）4.2.5 状态栏代码状态栏的目的是为了显式的表示算法的效率，对实验的总结很有必要。这里计算的算法结束的当前

42、的时间减去开始记录下的时间updateCostTimeMillis(System.currentTimeMillis() - start);4.3 对算法实现进行设计4.3.1 路径组成函数和搜索逻辑设计以下则是最重要的部分对于算法的实现，上面已经提及到find（）方法将会最终完成这个程序最重要的功能，寻找路径。public List<AStarNode> find() init();AStarNode current = null;while(!isEnd() && !isFind()current = getMinFNodeFromOpenList();if(i

43、sAchieve(current)buildPath(current);isFind = true;elseadd2CloseMap(current);for(AStarNode neighbor : getNeighbor(current)if(neighbor=null | isInCloseMap(neighbor)| isCanNotGo(current, neighbor)continue;booleanisBetter = true;AStarNodenodeFromOpenList = getNodeFromOpenList(neighbor);if(nodeFromOpenLi

44、st!=null)inttg = neighbor.distinctG(current);isBetter = tg>neighbor.getG() ? false : true;elseadd2OpenList(neighbor);if(isBetter)neighbor.reCalculatorGAndH(current, target);return path;上述算法一开始将图初始化，并且判定时候已经找到路径或者已经到达了终点，如果不是则开始寻找，寻找最初，将判断，这个节点是否有相邻的节点，相邻的节点时候已经搜索到，相邻节点是否在已有路径中。if( (offsetX=1 &

45、;&offsetY=-1 && (isValidX(from.getX()-1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()-1 | isValidY(from.getY()+1) &&STATE_BARRIER=astarDatafrom.getY()+1from.getX() |(offsetX=1 &&offsetY=1 && (isValidY(from.getY()-1) &&STATE_BARRIER=astarDatafrom

46、.getY()-1from.getX() | isValidX(from.getX()-1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()-1) |(offsetX=-1 &&offsetY=1 && (isValidX(from.getX()+1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()+1 | isValidY(from.getY()-1) &&STATE_BARRIER=astarDatafrom.get

47、Y()-1from.getX() |(offsetX=-1 &&offsetY=-1 && (isValidX(from.getX()+1) &&STATE_BARRIER=astarDatafrom.getY()from.getX()+1 | isValidY(from.getY()+1) &&STATE_BARRIER=astarDatafrom.getY()+1from.getX()上述的的代码根据每一个节点相对于父节点的相对位置进行判断，判断是否可以通过这个节点。dopath.add(0, current);current

48、 = current.getFather();while(current!=null);这就是路径的组成他将她装载到一个动态数组中，使得以后在绘画出路径的时候可以直接点调用。并且这样的设计也易于路径的保存，方便了试验相互之间的比较。int index = 0;floatminF = openList.get(index).getF();int length = openList.size();for(int i=1; i<length; i+)AStarNodeaStarNode = openList.get(i);if(minF>aStarNode.getF()minF = aS

49、tarNode.getF();index = i;这段代码就是将得出来的估计值和已有的估价值相互比较，得出最好的结果。在上面的介绍中其实已经可以看出在这个算法中起到最重要的作用其实是节点及其周边环境。因此，算法中单独写了关于节点进行判断和算法运算的部分。4.3.2 节点判断函数及属性函数的设计AStarMap.java实现的路径总体的策略（即以上的代码）AStarNode.java则是实现路劲上每一个点的判断和下一个节点选择的事宜。在AStarNode.java中所使用的方法在3.1已经有了详细的描述，下面则是实现的代码：publicvoidinit(AStarNode target) thi

50、s.g = 0;this.h = heuristicCostEstimate(this, target);this.f = g+h;此函数的作用就是判断这个子节点是否能称为最优路径的下一个节点的函数。其中h是个很重要的度量，他将用：return (Math.abs(source.x - target.x) + Math.abs(source.y - target.y)*G_0;对角的平方差来计算他的值，值越小就意味着他离他的父节点就越近。这里值一开始会给一个预定的值以方便运算publicintdistinctG(AStarNode father) intoffsetX = x-father.x

51、;intoffsety = y-father.y;int distinct = 0;if(offsetX=0 &&offsety=-1)distinct = G_1;elseif(offsetX=1 &&offsety=-1)distinct = G_2;elseif(offsetX=1 &&offsety=0)distinct = G_3; . . .privatefinalstaticintG_1= 10;privatefinalstaticintG_2= 14;privatefinalstaticintG_3= 10;privatefina

52、lstaticintG_4= 14;privatefinalstaticintG_5= 10;一个方块各个角上的值都是最大的，边上的值则比他小一点。从上述的带那种可以看出G_N的值是根据他的位置来确定，他的位置设置的代码为if(offsetX=0 &&offsety=-1)distinct = G_1;这个就相当于（0，-1）的坐标thrownewAStarPositionException("Unvalid relation between current node("+this+") and fater node("+father+&

53、quot;)");returndistinct+father.g;为了保证不会出现局部最优的情况，他将调用下一函数再次计算是否存在一个更好的节点：publicvoidreCalculatorGAndH(AStarNode father, AStarNode target) this.g = distinctG(father);this.h = heuristicCostEstimate(this, target);this.f = g+h;this.father = father;以上就是程序一个基本的算法的实现。5 仿真实验结果的比较及界面UI图5.1 初始软件界面上面就是A*算法

54、 的具体的实现的界面，采用的是JAVA的swing的技术，运用JAVA自带的UI组建搭建一个具体的界面。当点击各个按钮将会触发各个函数。5.1 SWING技术介绍Swing 是一个为Java设计的GUI工具包。 Swing 是 JAVA基础类 的一部分。 Swing 包括了图形用户界面 (GUI) 器件 如：文本框，按钮，分隔窗格和表。SWING 提供许多比AWT更好的屏幕显示元素。它们用纯Java写成，所以同Java本身一样可以跨平台运行，这一点不像AWT。 它们是JFC的一部分。 它们支持可更换的面板和主题（各种操作系统默认的特有主题），然而不是真的使用原生平台提供的设备，而是仅仅在表面上

55、模仿它们。这意味着你可以在任意平台上使用JAVA支持的任意面板。 轻量级元件的缺点则是执行速度较慢，优点就是可以在所有平台上采用统一的行为。5.2 仿真实验及结果比较5.2.1 g(n)的改变对结果的变化图5.2 第一次运行的路径图这是任意画出的障碍物，灰色显示的就是路径中的障碍物。而蓝红色的则是寻找出的路径，可以看书它相对而言是一天最短的路径。在他一开始的时候他明显是以对角线的方式进行着搜索，这是因为在AStarNode。JAVA文件中，定义了每个点的估价值我开始讲对角线上的估价值设为最高，/* * G8G1G2 * G7G3 * G6G5G4 */privatefinalstaticintG_1= 10;privatefinalstaticintG_2= 14;privatefinalstaticintG_3= 10;privatefinalstaticintG_4= 14;privatefinalstaticintG_5= 10;privatefinalstaticintG_6= 14;privatefinalstaticintG_7= 10;privatefin