基于打破对称性的快速寻路算法.pdf

《基于打破对称性的快速寻路算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第35卷第3期宁夏大学学报(自然科学版)2Ol4年9月Vo1．35No．3JournalofNingxiaUniversity(NaturalScienceEdition)Sep．2O14文章编号：0253—2328(2014)03—0216—05基于打破对称性的快速寻路算法邱磊(武汉船舶职业技术学院电气与电子工程学院，湖北武汉430050)摘要：基于Java实现了跳点搜索算法，给出了算法实现的过程．实验结果表明：跳点搜索算法找到了一条从起始节点到目标节点的最优路径，且能够有效地识别和消除网格地图上的路径对称性，大幅度减少了节点扩展的数量．对比A、宽度优先搜索、最佳优先搜索和D

2、ijkstra可知，在所求解的路径长度一致的情况下，跳点搜索在平均搜索时间上显著快于其他算法．因此，跳点搜索是快速、高效的．关键词：网格地图；寻路，跳点搜索，路径的对称性分类号：(中图)TP312；TP391文献标志码：A网格地图是一个简单但又常见的环境表示方路径的，本文所述的跳点搜索算法，能够有效地识别法，通常用于表示寻路的区域．等价网格地图环境下和消除寻路领域的对称性，大幅度减少节点扩展的的寻路问题普遍存在于机器人、电子游戏等应用领数量，可以非常快地到达目标点，加快了寻路的域．路径的对称性是等价网格地图的一种属性，也是速度．导致路径搜索速度减慢的主要原因，通过识别和消除网格

3、地图上的路径对称性，能大幅提高寻路的速1路径的对称性度并最终得到最优路径．人们在规划、约束编程和组合优化等领域均提出了识别和消除搜索空间对称性网格地图上的路径是一个有序的向量序列，其的方法，然而，在网格地图寻路领域却很少有文献系中每个向量代表从网格上的一个节点到相邻的节点统陈述识别和处理对称性的方法．研究者在网格地的一个单步．如果两条路径的起点和终点相同，并且图寻路领域做了很多工作，如2004年，A．Botea等交换一条路径的组成向量之间的顺序可以得到另一提出的HPA算法在不要求最优性的情况下，通过条路径，则称这两条路径是对称的，或称之为两条路将搜索空间分解为更小的近似值来提高

4、性能l】；径之间存在对称性_6。]．Bjornsson在2006年提出的“死胡同”启发算法l2及图1可以清楚地说明这一点．图1中每条路径Pochter在2010年提出的Swamps算法l_3]，均将网均具有相同的起点和终点、相同的路径长度，因而它格地图分解为一系列相邻的区域，以此来识别一些们之间是彼此对称的．换句话说，每条路径的移动序与最优求解一个特定的寻路实例不相关的区域；列是相同的，只是排列方式不同而已．图1a为沿着2009年，Sun等提出了快速扩展的方法，若发现某水平和垂直方向移动的路径对称的例子，其中，蓝色个后继节点与open列表中的最佳节点一样好(或更和紫色的路径具有

5、相同的起点和终点及相同的长好)时，则该方法避免对open列表做不必要的操度；图1b为允许沿着对角线方向移动的路径对称的作]．2010年，Sturtevant等给出了一种识别“死的”例子，其中，各条路径共享相同的起点和终点、具有和“冗余的”单元格的方法，该方法是在基于学习的相同的长度，因而这些路径之间是对称的．启发式搜索这个环境下开发的，只有对迭代加深算在对称性存在的情况下，一些搜索算法，例如法执行多次迭代后，才提高了搜索的速度Ⅲ5]．然而，A算法，必须去探索每一条最优路径上几乎每一个上述研究均不是通过识别并消除对称性而得到最优位置．图1中，到达目标之前，A算法有可能会扩展收稿日

6、期：2013—11—21基金项目：湖北省教育厅科学技术研究计划指导性项目(B2014202)；湖北自然科学基金面上项目(2Ol2FFB41O2)作者简介：邱磊(1982一)男，讲师，硕士，主要从事网格地图寻路研究．218宁夏大学学报(自然科学版)第35卷(searchGrid)；●：●jpParam．reset(newGridPos(10，10)，newGridPos(20，nrr、1O))；l、Step6为了找到一条路径，需用上面创建的IJumpPointParam对象作为参数去运行findPatha直线式跳跃b对角线式跳跃函数．图4修剪算法作用的两个例子List

7、os>resultPathList—JumpPointFinder．findPath(jpParam)；3算法实现与性能比较Step7不同于PathFinding．jS[M，JumpPoint—Param类可以通过改变起始和终止位置而多次本文的程序利用Java开发实现，参考了文献使用．E13]中WoongGyuLa的C#实现方法，与XujpParam．reset(newGridPos(15，15)，newGridPos(2O，Xueqiao的JavaScript实现方法_1]很相似．算法的1