A算法演示系统毕业设计

1、摘要本次课程设计的题目是“ A星算法的演示系统”，A*算法在人工智能中是一种典型的 启发式搜索算法，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。 常用于游戏中的NPC勺移动计算，或在线游戏的BOT勺移动计算上。本次课程设计要求能 够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓 演示出来。在对算法充分了解的基础上，演示算法的执行过程，就要涉及到图像的绘制，而对于 图像的编程，显然高级语言有其开发效率高的特点，java强大的运算和图形展示功能，使 图像编程变得更加的简单和直观。本课题基于 eclipse的java集成开发环境，设计并实 现了 A星

2、算法的演示系统，展示 A星算法如何进行启发式搜索和寻路的过程。实现了设置 起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、重新寻路、添 加默认障碍这些功能的操作。使用者能够通过自己的要求进行A星算法的演示和使用，本软件充分展示A星算法的执行过程。关键字：A*算法，启发式搜索，javaAbstractThe topic of the course design isA star algorithm demo software, A * algorithm in artificial intelligence is A kind of typical heuristic sear

3、ch 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 of BOT.The course design requirs to demonstrate the implementation process of the whole algo

4、rithm, can be single step demo, dynamic demonstration, the essenceof the execution process of algorithm demo.on the basis of full understanding of the algorithm, Demonstrateing the algorithm implementation process will involve the Graph drawing, and the programming on image, obviously a high-level l

5、anguage 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 eclipses Java integrated development environment, A star algorithm demo software was designed an

6、d 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, dynamic pathfinding, pathfinding again, add default barrier function of these operations.the user

7、 can use the software according to their requirments, the software fully shows the execution of A star algorithm.Keywords： AStar arithmetic , heuristic search, java目录 TOC o 1-5 h z HYPERLINK l bookmark0 o Current Document 摘要.0 HYPERLINK l bookmark2 o Current Document Abstract1. HYPERLINK l bookmark4

8、 o Current Document 目录2. HYPERLINK l bookmark6 o Current Document 1需求分析3.编写目的3.背景3.A*搜索算法介绍.3.Dijkstra 算法4.java语言介绍 5.java图形化编程的知识 7.任务概述7.运行环境规定 8.其他A星软件的优劣8.(1)软件一 8.软件二9. HYPERLINK l bookmark8 o Current Document 2概要设计1.0界面设计10软件的进入界面设计10软件的进入界面的分析10软件主题界面的设计1.1软件主体界面的分析1.1程序需要实现的功能 1.2 HYPERLINK

9、l bookmark10 o Current Document 3详细设计1.3类图的设计13类之间的关系说明1.3类图的分析14程序的实现15程序逻辑的设计1.5找到link中结点的F值最小的结点 1.9响应绘制方块paint的参数与getGraphics( )2 2程序主体界面 MyPanel中paint函数做的工作 2 3主体界面类做的工作23鼠标监听 mouseClicked OR mousePressed.24动态寻路的演示24设置起点的工作24设置终点的工作24找不到路径的提示25 HYPERLINK l bookmark12 o Current Document 4总结26. H

10、YPERLINK l bookmark14 o Current Document 5致谢27. HYPERLINK l bookmark16 o Current Document 6参考资料281需求分析编写目的A*算法作为为基本寻路算法常出现在游戏设计中，刚刚接触A*算法，难免初学者会产生迷惑，为了使算法的执行步骤更加的清晰，是算法的思路完整的展现出来，此次课题的 要求就是用图形化的方式，一步一步的展现 A*算法的执行步骤，使想了解 A*算法的人能 够更清晰的理解此算法，等真正理解了，就会发现，原来游戏的寻路是这样的，从而也会 是学习者有更大的兴趣深入其他算法的学习。目乐A*搜索算法介绍A*

11、在游戏设计中有它很典型的用法，是人工智能在游戏中的代表。A*算法在人工智能 中是一种典型的启发式搜索算法在说启发式搜索之前先提状态空间搜索。状态空间搜索，如果按专业点的说法就是将 问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求 一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。 由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造 成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解 实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜 索。常用的状态空间搜

12、索有深度优先和广度优先。广度优先是从初始状态一层一层向下找， 直到找到目标为止。深度优先是按照一定的顺序先查找完一个分支，再查找另一个分支， 以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的 解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间 中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测 的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径

13、，提高了效率。在启 发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到 n节点的实际代 价，h(n)是从n到目标节点最佳路径的估计代价。 在这里主要是h(n)体现了搜索的启发信 息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) g(n)时，可以省略g(n),而提高效率。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然 A*也是。这些算法都使用了启发函数，但在具体的选取最

14、佳搜索节点时的策略不同。像局 部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点， 而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节 点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先 就聪明多了，他在搜索时，并没有舍弃节点(除非该节点是死节点)，在每一步的估价中 都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防 止“最佳节点”的丢失。那么 A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法，只不过要加上一些约束条件罢了。由于在一些 问题求解时，我们希望能够求解出

15、状态空间搜索的最短路径，也就是用最快的方法求解问 题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n) = g(n) + h(n)这里，f(n)是估价函数，g(n)是起点到节点n的最短路径值，h(n)是n到目标的最 短路经的启发值。举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0 ,这种h(n)肯定小于h(n),所以由前述可知广度优先算法是一种可 采纳的。实际也是。当然它是一种最臭的 A*算法。再说一个问题，就是有关h(n)启发函数的信

16、息性。h(n)的信息性通俗点说其实就是在 估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估 价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的 h(n)=0 , 一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。游戏中速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要 的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变 方向，则在接近当前位置

17、的地方，选择一条好的路径则是更重要的，因此为何要对后续路 径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要， 但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。所以A星算法应用在游戏中时可以根据具体的情况为各种不同的障碍设置不同的加权值是尽可能的出最有效的方案。Dijkstra 算法图1.1 Dijkstra算法的执行图Dijkstra 算法迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径 问题，算法最终得到一个最短路径树。并没有启发寻路，属于A*算法的特例。这个算法的 工作过程就是从起始点开始，不断的向未知点扩展，使从已知点集合到达任意未知点的距

18、离权重都是最小的，这样当扩展到终止点的时候，也就找到了最短的权重。java语言介绍(1)起源Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计语言 (以下简称Java语言)和Java平台的总称。由James Gosling和同事们共同研发，并在 1995年正式推出。Java最初被称为Oak,是1991年为消费类电子产品的嵌入式芯片而设 计的。1995年更名为Java,并重新设计用于开发Internet应用程序。用Java实现的HotJava 浏览器(支持Java applet )显示了 Java的魅力：跨平台、动态的 Web Internet 计算。

19、 从此，Java被广泛接受并推动了 Web勺迅速发展，常用的浏览器均支持 Javaapplet。另 一方面，Java技术也不断更新。(2)组成Java由四方面组成：Java编程语言Java文件格式Java 虚拟机(JVM)Java应用程序接口(Java API)(3)体系Java 分为三个体系 JavaSE (J2S6 (Java2 Platform Standard Edition , java 平台 标准版)，JavaEE(J2EE)(Java 2 Platform,Enterprise Edition , java 平台企业版), JavaME(J2ME)(Java 2 Platform

20、 Micro Edition , java 平台微型版)。(4)优势与传统程序不同，Sun公司在推出Java之际就将其作为一种开放的技术。全球数以 万计的Java开发公司被要求所设计的Java软件必须相互兼容。“Java语言靠群体的力 量而非公司的力量”是Sun公司的口号之一，并获得了广大软件开发商的认同。这与微软 公司所倡导的注重精英和封闭式的模式完全不同。Sun公司对Java编程语言的解释是：Java编程语言是个简单、面向对象、分布式、 解释性、健壮、安全与系统无关、可移植、高性能、多线程和动态的语言。Java平台是基于Java语言的平台。这样的平台非常流行。因此微软公司推出了与之 竞争的

21、.NET平台以及模仿Java的C#言。Java是功能完善的通用程序设计语言，可以用来开发可靠的、要求严格的应用程序。(5)语言特征Java编程语言的风格十分接近 C语言、C+1言。Java是一个纯粹的面向对象的程序 设计语言，它继承了 C+语言面向对象技术的核心。Java舍弃了 C语言中容易引起错误的 指针(以引用取代)、运算符重载(operator overloading )、多重继承(以接口取代) 等特性，增加了垃圾回收器功能用于回收不再被引用的对象所占据的内存空间，使得程序 员不用再为内存管理而担忧。在 Java 1.5 版本中，Java又引入了泛型编程(Generic Programm

22、ing) 类型安全的枚举、不定长参数和自动装 /拆箱等语言特性。Java不同于一般的编译执行计算机语言和解释执行计算机语言。它首先将源代码编译 成二进制字节码（bytecode）,然后依赖各种不同平台上的虚拟机来解释执行字节码。从 而实现了 “一次编译、到处执行”的跨平台特性。不过，每次的执行编译后的字节码需要 消耗一定的时间，这同时也在一定程度上降低了Java程序的性能。（6）主要特性Java语言是易学的。Java语言的语法与C语言和C+胡言很接近，使得大多数程序员 很容易学习和使用Java。另一方面，Java丢弃了 C+”很少使用的、很难理解的、令人迷 惑的那些特性，如操作符重载、多继承、

23、自动的强制类型转换。特别地，Java语言不使用指针，而是引用。并提供了自动的废料收集，使得程序员不必为内存管理而担忧。Java语言是强制面向对象的。Java语言提供类、接口和继承等原语，为了简单起见， 只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关 键字为implements ）。Java语言全面支持动态绑定，而C+胡言只对虚函数使用动态绑定。 总之，Java语言是一个纯的面向对象程序设计语言。Java语言是分布式的。Java语言支持Internet应用的开发，在基本的Java应用编程 接口中有一个网络应用编程接口（ java net ）,它提供了用于网络应用编

24、程的类库，包括 URL URLConnection、Socket ServerSocket 等。Java 的 RMI （远程方法激活）机制也是 开发分布式应用的重要手段。Java语言是健壮的。Java的强类型机制、异常处理、垃圾的自动收集等是 Java程序 健壮性的重要保证。对指针的丢弃是Java的明智选择。Java的安全检查机制使得Java更 具健壮性。Java语言是安全的。Java通常被用在网络环境中，为此，Java提供了一个安全机制 以防恶意代码的攻击。除了 Java语言具有的许多安全特性以外，Java对通过网络下载的 类具有一个安全防范机制（类 ClassLoader）,如分配不同的名

25、字空间以防替代本地的同 名类、字节代码检查，并提供安全管理机制（类 SecurityManager ）让Java应用设置安全 哨兵。Java语言是体系结构中立的。Java程序（后缀为java的文件）在Java平台上被编译 为体系结构中立的字节码格式（后缀为 class的文件），然后可以在实现这个 Java平台 的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。Java语言是解释型的。如前所述，Java程序在Java平台上被编译为字节码格式，然 后可以在实现这个Java平台的任何系统中运行。在运行时，Java平台中的Java解释器对 这些字节码进行解释执行，执行过程中需要的类在联接阶段

26、被载入到运行环境中。Java是性能略高的。与那些解释型的高级脚本语言相比，Java的性能还是较优的。Java语言是原生支持多线程的。在 Java语言中，线程是一种特殊的对象，它必须由Thread类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为 Thread（Runnable）的构造子将一个实现了 Runnable接口的对象包装成一个线程，其二， 从Thread类派生出子类并重写run方法，使用该子类创建的对象即为线程。值得注意的 是Thread类已经实现了 Runnable接口，因此，任何一个线程均有它的 run方法，而run 方法中包含了线程所要运行的代码。线程的活动由一组

27、方法来控制。Java语言支持多个线 程的同时执行，并提供多线程之间的同步机制（关键字为synchronized ）。Java语言是动态的。Java语言的设计目标之一是适应于动态变化的环境。Java程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于 软件的升级。另外，Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。Java语言的优良特性使得Java应用具有无比的健壮性和可靠性，这也减少了应用系 统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开 发时间并降低成本。Java的编译一次，到处可运行的特性使得它能够提供一

28、个随处可用的 开放结构和在多平台之间传递信息的低成本方式。特别是Java企业应用编程接口（ JavaEnterprise APIs ）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。java图形化编程的知识java的GUI编程（Graphic User Interface ,图形用户接口），是在它的抽象窗口工 具箱（Abstract WindowToolkit , AWT上实现的，java.awt是AWT勺工具类库，其中包 括了丰富的图形、用户界面元件和布局管理器的支持。GUI主要用在两个地方：Application ； Applet。GUI界面：用户与程序之间交互的一个控制面板，具内

29、包含有菜单，控件（或组件），容器并能 响应用户的事件。现在有各种各样的窗口系统，不同的窗口系统提供给程序设计的程序库是大不一样的， 例如，基于 Windows的SDK和基于Unix平台的X Windows的Xlib。为了使程序能在不同的窗口系统下运行，Java提出了 “抽象窗口系统”的概念，提供 了 AWT（抽象窗口工具箱），使得java能够在不同的窗口系统下运行。Java中的GUI实现方式：采用AWT（抽象窗口工具集）从而可使 GUI适用于不同OS的环境。特点如下：其具体实现由目标平台下的 OS来解释，从而导致Java GUI在不同平台下会出现不 同的运行效果（窗口外观、字体等的显示效果会发

30、生变化）。 组件在设计时不应采用绝对定位，而应采用布局管理器来实现相对定位，以达到与平台及设备无关。3）新增的Swing GUI组件AWffi件以及事件响应不及微软的 SDK富（因为有些OS平台无彳软的Window却件）， Sun在Java2中新增了 Swing GUI组件。但是，AWT:匕较简单，功能也能满足大多数界面 需求，特别在Java Applet的设计中受到了普遍的应用。任务概述本次课程设计的题目是“ A星算法的演示系统”，A*算法在人工智能中是一种典型的 启发式搜索算法，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。 常用于游戏中的NPC勺移动计算，或在线游戏的B

31、OTB移动计算上。本次课程设计要求能够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓 演示出来。实现了设置起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、 重新寻路、添加默认障碍这些功能的操作。运行环境规定任何安装java运行环境的系统1：在eclipse中加载该项目，直接打开并运行该项目。2：安装java运行环境的机器中，控制台下，进入bin目录，输入java .java13:安装java运行环境的机器中，直接运行已经打包好的axing.jar其他A星软件的优劣(1)软件图1.2 C#完成的A*算法的演示程序这个程序的好处就是实现的功能很全。优

32、点：(1)对于障碍的不同级别，进行了设置，表现在程序上我觉得就是障碍的加权值的不 同，而且在实际的执行过程中也可以越过一些障碍。(2)时间的延迟进行了设置，对于程序的演示效果能有更好的展现。(3)方格的大小也进行了设置，可以进行随便的调节，也是为了方便展示。缺点：(1)功能过于复杂，初次拿到软件的人会先进行一段时间的熟悉，不适合激发初学A星算法的人的兴趣。(2)文字说明多，也是其复杂原因的一种，如果用图形化的方式进行更多的说明会事 半功倍。(2)软件二这个软件演示的很清晰，说明很到位，没有实现动态执行的功能。优点：该有的功能一般都有了，操作起来并不复杂，演示效果很好，图形化的执行很不错。缺点：

33、每次执行都要全屏展示，在我的电脑上如果一旦按 WINDOWS进行其他操作，在打开 此程序，发现看不到之前的执行路径了。基于上面的研究成果，我本次使用JAVA语言写的A星算法演示程序，争取尽可能的简 单易操作。2概要设计界面设计软件的进入界面设计图2.1软件的进入界面软件的进入界面的分析一般软件都有自己的进入界面，软件的进入界面能够使软件更富有意义，界面设 计是为了满足软件专业化标准化的需求而产生的对软件的使用界面进行美化优化规范化 的设计分支。(2)此界面大小长950像素，宽710像素，能够满足大部分计算机的整个屏幕的显示， 跟程序的主体界面大小一致。图形的显示位置在 x=30, y=10的位

34、置。“AStar算法演示软 件”几个字采用70号字，总体加粗。作者和姓名及“进入演示程序”字体采用40号，Font _LAYOUT _NO _LIMIT_CONTE笳。(3)整个框架是外面的 MyFace包含FacePanel ,左右图形的绘制通过 FacePanel中 的paint函数实现。(4)背景是宇宙，有很多的星星，周围放出万丈光芒，宇宙能够给人以无限的想象， 此处希望本程序的演示也能给使用者以无限的想象。蓝色的光线是从两边的中心位置依次 向上面和下面画线，下面的间距为 30个像素，这样的设计能够突出中间文字的显示效果。(5)此处星星的设计和程序的名称有相对应的地方，星星的绘制是通过在

35、界面的区域 内随机产生450个三种颜色的点来显示的。(6)当点击“进入程序演示”就会启动一个线程执行显示程序主体界面的程序，同时 本界面会隐藏。软件主题界面的设计图2.2软件主体界面软件主体界面的分析(1)整个FRAM的大小，长950像素，宽710像素，内包含两个Panel,顶层的Panel 包含4个JRadioButton ,分别是“设置起点”、“设置终点”、“设置障碍”，“清除障 碍”。下面的Panel是自定义的，包含左边的方块区域和右边的说明区域，方块区域的长 700像素，宽600像素。(2)小方块的边长为50,整个区域长14个方块，高12个方块。之所以这几这么大 小，是因为，这样的大小

36、基本适合13寸以上的电脑能够在整个屏幕内演示，能够满足大 部分使用此软件的人员的要求。(3) JRadioButton刚开始默认选定是设置障碍，可以通过点击其他的单选按钮，进 行相应的操作。当点击其他的单选按钮后，鼠标对下面方框区域的操作与其对应。(4)右边说明的主题意思是通过方块颜色的不同来区分起始结点，终止结点，CLOSE中的节点，OPEW的节点等。另外箭头指向启发式寻路过程中的每个节点的前驱。2.2程序需要实现的功能1:设置起点2:设置终点3:设置障碍4:消除障碍5:直接寻路（点击按钮就显示出最后的寻路结果）6:单步寻路（通过不断的点击按钮，一步一步显示出程序的寻路过程）7:动态寻路8:

37、重新寻路9:添加默认障碍3.1类图的设计ni 二 I.nte=r sy： Integeri2ntsist H: Intsfitr F:IntiE*r H*ca3tFTMi; String sdirect:Znteger kf1ag:integaTaca-j.cT : LnliziLted2.3详细设计KxingT-alhH 7 Integer-CHth:integET *otartx 二nte.&r startT：Inteear-&ndT：工nt号彳工-pr ice 二Integer= zzDirect _j lUhIlei_ . .-te-pG 二：ntBETHisSetter:Boolea

38、n心噎h： lAjiftENdsvcloi#List :Axir：ffN&dtk*pwnL 己 5t 二 RxfngXodeAxins-fiad3mFAfunStep,horPath-gap:Integer size 二lEteaST* 二三工匚he :Zntegex iFrcsr：:ntsger vuinE：Axini HE.M：UnlEz3Wt看, 仁二 1 二 r 7 er ;UiB.,jpliUnlioitt., =W1 ：X?Panel-jrbl :Unl isit. tS jr b2: Uni lz：lt . cjrbl .Ud imt. jblfUnli.aite . wjfc2

39、：Unl:aite . wjb3：rnLiHitE.-Jc4: Unlisite. e jc 52 tinliniite.,Unliziiti&d. wcolcr lUiliffii.u . *ch.&n.E-Dnt#&r -fag an 二1 nt 仔8丁 IFrame fL earl is t *5 tit&ck *zBDU.sFre Ad itjKttStat tCha. KtionPETf-Tsed *run图3.1 A星算法演示软件的类图3.2类之间的关系说明(1)继承关系：继承指的是一个类(称为子类、子接口)继承另外的一个类(称为父 类、父接口)的功能，并可以增加它自己的新功能的能

40、力。在 Java中继承关系通过关键 字extends明确标识，在设计时一般没有争议性。在 UM送图设计中，继承用一条带空心 三角箭头的实线表示，从子类指向父类，或者子接口指向父接口。(2)实现关系：实现指的是一个class类实现interface 接口(可以是多个)的功能, 实现是类与接口之间最常见的关系。在Java中此类关系通过关键字implements明确标识， 在设计时一般没有争议性。在 UMLfe图设计中，实现用一条带空心三角箭头的虚线表示， 从类指向实现的接口。(3)依赖关系：简单的理解，依赖就是一个类 A使用到了另一个类B,而这种使用关 系是具有偶然性的、临时性的、非常弱的，但是类

41、 B的变化会影响到类A。比如某人要过 河，需要借用一条船，此时人与船之间的关系就是依赖。表现在代码层面，为类 B作为参 数被类A在某个method方法中使用。在UM改图设计中，依赖关系用由类 A指向类B的 带箭头虚线表示。(4)关联关系：关联体现的是两个类之间语义级别的一种强依赖关系，比如我和我的 朋友，这种关系比依赖更强、不存在依赖关系的偶然性、关系也不是临时性的，一般是长 期性的，而且双方的关系一般是平等的。关联可以是单向、双向的。表现在代码层面，为 被关联类B以类的属性形式出现在关联类 A中，也可能是关联类A引用了一个类型为被关 联类B的全局变量。在UM送图设计中，关联关系用由关联类 A

42、指向被关联类B的带箭头 实线表示，在关联的两端可以标注关联双方的角色和多重性标记。(5)聚合关系：聚合是关联关系的一种特例，它体现的是整体与部分的关系，即has-a 的关系。此时整体与部分之间是可分离的，它们可以具有各自的生命周期，部分可以属于 多个整体对象，也可以为多个整体对象共享。比如计算机与CPU公司与员工的关系等，比如一个航母编队包括海空母舰、驱护舰艇、舰载飞机及核动力攻击潜艇等。表现在代码 层面，和关联关系是一致的，只能从语义级别来区分。在UMLfe图设计中，聚合关系以空心菱形加实线箭头表小0(6)组合关系：组合也是关联关系白一种特例，它体现的是一种contains-a的关系，这种关

43、系比聚合更强，也称为强聚合。它同样体现整体与部分间的关系，但此时整体与部 分是不可分的，整体的生命周期结束也就意味着部分的生命周期结束，比如人和人的大脑。表现在代码层面，和关联关系是一致的，只能从语义级别来区分。在UML1图设计中，组合关系以实心菱形加实线箭头表示。3.3类图的分析(1)类图(Class diagram)是显示了模型的静态结构，特别是模型中存在的类、类的 内部结构以及它们与其他类的关系等，一般在详细设计过程中出现，主要用来描述系统中 各个模块中类之间的关系，包括类或者类与接口的继承关系，类之间的依赖、聚合等关系。(2)此次的A*算法演示程序共用到了 7个类，此7个类的关系相对比

44、较简单，有依 赖关系和聚合关系组成。java1类是程序的入口点，包含程序需的 main函数，main函数产生了界面类的 对象。进而界面类会调用界面类包含的 Panel类的paint函数，绘制出软件的进入界面。软件的进入界面类对应 MyFace类,MyFace类包含FacePanel类的对象，此界面 的绘图操作是通过FacePanel类的paint函数来绘制的，(见上面的图2.1软件的进入界 面)当点击”进入演示程序”按钮之后，会启动一个线程，此线程会产生MyFram酸的对象。MyFram嵌是程序的主题界面显示的类，如图 2.2软件主体界面，此类包含两个 Panel,顶层的Panel包含单选按钮

45、和按钮，底层的 Panel包含图形的绘制主体方块和说 明信息。MyPanel是自己定义的JPanel,它继承自JPanel,这个类主要是画出主体方块 区域和现实说明信息。Axing类用来设计整个A星算法，其中包含图形的起始坐标，终止坐标，每走一 步的带权值，以及最重要的 A星算法的实现代码等。AxingNode类是程序的结点类，它设计了程序的结点，因为A星算法要用到两个链表，链表的结点类型就是 AxingNode类型，每个节点都包含自己在方块区域的坐标，GH、F值，指向前驱的字符串，direct用来指示cameFromfl勺方向，flag用来标记每个结点 的类型，0:起始点1:障碍2:目标点3

46、:其他，还有颜色值。3.4程序的实现程序逻辑的设计我此处用了两个链表：OpenList初始化时存放起始结点，用来存放还为探测的结点。CloseList初始化为空，用来存放已经探测过得结点。整个图的结点用一个 AxingNode型数组来存放因为A星算法需要进行启发式寻路，我采用的启发式寻路的方式为当前结点与目标结 点的横纵坐标的和作为启发寻路的启发 H值，G值为前驱结点到起始结点的权值加上前驱 结点到本结点的权值。F=G+H乍为总权值。每次比较就是按照 F值进行的比较。F = G + HG=从起点沿着产生的路径，移动到网格上指定方格的移动耗费。H=从网格上那个方格移动到终点 B的预估移动耗费。正

47、如上面所说，G表示沿路径从起点到当前点的移动耗费。在这个例子里，我们令水 平或者垂直移动的耗费为10。既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它的前驱结点的G值，然后依照它相对前驱结点直角方向（非对角线），增加和10。例子中这个方法的需求 会变得更多，因为我们从起点方格以外获取了不止一个方格。H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前 格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以10。这被成为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数，在 那里你不能沿对角线方向穿过街区。很重要的一点，我们

48、忽略了一切障碍物。这是对剩余 距离的一个估算，而非实际值，这也是这一方法被称为启发式的原因。F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。 F,G和H的评分被 写在每个方格里。正如在紧挨起始格右侧的方格所表示的，F被打印在左上角，G在左下角，H则在右下角。具体算法的寻路思路如下：（1）将从起始点开始，方块添加到 open列表中，该列表有最小的和值。且将这个方 块称为S吧。（2）将S从open列表移除，然后添加S到closed列表中。（3）对于与S相邻的每一块可通行的方块 T:（这里我问题只要有上下左右可以通行）1）如果T为终止结点，则结束。2）如果T在closed列表中：不管它。

49、3）如果T不在open列表中：添加它然后计算出它的和值，并标记S为他的前驱。4）如果T已经在open列表中：当我们使用当前生成的路径到达那里时计算新 F值，检查新F值与原有F值相比是否更小。如果是，更新它的 F值和它的前驱。5)继续扫描open列表中拥有最小的F值的结点，记为S,重复(3)/A星算法的具体代码如下public boolean Afun()(while(!openList.isEmpty() (AxingNode tempNode=openList.get(findMinF(openList); if(tempNode.flag=2)/如果是最后一个结点(pathstartxst

50、arty.F=pathendxendy.F;pathstartxstarty.H=pathendxendy.G; return true;/能够到达最后的结点openList.remove(tempNode);closeList.add(tempNode);/另外添加，对于openList,closeList中的结点的颜色进行设置if(tempNode.flag!=0)/如果不是开始结点(tempNode.color=Color.cyan;/蓝绿色标志为进入 closeList 中的结点。/对于刚加入closeList即刚从openList中删除的结点，看其周围的结占 八LinkedList

51、neighborNodes=new LinkedList();if(tempNode.x0&pathtempNode.x-1tempNode.y.flag!=1&!closeList.contai ns(pathtempNode.x-1tempNode.y)/ 左 (如果openList不包含周围的结点，即周围的结点并没有提前在 openList中，那么可以更改directif(!openList.contains(pathtempNode.x-1tempNode.y)(pathtempNode.x-1tempNode.y.direct=1;/neighborNodes加入的顺序是“左右上下”

52、，这个顺序随意neighborNodes.add(pathtempNode.x-1tempNode.y);if(tempNode.x0&pathtempNode.xtempNode.y-1.flag!=1&!closeList.contai ns(pathtempNode.xtempNode.y-1)/ 上 if(!openList.contains(pathtempNode.xtempNode.y-1) pathtempNode.xtempNode.y-1.direct=3; neighborNodes.add(pathtempNode.xtempNode.y-1); if(tempNode

53、.y11&pathtempNode.xtempNode.y+1.flag!=1&!closeList.conta ins(pathtempNode.xtempNode.y+1)/ 下 if(!openList.contains(pathtempNode.xtempNode.y+1) pathtempNode.xtempNode.y+1.direct=2; neighborNodes.add(pathtempNode.xtempNode.y+1); isBetter=false;/ 很重要，防止之前的 for(i=0;ineighborNodes.size();i+) /if(closeList

54、.contains(neighborNodes.get(i)/continue;/中的/tempNode 是从openList中取出的最小的，刚加入 closeList 结点/tempG指按照这个结点计算出的四周的结点的G值tempG=pathtempNode.xtempNode.y.G+price;/从起点至 Uneighbor的G距离if(!openList.contains(neighborNodes.get(i) openList.add(neighborNodes.get(i);isBetter=true;else if(tempGneighborNodes.get(i).G)/op

55、enList 之前已经包含neighborNode结点，但是按照当前的结 点计算tempG会更小一些if(neighborNodes.get(i).xtempNode.x) neighborNodes.get(i).direct=0;if(neighborNodes.get(i).ytempNode.y) neighborNodes.get(i).direct=2;if(neighborNodes.get(i).ytempNode.y) neighborNodes.get(i).direct=3; isBetter=true; else isBetter=false; if(isBetter)

56、 邻居节点X小于当前指向左指向上指向下neighborNodes.get(i).cameFrom=Character.toString(szDirectneighborNodes.ge t(i).direct);neighborNodes.get(i).G=tempG;neighborNodes.get(i).H=(Math.abs(endx-neighborNodes.get(i).x)+Math.abs(end y-neighborNodes.get(i).y)*price;neighborNodes.get(i).F=neighborNodes.get(i).G+neighborNode

57、s.get(i).H;if(neighborNodes.get(i).flag!=2)/如果不是终止结点 neighborNodes.get(i).color=Color.blue;/蓝色设置为加入openList中的结点的颜色 /end for(neighbor) /end while return false; 代码说明： 代码中的path是相对于主体界面(图2.2软件主体界面)桔黄色寻路区域的二维数 组代码表示，是AXingNode类型的结点。 neighboeNodes也是AXingNode类型的链表的表示。用来存饭每次要进行拓展的当前 结点的可以进行再探测的结点。 总体的执行思路就是

58、按照上面给出的执行逻辑进行的编码。3.3.2找到link中结点的F值最小的结点/找到link中结点的F值最小的结点的下标(最后探测到的) /从后向前扫描，找到最前面的最小的F的结点的下标，返回注意探测的链表因为下标从0开始都是数据，所以使用前一定要判断链表不为空才 行！ ！ ！public int findMinF(LinkedList link) int i,minF,index=0;minF=link.get(0).F;/从前向后扫描，找到最小的那个 F的下标，如果几个相同的下标， /取最后面的最小的那个，这样可以以最快的方式到达目标结点 for(i=1;ilink.size();i+)

59、if(link.get(i).F=minF)/*如果此处没有=,那么会去最前面的最小的结点，会探测一些无用的点。 index=i;minF=link.get(i).F;)return index;/返回下标探测结果如下:图3.2 FindMin 加上“=”的执行效果图如果/*处的 =改成 ,代码如下：public int findMinF(LinkedList link)int i,minF,index=0;minF=link.get(0).F;for(i=1;ilink.size();i+)if(link.get(i).FminF)/* 此处没有=index=i;minF=link.get(

60、i).F;return index;/ 返回下标)对于相同的障碍，结果如下:图3.3 FindMin 不加上“=”的执行效果图很明显，后面的情况会探测很多无用功的结点。通过此函数的演示效果，可以说明不同的最小值选取防止对于程序的执行结果优化程 度是不同的，这里之所以选取从前向后最后探测到的那个最小的结点作为继续探测的最小 的结点，是因为(1)每次探测结点都是在链表后面进行插入。(2)每次探测我们做的选择都是目前最优的选择， 及选择最接近目标结点的那个结点 进行探测。(3)因为我的启发式搜索的H的计算采用的是通过当前结点和目标结点横纵坐标的绝 对值之差相加。所有不算是最精确的启发式寻路，寻路过程