本科生毕业设计论文基于a算法的路径寻找

本科生毕业设计论文基于a算法的路径寻找内容摘要：

FS） BFS 算法试图找出一点与最初始的点最接近在一 层内，但是他不会连续两次访问同一个节点。 他的最好的情况为 o(bd)，最差的情况为 o(bd)此处 b树的广度， d树的深度。 这个算法的好处是他一定可以找出一个解，并且解出步数将会小于 DFS 的步数，因为对于树来说，深度往往要比树的广度要打，但是这一算法将会大量的耗费内存，他会将他所有的可能的节点全部保存下来，因此他在算法效率上十分的笨重。 BFS 算法倾向于使用队列作为他的数据处理方式。 深度优先搜寻 （ DFS） DFS 算法与 BFS 的区别就是他将会对每个节点子节点优先进行搜索，这将会对具有很大广度的树来说更加 有效率，它最好的情况为 o(b*d)最坏的情况为 o(bd)。 此处 b树的广度， d树的深度。 DFS 对于某些特殊的情况更加使用，因此它的使用范围相对 BFS小点，但是它的优势就是 BFS 就会使用 bd个空间用于存储节点，而 DFS 不会，它将大大节省空间。 DFS 更加倾向于使用堆债作为他的数据的处理方式。 A*算法 以上两种算法 BFS 肯定能找出答案，但是他会耗费大量的资源， DFS 虽然效率更好但是他只是用某些特殊的情况，而且他有可能会在一个局部内死循环，从而得出一个局部的最优解，而不是全局的最优解。 这里引入 A*算 法， A*算法更加的智能它引入了一个估价函数的机制，从而避免了局部最优解的局面。 *的意思是他比起普通的算法更加的优化。 对于 A 算法来说，他不会比较估价函数的值，而 A*算法则会比较他们之间的值，从而得出最好接，这就会将局部以外的可能更优的节点加入到搜索的过程中。 这个函数式为 f*(n)=g*(n)+h*(n)，最重要的是找出 h*(n)的值如果无法计算出一个好的值，那么他的效率将会和上面说到算法一样低下，因此它最好的情况是 O(b*d)最差的情况是 O(bd)。 此处 g*(n)不是重点的原因是因为在其他的位置可能存在更好 的解，这就会防止局部最优解的产生。 基于 A*算法的路径寻找 8 A*搜寻算法， 他可以应用在具有多个不同节点的路径的图上，同时求出一个最短路径的算法。 它的最常见的应用是在游戏中 NPC 的移动方面，或者是在网络游戏中 BOT 的移动计算方面。 上文中提到 该算法像 与 Dijkstra 算法 的原理基本一致 ， 目的是为找出一条最短的路径 ； 同时他 也像 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)的值越来 越小 的时候 ， 他所涉及到的 需要计算的节点 数目将会 越多，此时的 算法效率 将会低下。 比如当应用到几何型的网络中时， 可以取两节点间 直线距离（即是欧几 理德距离 ）做为 节点的 估价值，即 f=g(n)+sqrt((dxnx)*(dxnx)+(dyny)*(dyny))； 这样的话受到估价值 h的影响个，在 g值一定的情况下估价函数 f 会受到 h 的约束 ， f的值越小 就意味着 h的值也小，同时表示这个节点距离目标点就越近 ， 这样话就是表示搜索到的每一个点就会产生一条最短路径。 而这点 明显 和 Dijstra 算法 在点四周漫无目的的以枚举的方式进行寻找就好很多，因为他对每个点进行了预判剔除了不必要的点，极大地提高了效率。 这里需要提到 h（ n）的一个属性他被称为信息性，他的意思是在估算 一个节点的估价值的时候的约束条件， 当一个节点的约束条件越多或者说他的信息性越多的话，他被剔除的可能性就越大，这样大量不需要计算的节点就会被排除，所以我们就可以说这个估价函数很好或者是这个算法更加优秀。 这个特性使得它比广度优先算法优秀很多，因为他的 h(n)为 0，换句话就是它不具有信息性即启发性信息。 但是在路径搜索的过程中，他往往要求了很高的实时性， h(n)的信息性越强，他的要求的计算量就会相对上升，使得他耗费的时间也就会越大。 此时为了满足他的实时性，我们必须在一定程度上减少的h(n)的信息性 ，即减少节点的约束 性的条件。 但是他付出的代价就是准确性会降低，这就是一个我们需要权衡的问题。 简化的 A*算法流程： 搜索区域被划分成了方形网格。 简化搜索区域，是寻路的第一步。 这一方法把搜索区域简化成了一个二维数组。 数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。 路径被描述为从 A到 B我们经过的方块的集合。 一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。 基于 A*算法的路径寻找 9 ，他会将其周围待处理的节点放入一个列表中。 一开始只有一个，即是起点，但是之后就会多起来。 表格内包含待检查的方格。 找起点周围可到达的一切可通过的方格，放弃不可通过的方格。 把这些可行的方格加入到列表中。 为这些方格保存点 A 为这些方格的父方格。 父方格很重要类，类似于树中的父节点。 A，将其加入另一个表（称为关闭列表），这个列表中保存所有不需要再次检查的方格。 接着重复以上步骤，找出每个可行的方格的表和关闭列表。 类似于一棵树，寻找他的最小的路径。 选择路径中经过哪个方格的关键是下面这个等式： F=G+H *G=从起点 A，沿着产生的路径，移动到网格上指定方格的移动耗费。 *H=从网格上那个方格移动到终点 B 的预估移 动耗费。 这经常被称为启发式的 ， H的值将会是不定的。 此为最简单的方式。 既然我们在计算沿特定路径通往某个方格的 G值，求值的方法就是取它父节点的 G 值，然后依照它相对父节点是对角线方向或者直角方向 (非对角线 )，分别增加和。 例子中这个方法的需求会变得更多，因为我们从起点方格以外获取了不止一个方格。 H值可以用不同的方法估算。 我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向，然后把结果乘以 10。 这被称为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的 街区数，在那里你不能沿对角线方向穿过街区。 很重要的一点，我们忽略了一切障碍物。 这是对剩余距离的一个估算，而非实际值，这也是这一方法被称为启发式的原因。 想知道更多。 你可以在这里找到方程和额外的注解。 F的值是 G和 H的和。 第一步搜索的结果可以在下面的图表中看到。 F,G 和 H 的评分被写在每个方格里。 正如在紧挨起始格右侧的方格所表示的， F被打印在左上角， G在左下角， H 则在右下角。 为了继续搜索，我们简单的从开启列表中选择 F值最低的方格。 然后，对选中的方格做如下处理： 4，把它从开启列表中删除，然后添加到关闭列表中。 5，检查所有相邻格子。 跳过那些已经在关闭列表中的或者不可通过的 (有墙，水的地形，或者其他无法通过的地形 )，把他们添加进开启列表，如果他们还不在里面的话。 把选中的方格作为新的方格的父节点。 6，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。 换句话说，检查如果我们用新的路径到达它的话， G 值是否会更低一些。 如果不是，那就什么都不做。 基于 A*算法的路径寻找 10 以上就是 A*算法的主要的过程，但是无法体现估价函数重要的价值。 为了更加明了的解释这格的重要性，我将用华容道作为例子来解释他的重要性。 有一个 3*3的方格 8 1 3 4 5 2 7 6 他最终的目的是变成 1 2 3 8 4 7 6 5 他将会使用两种不动估价函数，在附录中将会有这两种情况的图片 使用了两种不同的估价函数 f(n)good 和 f(n)weak 都最终得到了结果但是 f(n)good的估价函数效率更加高。 我们通过更加深入的观察这些过程可以了解到为何 f(n)weak 用了更多的步数才得到了结果，从一开始，搜索的步骤直接导向了有最终结果的那个分支。 但是在 f(n)weak 达到这个路径之前他多使用了 4 步才搜索到了这个具有最终解的分支。 并且 f(n)good 三个子节点的估价值远远高于 f(n)weak的估价值是的结果更加具有了区分度，更加容易得出具有答案的分支。 再设计 f(n)函数的时候， h(n)必须谨慎的设计，如果随意设置就会导致算法效率及其的低下。 h(n)的值可以根据不同的应用的场景特殊设计。 基于 A*算法的路径寻找 11 4 A*算法 仿真系统设计 路径寻址系统概述 建立一个可以自由画障碍物的程序，在起点到终点的过程中可以绕过障碍物。 寻找一个最优的路径。 并且可以保存及加载路径，一边可以用相互之间的比较。 对用户界面进行模块设计 主窗口界面 使用 JAVA 的 SWING 技术搭建一个 UI 界面 主要的程序入口为 AStarDemo 文件，他会负责加载各个窗体的组建 AstarPanelastarPanel = newAstarPanel(15,15,60,40)。 StatusPanelstatusPanel = newStatusPanel()。 (statusPanel)。 (newAStarMenuBar(astarPanel))。 ().add(new ControlPanel(astarPanel), )。 (true)。 ()。 以上代码将 astarPanel， statusPanel， AStarMenuBar， ControlPanel 等相关的组建加入到 UI 中。 绘画过程代码 astarPanel 作用是最主要他负责在界面上画出障碍物 和画出计算出的路径 ，使得A*算法画出他算出的路径。 并且可以显示出每个节点的相应的坐标。 (x, y , width, height, arc, arc)。 (TIPS_COMPOSITE2)。 (TIPS_FG)。 (Current grid num : ( + ().x + , + ().y + ), x + 15, y + 15)。 ()。 其上为显示坐标的代码 基于 A*算法的路径寻找 12 在 60*40的表格而每个节点的大小为 15pix*15pix的背景。 publicvoidpaintComponent(Graphics g) { (g)。 fillBarrier(g)。 fillTargetAndSourceGrid(g)。 fillOpenList(g)。 fillAStarPath(g)。 fillDrawData(g)。 drawGridLine(g)。 drawTips(g)。 } 以上代码的绘画逻辑是 ： 图 绘画代码逻辑 工具栏代码 AStarMenuBar 的作用是显示菜单栏，它的基本显示的代码： enumMainMenu{ File(File, 39。 F39。 ), View(View, 39。 V39。 ), Help(Help, 39。 H39。 )。 基于 A*算法的路径寻找 13 publicSubMenu[] getSubMenus() { if(subMenus==null){ ListSubMenutmp = newLinkedListSubMenu()。 for(SubMenusubMenu : ()){ if(()==this){ (subMenu)。 } } subMenus = newSubMenu[()]。 subMenus = (subMenus)。 } returnsubMenus。 } } 他有三个主菜单组成使用， getSubMenus()方法得到下层的菜单。 ControlPanel 的作用是实现界面上的三个按钮通过调用不同的函数实现功能，三个函数是 : startFind()这是算法开始的入口，是最重要的函数他将调用他的一个 find()方法实现他的路径搜索。 clearPath()清理路径 clearMap(。