智能导航系统设计

中国科学技术大学本科论文目录目录第一章绪论111论文研究背景112论文内容安排2第二章最短路径问题概述321前言322最短路径问题的定义323几类搜索算法思想4231盲找BLINDSEARCH4232DIJKASTRA算法6233最好优先算法BESTFIRSTSEARCH，简称BFS7234A算法7第三章A算法1031A算法,图搜索策略，人工智能产生系统搜索策略1032图搜索策略11321图论术语11322图搜索一般过程13323无知搜索UNINFORMEDGRAPHSEARCH和启发式搜索HEURISTICGRAPHSEARCH14324评价函数15325启发式函数1633A算法17331A算法17332A算法的可采纳性ADMISSIBILITY18333A算法的比较COMPARISON20334A算法的单调约束MONOTONERESTRICTION21335预估函数的启发能力2334相关算法24341双向搜索BIDIRECTIONALSEARCH24342分阶段搜索STAGEDSEARCH24第四章A算法的典型实现2541前言25I中国科学技术大学本科论文目录42A算法的典型实现25421ASTARPATHFINDER类描述26422ASTARPATHFINDER类部分实现，及与矢量地图结构的联系分析2843矢量地图中使用A算法35431矢量地图中的问题35432矢量地图上的A算法流程37第五章优先队列的实现4051前言4052有序链表SORTEDLISTS4153优先树PTREES，或PRIORITYTREES4354二叉树45541左树LEFTISTTREES45542二叉优先队列46543二叉搜索树优先队列47544堆48545多级桶MULTILEVELBUCKETS50546HOT队列52第六章总结与展望5461工作的重要性5462论文工作总结5463论文的现实意义5564工作展望55II中国科学技术大学本科论文第一章绪论第一章绪论11论文研究背景科大GPS实验室从1993年开始研究全球卫星定位系统在监控及导航方面的应用，由最早的简易便携的GPS接受装置到船用导航仪，由单机车辆导航系统到基于局域网的车辆监控系统。1998年四月，GPS实验室开始转向结合矢量地图的智能车辆导航系统，并在笔记本电脑上完成了导航系统的原型开发。1999年元月，开始尝试将现有的原型移植到掌上电脑WINDOWSCE系统。智能导航系统设计的最初想法，就是实现复杂交通情况下，移动车辆的协助导航，即出发点和目标点已知，结合矢量地图，找出最短的路径，并结合GPS的实时信号，为移动车辆提供当前的位置信息，以及转向提示。另外一个想法是，当前的监控系统仍然停留在车辆的被动监视的层次上，如何让一定目标自身具备“智能”，了解自己的位置以及协助其它的移动目标完成整体协作工作，这个在警用监控系统中用于移动目标的整体协作工作非常重要。以上的两个想法提出了一个问题，如何在当前的矢量地图上实现有效的路径寻优算法于是在开发的原型中，我们实现一个简单的路径寻优算法，并且满足了当时的单源点路径优化的要求。但是最初的实现部份存在一些问题1）采用的算法到底应该归属于网络规划的那个子问题之下，此类算法在人工智能研究领域有没有成熟的理论可以参考，算法有没有成熟的理论框架指导；2）当前的算法在实时要求很好的情况下，能不能胜任，即算法的时间复杂度和空间复杂度，是不是可接受的；那么算法的复杂度由那些因素制约；3）如何克服制约因素，采用高效的数据结构即文中谈论的实现优先队列的数据结构完成算法的设计。本篇论文就是围绕上述三个方面展开讨论，并尝试一些实现，为GPS实验室在自主开发矢量地图的基础上研究最短路径等网络规划问题起个抛砖引玉的作用。1中国科学技术大学本科论文第一章绪论另外一个值得关注的事实是，美国政府已经于2000年五月一日晚上八时，取消了在卫星信号中人为降低定位精度的SA政策，民用定位精度已经达到10米，较以前提高了10倍，这无疑将推动GPS导航系统的研究开发，从这个意义上看，研究高效实时的最短路径等网络规划问题，前景乐观。以前我们的系统为了克服这种人为的误差，采用KALMAN滤波理论取得了一定的效果。现在精度提高结合现有的修正算法，GPS实验室会说“我们的地图精度比以前提高了，我们的导航系统向大规模推广又近了一大步，GPS实验室的前景将随同GPS技术广泛的应用，敞亮起来了”12论文内容安排第一章绪论介绍论文研究背景，以及整篇论文安排。第二章最短路径问题概述简单介绍最短路径问题，分析几类搜索算法思想。第三章A算法介绍图搜索策略，人工智能产生系统搜索策略。仔细分析了A算法及其可采纳性，单调约束等内容。第四章A算法的典型实现阐述A算法的典型实现，提出矢量地图中的一些问题以及A算法在矢量地图中的具体实现。第五章优化队列的实现提出优化A算法可使用的几种复杂数据结构有序链表，二叉树中的左树，二叉优先队列，堆，多级桶以及HOT（HEAPONTOP）队列等。并分析了他们的一些重要操作。第六章总结与展望总结论文内容，提出发展前景。2中国科学技术大学本科论文第二章最短路径问题概述第二章最短路径问题概述21前言在地图上确定最优的行走路线是一个有趣的问题。有很多不同的实现方法，最简单的思想是，“一直往前走，直到发现障碍为止”；较复杂的思想是，“采用启发式的路径寻找方法”。路径寻优算法的研究隶属人工智能的研究范畴，尤其在模拟人类智能的电子游戏的编写中，得到广泛应用。在一个半稀疏的稠密网格中，我们可能会采用所谓的“A算法”，这个算法最根本的特点就是，“总可以找到最短路径”；如果实现一个稠密网格结构，比如迷宫问题，我们往往寻找迷宫问题的解决办法，其中有很多不同的方法，比如距离表格法DISTANCETABLE，路由表格ROUTINGTABLE，深度优先搜索法DEPTHFIRSTSEARCH,宽度优先搜索法BREADTHFIRSTSEARCH。当面对一个实际问题时，并不存在一个清晰的界线划分半稀疏与稠密网格，从而也不可能完全肯定地说出什么方法一定好，什么方法一定很差，通常总是从中选取一种或几种方法结合起来应用。22最短路径问题的定义最短路径问题PATHFINDINGORSHORTESTPATHALGORITHMS是一种计算机图形搜索算法，在出发点和目标点之间找出总代价最低的路径。大多数算法解决的是网格数据，通常称为MAPS，它存储了每个节点的代价，见图21。算法一方面要完成沿网格探索最低代价的路径，见图22，另一方面要做到尽可能快，尽可能少占用内存，即尽可能降低算法的时间复杂度和空间复杂度。这里给出单源点最短路径问题的定义。单源点最短路径问题的输入是G，S，L,有向图GV,E，长度函数LER，源点VS。目标是发现从源点到G的其它节点的最短路径或者得到一个负长度的回路。如果G有一个负长度的回路，我们称这个问题是不可行的。图21图223中国科学技术大学本科论文第二章最短路径问题概述23几类搜索算法思想231盲找BLINDSEARCHBLINDSEARCH是上面提到的最简单的一类。算法朝着目标点搜索，当发现障碍时，改变方向，沿着障碍的边缘探索。见图23。这里，算法在选择每一步的展开时，并没有将逼近目标点所花费的代价考虑进去。隶属BLINDSEARCH类的算法有宽度优先搜索法，双向宽度优先搜索法BIDIRECTIONALBREADTHFIRSTSEARCH，迪杰斯特拉（DIJKASTRA）算法，深度优先算法，迭代加深深度优先算法ITERATIVEDEEPENINGDEPTHFIRSTSEARCH。图23图24宽度优先搜索法和深度搜索法，是遍历图的两种重要方法。如果我们从某个节点N1出发，宽度优先算法中，离节点N1长度M的节点总是在离节点长度M1的节点之前搜寻到；深度优先算法中，如果节点N2搜索到，所有与N2相联的节点要优先于其它节点被搜寻。如果我们以家谱的术语讲就是，深度优先算法中，节点的子孙总是在他的尚未被访问的兄弟之前遍历到；宽度优先算法中，兄弟的遍历总是先于他的子孙。具体的实现通常由队列完成。以下是二者的伪码的实现宽度优先搜寻实现伪码TREE_TYPEBFS_QUEUETREE_TYPETREE,BOOLPREDICATETREE_TYPEQUEUE_TYPEQUEUECREATE_QUEUETREE_TYPEGUESSENQUEUETREE,QUEUEWHILEEMPTY_QUEUEFALSE4中国科学技术大学本科论文第二章最短路径问题概述GUESSDEQUEUEQUEUEIFEMPTY_TREEGUESSTRUECONTINUEIFPREDICATEGUESSTRUERETURNGUESSENQUEUELEFT_CHILDGUESS,QUEUEENQUEUERIGHT_CHILDGUESS,QUEUERETURNTHE_EMPTY_TREE深度优先算法实现伪码TREE_TYPEDEPTH_FIRST_SEARCHTREE_TYPETREE,BOOLPREDICATETREE_TYPETREE_TYPERESULTIFEMPTY_TREETREETRUERETURNTHE_EMPTY_TREEIFPREDICATETREETRUERETURNTREERESULTDEPTH_FIRST_SEARCHLEFT_CHILDTREE,PREDICATEIFEMPTY_TREERESULTFALSERETURNRESULTELSERETURNDEPTH_FIRST_SEARCHRIGHT_CHILDTREE,PREDICATE宽度优先算法只要各个节点的代价是一致的，就可以确保找到最短路径，见图24。双向宽度优先算法是，两个宽度优先算法分别由源点和目标点同时出发，直到搜寻到一个共同的节点汇合，最终的路径就是源点到汇合点的路径加上目标点到汇合点的路径。5中国科学技术大学本科论文第二章最短路径问题概述232DIJKASTRA算法将DIJKASTRA算法从BLINDSEARCH类中提出单独分析，是因为以下重点介绍的A算法，实际上就是建立在典型的DIJKASTRA算法之上的。A算法将启发式加入了DIJKASTRA算法中，从而保证在无负数边的有向图上有效地找到代价最低的路径。DIJKASTRA算法第一次提出是在DIJK59，现代解释和完整证明在CORM90给出。以下给出算法的简洁描述输入为有向图GV,E,源顶点VS，这里V是顶点的集合，E是图G的边集合，进一步有边的权值函数WU,V0，VU,VE。算法将顶点集合V划分为两类，V。集合R包含的顶点，是那些已经确定得到离源点的最近路径的顶点，集合。当一个顶点从集合转移到集合R，我们就称它已经“退休”。在一些算法的描述中，称Q为打开OPEN集合，称R为关闭CLOSE集合。对于每一个顶点，V，我们都保存当前最短路径的估计值，GV。因为我们实际感兴趣的不是那些最小代价的数值，而是组成那个最小代价的顶点集合。所以，我们将为每一个顶点保存一个“入边”，EDV，即在到当前顶点的最短路径中，那个直接由邻点到当前顶点的边。这样，我们就可以根据这个信息，从目标点反向回溯重建这条最短的路径。如果有一条以上的最优路径，只有最近发现的路径被记录下来。DIJKASTRA的伪码实现如下QRVQRQDIJKSTRAG,W,SRQDOVVALLFORVGQINSERTVDOQWHILEUQEXTRACTMINURRDOUNEIGHBORSVFORIFGVGUWU,VTHENQDECREASEKEYV,GUWU,VEDVU,V6中国科学技术大学本科论文第二章最短路径问题概述以上，集合Q可用优先队列实现，但必须实现三种操作1QINSERTU，在队列中插入顶点；2QEXTRACTMIN，将有最短估计的顶点VQ从队列中移出；3ADECREASEKEYV,A，将GV减小至A，并更新队列。算法就是不停地展开具有当前最小代价估计GV的顶点VQ。因为所有边的代价都为非负，在某一顶点展开后得到的最短路径，不可能比当前顶点得到的最短路径还短。因此，我们已经确定了某一顶点V的当前最短路径后，就可以将其“退休”至集合R。然后我们检验，当前这条路径向邻顶点展开出去，是不是会有比那些邻顶点当前具有最短路径更短的路径。如果有，我们就更新松驰RELAX最短路径的估计，以及相应邻顶点的入边。因为我们始终在选取具有当前最短路径的顶点，然后松驰它，所以这个算法属于典型的“贪心”松驰优化算法。在实际应用中，我们可以将Q划分为两个集合，U和PQ。算法开始时，U包含了所有的顶点除了S，如果某个顶点，第一次被访问到,就将其移到PQ集合中。我们也可以用标志位来表示一个顶点以前是不是被访问过，这样我们就不用显式的保存集合U。为了让算法的效率更高，总是希望将队列PQ的大小控制的越小越好。233最好优先算法BESTFIRSTSEARCH，简称BFS最好优先算法是一种启发式的搜索算法，也就是它将地图的一些知识带入了搜索标准中。它类似DIRJKSTRA算法，但是它总是先走向离目标点最近的顶点，而不是逐渐走向离出发源点越来越远的顶点，然后一步步地逼近。BFS的关键就是，“面向问题”寻找可以用来做决策的标准。标准选择的好坏直接关系到搜寻的结果，甚至关系到是否有解。如何选择适当的标准，以及算法中是如何体现这种启发式，A算法就是最好的体现。因为A算法就是建立在典型的DIRJKSTRA算法和BFS算法之上的。234A算法A算法是一种非常有效的路径寻优算法，它比DIJKSTRA算法和BFS算法都要快，最早出现在1968年，算法结合了启发式方法利用解决问题时的决策标准和正规方法没有利用问题有关的信息，可以正规分析,NILS82。算法的整体框架是一个图的遍历搜索算法，但它不同于大多数图的搜索算法，采用了启发函数来估计地图上的任意点离目标点的远近程度。通过这种启发式，可以协助选择最好的方向搜索。如果过程中失败，还可以选择其它的路径探索，直到找到最优的路径。7中国科学技术大学本科论文第二章最短路径问题概述因为我们感兴趣的只是两个顶点之间的最短路径，像DIJKSTRA算法计算出从一个顶点到所有其它顶点的最短路径，就是一种对资源的浪费。最显然的改进，就是当目标顶点一旦“退休”，立即停止搜索。可是，这样的改进在搜索的过程中根本就没有利用任何目标顶点的位置信息。A算法希望通过将搜索方向偏向目标点，从而提高搜索的效率。其中突出的一点体现在，每一次迭代过后，应该是哪些顶点“退休”，然后新的优先队列如何重新排序。最基本的思想是，取代DIJKSTRA算法采用的GV排序优先队列，用FVGVHV作为新顶点插入队列的排序标准，这里，GV表示源点到当前顶点的实际代价，HV是当前顶点的启发值。理论上已经给出证明，如果HV与从V到T的实际最小代价相比，是一个低估值UNDERESTIMATE，那么A就可以产生像DIJKSTRA算法的最优解。优先队列最糟糕的情况就是和DIJKSTRA一样的效率，但是我们如果提供一个良好的启发函数HV，A算法的平均效率就会好的多了。本章结尾处的图25给出一个典型的搜索过程。圆圈表示路径的目标点，灰色单元在算法的执行过程中没有被访问，黑色表示障碍。箭头表示那些被检验的单元当前所知的路径的边，也就是箭头处顶点的EDV值。粗箭头表示到目标点最近的路径。对于“退休”顶点，这也是到他们距离最近的路径。如果我们只对最短路径的代价感兴趣，就不必要保存EDV。现在可以利用EDV从目标点出发反向重建找到的路径。从反向回溯得到的路径中产生一个前向路径不是一件难事。实现A算法，最重要的考虑因素就是内存的使用和计算的时间，直接说就是优先队列如何实现可以最大地降低时间复杂度和空间复杂度。我们用N表示单元数目，每一次主循环中，PQEXTRACTMIN被调用一次，当节点被抽取到，就不再进行下去，所以这个循环最多执行N次。除了PQEXTRACTMIN之外，唯一一个操作不是以常数时间运行的是邻点的扫描循环。邻点扫描最多八次，这并没有提高时间的复杂性，而且在我们实际应用的矢量地图结构安排中，可以很容易地找到邻点。邻点扫描循环中，非常数时间操作就是PQINSERT和PQDECREASEKEY。所以，整个算法花费的时间为，,8,8MINEXTRAXTMINPQYDECREASEKEPQINSERTPQNO最简单的优先队列实现是用排序链表，因为PQEXTRACTMIN的时间复杂度为O1，PQINSERT和PQDECREASEKEY的时间复杂度为QN，所以整个算法的复杂度为O。很有名的优先队列是所谓的FIBONACCI堆。FIBONACCI堆的理论和实现比较复杂，根据内部的状态变量，花费的时间会不同。值得注意的是，FIBONACCI堆的分期清偿代价是PQINSERT是O1PQDECREASEKEY2N8中国科学技术大学本科论文第二章最短路径问题概述O1PQEXTRACTMIN是OLOGN,因此已知的A算法的实现时间复杂度为。隐藏在O里的是一个非常大的常数，因此他们对于小堆并不是很有用。NLOGNO考虑空间复杂度，算法开始时，如果每一点顶点需要保存GV和HV，就要花费ON。而且，优先队列的每一个成员也需要占据空间，队列的成员最大数目为N，因此总的空间复杂度有个上限ON。实际应用中，优先队列的大小要比N小的多。但是，在FIBONACCI堆中，队列中每个元素虽然是线性的，但都将消耗大量的空间。图259中国科学技术大学本科论文第三章A算法第三章A算法上一章提出了几种搜索算法思想，到底那个最好，还要按实际情况而定。考虑我们的实际应用，即“在矢量地图的基础上提供有效的路径选择算法，实现车辆的辅助导航功能，以及在道路堵塞仿真数据的基础上，动态规划最优的路径选择”，A算法是可行的，本章将详细阐述A算法的思想和各种提高性能采用的实现方案，并就典型的数据结构给出具体的伪码实现。结合矢量地图给出实际应用的流程。31A算法,图搜索策略，人工智能产生系统搜索策略上章前言提到，A算法作为一种搜索策略，在人工智能领域得到广泛研究和应用。大多数人工智能系统AI将计算元素划分为三类，数据DATA，操作集OPERATIONS，控制CONTROL。如果系统适当的描述，就可以得到中央实体，可称为全局数据库，它的操作建立在某种定义好的操作集，任何一种操作都将在全局控制策略下进行。人工智能产生系统的三个重要要素分别是全局数据库GLOBALDATABASE，产生规则集ASETOFPRODUCTIONRULES，控制系统CONTROLSYSTEM。全局数据库是被AI产生系统使用的数据结构，最简单的可以是一个小矩阵，在我们的实际应用中则是由点，线组成分层矢量地图数据结构。产生规则集运行在全局数据库之上，每一个规则都存在一个前提条件，只有当前提条件满足的时候，才可以在全局数据库上操作。控制系统决定使用哪一种规则以及规则运行的终止条件。许多AI的应用都包括一系列操作，比如控制机器人的行走以及自动编程。一个最简单的例子就是8PUZZLE的字谜游戏。8PUZZLE游戏就是，在一个33的网格中，放了八个方块，因为其中一个位置是空的，所以可以移动邻近的方块。那么如何从一种方块的分布模式，通过移动操作变为另外一种分布模式。将这个问题的表述对应到AI的三个要素上，就称为问题的表示REPRESENTATIONPROBLEM。好的问题表示是AI技术解决实际问题的关键。解决类似8PUZZLE问题的基本过程如下PROCEDUREPRODUCTION1DATA创建SEARCHGRAPH,G,仅包含起始节点，S。将S保存到OPEN表；2创建CLOSE表，初始为空；3LOOP如果OPEN空，返回失败；4从OPEN表中选取第一个节点，移出OPEN表，并将其放入CLOSE表,令这个节点为N5如果N是目标节点，成功返回，并利用指针从N返回至S，回溯出完整的路径指针在第七步产生6展开节点N，产生孩子集合M，并在图G中将其以孩子建立起来；7建立由集合M元素到节点N的指针，如果该元素在G中不存在也就说，在OPEN表和CLOSE表中都不存在将M的这些元素加入OPEN表，对于已经存在于OPEN表和CLOSE表的，决定是否重新将指针定向到N，对于M的成员已经存在于CLOSE表的，决定G中他的子孙是否应该重定向指针；8重新排序OPEN表，或者按照任意的方法，或者按照启发式的度量；9返回LOOP。以上这个过程充分普遍化，基本上包含了大量特殊的图搜索算法。过程GRAPHSEARCH产生了一个显式图，G，称搜索图SEARCHGRAPH和子集；T，称搜索树SEARCHTREE。G中的每个节点均包含在T中，搜索树是通过第七步定义的指针得到。G中每一个节点除了S都含有一个指针指向唯一的父亲。G中保存了算法发现的每一条可能的路径；T仅保存了到某一节点的路径。粗略的说，OPEN表13中国科学技术大学本科论文第三章A算法保存的是搜索树的叶子节点，CLOSE表保存的是非叶子节点。精确点就是，在第三步中，OPEN表保存的是那些尚未被展开的节点，而CLOSE表保存的或是那些搜索图中被选择展开但没有产生任何孩子的节点，或是搜索树中的非叶子节点。第八步的OPEN表排序是为第四步选择最优节点展开服务的。这种排序或者建立在大量启发函数上，或者建立在各种任意度量标准上。无论什么时候，只要是目标节点被选做了待展开点，过程就成功结束。这条从源点到目标点的成功路径，就可以利用指针从目标点朝源点反向重建出来。当搜索树中没有尚未展开的叶子节点时，过程就失败返回，因为有些节点根本就没有子孙，所以最终的OPEN表是有可能为空的。如果这种失败返回的情况发生，目标节点对出发点来说，就是不可达的。进一步分析过程的第七步。如果被搜索的隐式图是一个树，我们可以确定第六步产生的孩子以前一定没有生成过每一个节点除了根节点都是唯一节点的孩子，因而只有它的唯一父亲被展开时，生成且只生成一次。这样，M的每一个元素都将加到OPEN表中，并且在搜索树中作为N的孩子。在整个算法的执行过程中，搜索图也就是搜索树，没有必要改变子集T中节点的父亲。如果被搜索隐式图不是树，就有可能M元素已经存在于OPEN或CLOSE表。带来的问题是比较前后产生的结果而产生新的计算。可是，节点的重复带来的是计算孩子花费的冗余。因此，在比较前后产生结果和产生较大的查找树之间存在一个折衷。在第六步和第七步，算法是假设了比较前后产生节点不同所花费的时间代价，这是值得的。当搜索过程产生了以前已经生成的节点，意味着发现了新的也许是更好的路径。我们希望搜索树保存的是目前所有已找到的路径代价中最小的。当新产生的路径代价较小时，搜索树就会将新产生节点的父亲调整作为最近的父亲。如果在T上，父亲的CLOSED表上中节点N发生了改变，就意味着找到了一条到节点N代价较小的路径。这个较小代价的路径可能成为，搜索图G中到节点N的一些孩子的最短路径的一部分。因为G是有限的，这种朝着N的孩子下行转播新路径的过程，将是直观和有限的。323无知搜索UNINFORMEDGRAPHSEARCH和启发式搜索HEURISTICGRAPHSEARCH如果OPEN表排序没有用到问题域任何启发信息，这样的搜索过程称为无知或盲找UNINFORMED。AI领域，通常不对这种类型的查找感兴趣。最典型的是前面提到的深度优先，和宽度优先搜索。在深度优先搜索中，OPEN表节点是按照14中国科学技术大学本科论文第三章A算法他们在搜索树中的深度排序的，最深的节点被放到表的最前面，相同深度的节点之间任意排列。为了避免搜索过程长期陷入无效搜索，可对深度加限制，超出这个深度限制的节点不被展开。宽度优先搜索中，OPEN表节点是按照他们在搜索树的深度递增的顺序排列，如果源点和目标点之间的路径存在，宽度优先搜索总可以找到最短的路径。盲找是消耗型的搜索算法，在找到路径之前展开了太多的节点，因此在AI的产生系统中通常是不可行的，因为在实际的应用中，花费在路径寻找上的时间和空间都是有限制的。对于很多应用，利用与问题相关的信息约束搜索范围是完全可能的。这种排序信息称为启发信息HEURISTICINFORMATION，利用启发信息的搜索称启发式搜索HEURISTICSEARCH。通常是可以做到，在保证找到最短路径的前提下，降低搜索花费。当然也存在一些启发式，虽然大大地降低了搜索花费，但不能保证得到的是代价最小的路径。在解决实际的问题时，我们通常感兴趣的是降低路径代价和搜索这些路径所花费代价的一个组合值。而且我们希望得到的搜索方法，能够在待解决的所有问题的基础上，拥有的平均组合代价最小。平均组合代价实际上是无法计算的，因为很难给出问题集合的概率分布，评判一种方法平均组合代价的大小，只能靠一种从实际中总结出来的有知识的直觉INFOMEDINTUITION。需要指出的一点，在我们的矢量地图最短路径的搜索中，如何选取合适的启发式，是与地图的托扑类型和网的稠密度有关的，这需要从大量的实验中得出所谓的“直觉”的参数。324评价函数启发信息是为了排列OPEN表，展开信度最高的前端部分，因而需要一个方法计算节点的信度PROMISE。很重要的方法是在节点上使用一个实值函数，称评价函数EVALUATIONFUNCTION。评价函数的选择可以建立在很多种想法之上，比如，定义节点可能在最短路径上的概率函数，任意一点与目标点距离的度量，等等。为了找到最优的路径，A算法同时使用启发式函数HP和函数GP起始点到当前点P的最优路径代价函数这两个函数的和作为评价函数，记作FP。FP给出节点P的函数值，并且认为F是从源点到目标点经过节点P最短路径的估计。我们用函数F排序OPEN表中节点。OPEN表中的节点是按照F值的递增顺序排列，评价值低的节点在最优路径上的可能性大。15中国科学技术大学本科论文第三章A算法评价函数的选择严重影响搜索的结果。如果函数低估了一些节点的信度就会产生非最小代价路径，如果函数高估了一些节点的信度又会导致过多节点的展开，比如差的评价函数得到的只是一个宽度优先搜索。325启发式函数在路径寻优的问题上我们不应该只注重”最优”。事实上我们希望的是能快速地找到一条合理的路径，而并不是花上很多的时间去找那条最短的路径。当实际使用A算法的时候，我们希望获得的是一个可以减少搜寻时间，又相对合理的启发式函数。启发式函数HP为A算法提供了当前点P到目标点的一个代价估计。当使用类似A算法一类以启发式为基础的算法时，我们应该选用怎样的启发式函数呢启发式应该是连续的函数，而且对应于不同的地图空间，同一个启发式有可能面目全非。下面几种距离就可用作启发式函数MANHATTAN距离MANHATTAN距离是启发式的基础。观察不同的价值函数，可发现从一处到另一处的最小代价值。假设这个值是10，那定义的启发式就应该是10倍的MANHATTAN距离。10YGOALYAABSXGOALXAABSAH我们还可以使用比例尺配合我们的代价函数，这里不再仔细分析。斜距离DIAGONALDISTANCE如果在地图中可以允许存在对角线上的移动，那么就需要另一种启发式。在MANHATTAN距离定义的启发式中，假设需要向东移动4，向北移动4，那加起来总共移动的距离就是8。但是，如果你只是向东北方移动，只需移动4。所以此时的启发式应该是4。那么斜距离函数为,MAXYGOALYAABSXGOALXAABSAH直线距离STRAIGHTLINEDISTANCE如果在我们的系统中可以允许向任何方向取代网格的固定方向移动，那么我们就可以使用直线距离22YGOALYAXGOALXASQRTAH参考AMIT9916中国科学技术大学本科论文第三章A算法33A算法331A算法定义评价函数F，节点N处的估值为FN，估计从出发源点S到节点N处的最短路径代价加上从节点N到目标节点的最小路径代价。也就是说，FN是对约束从节点N通过的最短路径代价的估计。OPEN表中具有最小估计值F的节点，估计只需很小的约束，适合下一步展开。为方便分析评价函数的性质，引入以下术语。定义函数给出任意两个节点,间最短路径的实际代价注意，K在两个不可达的节点之间没有定义。节点N到某个目标节点的最短路径代价由给出。令HN为目标节点集合T上所有的最小值，因此HN是从节点N到目标节点的最短路径注意，如果目标节点不可达，函数H没有定义。通常我们感兴趣的是，给出从源点S到任意节点N的最优路径代价K。引入新函数G简化描述，定义G，所有N对于S可达。定义函数F，FN为节点S到节点N最优路径代价加上从节点N到目地节点最优路径代价，即FNGNHN。函数值FN就是约束从节点N通过的最优路径的实际代价。注意到，FSHS是从源点S出发到目的点无约束优化路径的实际代价。,JINNKINIJNIT,ITNK,ITNK,NS,NSK我们希望，评价函数F对F的值有个良好估计，估计值FNGNHN，G是对G的估计，H是对H的估计。GN估计的一个显然选择，就是搜索树中S到N的路径总和，这条路径是搜索算法中S到N的当前最短路径，如果上述第七步中搜索树变化了，某些节点的GN就会减小。注意到，这个定义隐含了GNGN。HN的估计HN建立在问题域的启发信息上。设定我们采用评价函数FNGNHN，作为图搜索算法中节点排序的标准，我们称这样的图搜索算法为A算法。如果H0GD搜索树中节点的深度，A算法就等同于宽度优先算法。前面我们提到，宽度优先算法可以保证搜索出最小代价的路径。这里，也可以证明，如果H选择为H的一个下限，即对于所有节点存在HNHN，A算法总可以找到逼近目标点的优化路径。如果A算法采用的17中国科学技术大学本科论文第三章A算法H是H的下限，我们就称这样的算法为A算法。H0一定是H的下限，所以宽度优先算法实际上是A算法的一个特例。332A算法的可采纳性ADMISSIBILITY对于任一图，只要源点到目标点之间存在路径，搜索算法总以找到的优化路径结束，我们称这样的搜索算法是可采纳的。证明算法可采纳，必须证明算法在目标点可达的前提下总可以终止。GRAPH_SEARCH算法在STEP3或STEP5终止。注意到，算法的每次循环，总有一个节点从OPEN表中移出，而且只有有限的展开得到的孩子被加入OPEN表。对于有限图，我们最终会用完所有的子孙，因而算法要么在STEP5找到最优路径之后成功返回，要么在STEP3因为耗尽OPEN表中所有节点终止。结论1GRAPHSEARCH对于有限图绝对可终止。可以证明，如果源点S与目标点之间存在路径，A算法对于无穷图也绝对可终止。理由是，假设A算法不可以终止，这种情况的产生只可能由于新的孩子节点不断的加入OPEN表。我们可以证明，即便OPEN表中最小的FN也会变成“不现实的大”。令DN为A产生的搜索树中，S到N的最短路径长度，因为图中每条弧的代价至少是一个任意小的正数E，有GNDNE。显然，GNGN，GNDNE。如果HN0，FNGN，则FNDNE。特别对于OPEN表每一节点，FN至少应该与DNE一样大，即使A选择OPEN表中F值最小的展开，如果算法不终止，D值会任意地大下去，F也会任意增长下去。为了证明A算法绝对终止，先证明A终止前，OPEN表中总会出现一个节点满足FNFS。根据结论2，算法结束之前，OPEN表中存在节点N，并且在最优路径之上，有FNFSH2N，称算法A2比算法A1更富有知识INFORMED。这种定义直觉上是合理的，因为H的下界保证了算法的可采纳性。较高的H值就要求更准确的启发信息。我们也可以直觉地认为，越富有知识的算法找到最短路径需要展开的节点就越少。当然，仅仅因为算法展开较少的节点，是不足以说明算法的效率，因为越富有知识的算法在预估函数的计算上要花费的代价也越大。但是，展开节点数确实是衡量算法有效的因素之一，也是比较算法优略的要素之一。假设A2算法比A1算法更有知识，A1,A2用来搜索最短路径，并且都以找到的最短路径终止。采用归纳法可以证明，A2算法在G中展开的节点N，也将在A1算法中展开，A1总是至少展开A2算法展开的节点。首先证明，A2在搜索树中展开深度为零的节点N，同样也会在A1中展开。这种情况就是NS，如果S就是目标点，则不展开任何节点；如果S不是目标节点，两种算法都会展开S节点。假设A2算法在深度K以下展开的节点都将在A1算法中展开，我们必须证明A2算法在深度K1以下展开的节点也将在A1算法中展开。根据归纳假设，A2搜索树中节点N的祖先，在A1算法中同样被展开。因此，A1搜索树中一定存在一个S到N的路径，代价不超过A2搜索树中S到N的路径，即G1NG2N。将反证法引入上面的归纳证明过程。假设A1没有展开A2中展开的节点N。因为A1展开了节点N的父亲，所以在算法A1终止时，节点N一定存在于OPEN表中。因为A1是以一个最小代价路径终止的，这个路径没有展开节点N，可以得出，F1NFS,有G1NH1NFS。因为我们已经证明G1NG2N，可以得出H1NFSG2N。但是，根据结论5，因为A2展开节点N，可以得到F2NFS，或G2NH2NFS,或H2NFSG2N。比较早些得到的不等式，H1NFSG2N，H1和H2必须一样大，这就与A2比A1更具有“知识”相矛盾。因此我们有结论620中国科学技术大学本科论文第三章A算法结论6如果A1，A2为两种A算法，A2比A1更具有知识MOREINFORMED，在图中搜索源点S到目标点的最短路径，并且都以发现最短路径终止，那么A2算法展开的节点一定在A1算法中被展开推论得，A1算法展开的节点数至少等同于A2算法。334A算法的单调约束MONOTONERESTRICTIONGRAPHSEARCH的描述过程中，我们注意到，当节点N被展开的时候，它的一些孩子可能已经存在于OPEN表或CLOSE表，搜索树就需要修改以便找到源点S到节点N的较小代价的路径。除了树的调整以外，判断节点是不是已经产生，计算量也是很大的。可以证明，如果H上存在一个合理的约束，A选择某个节点展开的时候，就已经找到了S到那个节点的优化路径。我们称满足以下条件的启发函数具有单调约束性，即对于所有节点N和，为的孩子，有IJNJNIN,JIJINNCNHNH，可改写为JN,IJINCNHNH，看似三角不等式。不等式表示，节点N到的最优代价估计不会超过到的弧的代价加上到目标点的最优代价的估计。IJNINJNJN下面证明，如果启发函数具有单调约束性，A展开节点的时候就已经找到了到这个节点的最优路径。如果NS，A无所谓找到S的最优路径，因此假设N不是S。令序列P,10NNNNSK是S到N的最优路径，令节点是在A选择N展开的时候，序列中最后出现在CLOSE表中的节点。因此，节点序列P中，在A选择节点N时，存在于OPEN表上。利用单调约束有LN1LN,11IIIIIINHNNCNGNHNG因为和IN1IN在最优路径上，,1JIIINNCNGNG因此有，。NHNGNHNG11IIII21中国科学技术大学本科论文第三章A算法调换位置得，或NHNGNHNG11KKLL1LNHNGNF因此，节点选取之后，在A选取节点N的时候，一定满足；不然，FN就会比大。因为对于搜索树中所有的节点M都有GMGM，所以，1LNFNGNG1LN结论7如果单调约束条件满足，当某一节点被选择展开时，A已经找到了到这一节点的最优路径。也就是说，如果A选择N展开，并且单调约束满足，就有NGNG单调约束隐含了另一个有趣的结果，A展开的节点序列，F值总是非递减。假设N2紧接着N1被展开，当N1被展开的时候，如果N2存在于OPEN表中，有FN1FN2。如果N2不在OPEN表中，那么N2一定会通过展开N1点将N2添加到OPEN表中，于是N2就是N1的孩子，在这些条件下，FN2GN2HN2GN2HN2结论7GN1CN1,N2HN2GN1CN1,N2HN2结论7因为单调约束隐含了CN1,N2HN2HN1，所以，FN2GN1HN1FN1，这个事实对于A展开的节点序列的任何一对相邻节点都是成立的，所以我们得到结论8结论8如果满足单调约束，A展开的节点序列F值是非递减的。如果单调约束不满足，就有可能在展开时出现比先前展开节点更小的F值。我们可以利用这个事实，提高该情况下的算法效率。根据结论5，节点N被展开，满足FNFS。假设，在A算法整个执行过程中，用一个全局量F，保存目前展开所有节点的F值的最大值。那么任何时刻就有，FFS。如果OPEN表中的节点N满足FNPARENTINTNODEGETXVOIDRETURNPATHXINTNODEGETYVOIDRETURNPATHY/下面的两个函数直接被A算法使用INTTILENUMINTX,INTY/返回方格数目INTFREETILEINTX,INTY/如果可以从这个位置走过，返回值1PRIVATEVOIDBOUNDARYTILESVOID/初始化A地图之前，标记地图边界。VOIDFREENODESVOID/释放内存/A算法的实现部分VOIDFINDPATHINTSX,INTSY,INTDX,INTDYNODERETURNBESTNODEVOIDVOIDGENERATESUCCESSORSNODEBESTNODE,INTDX,INTDYVOIDGENERATESUCCNODEBESTNODE,INTX,INTY,INTDX,INTDYNODECHECKOPENINTTILENUMNODECHECKCLOSEDINTTILENUMVOIDINSERTNODESUCCESSORVOIDPROPAGATEDOWNNODEOLD27中国科学技术大学本科论文第四章A算法的典型实现VOIDPUSHNODENODE/栈操作NODEPOPVOID422ASTARPATHFINDER类部分实现，及与矢量地图结构的联系分析4221ASTARPATHFINDERASTARPATHFINDERCDXMAPPMAP,INTFORBIDDENTILES,ASTARPATHFINDERASTARPATHFINDER,VOIDASTARPATHFINDERINITASTARTILEMAPCDXMAPPMAP,INTFORBIDDENTILES。上述三个函数在A算法与网格地图之间起到桥梁作用，为A算法提供必要的数据结构支持，比如栈的分配与释放，OPEN，CLOSE表的分配和释放，以及为不同的地图建立合理的内存映象。因为ASTARPATHFINDER应用是针对方块状网格地图，地图的内存映象就比较简单。我们的矢量地图结构比较复杂，采用了点与弧两层信息，虽然点的信息已经完全包括了地图的全部拓扑信息，但是在实际的路径选择中，道路选择的基本单位是弧，即两个相邻大节点间的连接。通过这两层的信息可以完成邻接弧的搜索，从而在A算法的实现上，网格与矢量地图没有区别。4222VOIDASTARPATHFINDERFREENODESVOIDNODENODE,OLDNODEIFOPENNULLNODEOPENNEXTNODEWHILENODENULLOLDNODENODENODENODENEXTNODEFREEOLDNODEIFCLOSEDNULL28中国科学技术大学本科论文第四章A算法的典型实现NODECLOSEDNEXTNODEWHILENODENULLOLDNODENODENODENODENEXTNODEFREEOLDNODE完成OPEN表和CLOSE表的空间释放，从中可以看出典型的链表结构。4223VOIDASTARPATHFINDERFINDPATHINTSX,INTSY,INTDX,INTDYNODENODE,BESTNODEINTTILENUMDESTTILENUMDESTTILENUMDX,DYOPENNODECALLOC1,SIZEOFNODECLOSEDNODECALLOC1,SIZEOFNODENODENODECALLOC1,SIZEOFNODENODEG0NODEHDXSXDXSXDYSYDYSY/预估函数H采用直线距离NODEFNODEGNODEH/计算节点的评价函数NODENODENUMTILENUMSX,SYNODEXSXNODEYSYOPENNEXTNODENODE/将OPEN表指向第一个节点/A算法的主循环FOR29中国科学技术大学本科论文第四章A算法的典型实现BESTNODERETURNBESTNODE/从OPEN表中返回最优节点并插入CLOSE表IFBESTNODENODENUMTILENUMDEST/判断是否已经到达目标BREAKGENERATESUCCESSORSBESTNODE,DX,DY/展开最近一次的最优节点PATHBESTNODE4224ASTARPATHFINDERNODEASTARPATHFINDERRETURNBESTNODEVOIDNODETMPCHARMESSAGE128IFOPENNEXTNODENULL/OPEN表没有新的节点，通常是因为源点到目标点不是可达的SPRINTFMESSAGE,“NOMORENODESONOPENPERHAPSTILENUMDESTINATIONNOTREACHABLE“MESSAGEBOX0,MESSAGE,“ERRORAPATHFINDER“,MB_OK|MB_ICONERRORPOSTQUITMESSAGE0/选则F值最小的节点，因为OPEN链表是经过排序的，链表的第一个元素就是要选择的节点，称它为最佳节点BESTNODETMPOPENNEXTNODE/指向OPEN表中第一个节点OPENNEXTNODETMPNEXTNODE/MAKEOPENPOINTTONEXTNODEORNULL/取出OPEN表中最优节点，并将其插入CLOSE表TMPNEXTNODECLOSEDNEXTNODECLOSEDNEXTNODETMPRETURNTMP30中国科学技术大学本科论文第四章A算法的典型实现4225VOIDASTARPATHFINDERGENERATESUCCESSORSNODEBESTNODE,INTDX,INTDYINTX,Y/以下是从当前最优节点所在位置出发，向八个方向展开；/这里的FREETILE函数是检查展开的这个位置是否走通，即是否为障碍；/展开左上角节点IFFREETILEXBESTNODEXTILESIZE,YBESTNODEYTILESIZEGENERATESUCCBESTNODE,X,Y,DX,DY/展开顶上的节点IFFREETILEXBESTNODEX,YBESTNODEYTILESIZEGENERATESUCCBESTNODE,X,Y,DX,DY/展开右上角节点IFFREETILEXBESTNODEXTILESIZE,YBESTNODEYTILESIZEGENERATESUCCBESTNODE,X,Y,DX,DY/展开右边节点IFFREETILEXBESTNODEXTILESIZE,YBESTNODEYGENERATESUC