计算机系统应用ＩＳＳＮ １００３．３２５４，ＣＯＤＥＮ ＣＳＡＯＢＮ ＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ＆Ａｐｐｌｉｃａｔｉｏｎｓ，２０１７，２６（７）：１４６—１５２【ｄｏｉ：１０．１５８８８０．ｃｎｋｉ．ｃｓａ．００５８５９］ ＠中国科学院软件研究所版权所有． Ｅ－ｍａｉｌ：ｃｓａ＠ｉｓｃａｓ．ａｃ．ｃｎ ｈｔｔｐ：／／ｗｗｗ．ｃ—Ｓ—ａ．ｏｒｇ．ｃｎ Ｔｅｌ：＋８６．１０．６２６６１Ｏ４ｌ 基于Ａ去算法的三维地图最优路径规划① 赵德群，段建英，陈鹏宇，苏晋海 （北京工业大学信息学部，北京１００１２４） 摘要：研究了基于Ａ 算法的适合人步行行走的山地环境下三维地图最优路径规划算法及实现．本文考虑了三维 山地无路息覆盖的条件较差环境，对Ａ 算法进行改进，并利用三维地形ＤＥＭ数据计算出一条相对平缓且长度 较短的三维路径．改进算法对三维条件下路径最短的评价标准由原有的空间距离累加最短改进为先将空间等效成 水平距离，再计算距离是否最短．同时，本文充分考虑了搜索点周围环境的整体坡度信息作为启发信息，来降低算法 寻找的路径走在陡坡上的概率．实验表明，本算法最终计算出的三维最优路径在平缓度及路径最短上有所改善，基 本符合人步行行走的习惯． 关键词：Ａ 算法；三维地图；山地；最优路径规划；ＤＥＭ 弓Ｉ用格式；ｊ赵德群’段建荚，陈鹏字；苏晋海：基于Ａ｜＿算法的三维地图最优路径规划。计算机系统应用；２０Ｉ Ｊ７ｒ，２６（７）：Ｉ４ １５２ｉ ｈｔｔｐ：／／ｗｗＷ，￣－ｓ— Ｏｐｔｉｍａｌ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｆｏｒ ３Ｄ Ｍａｐ Ｂａｓｅｄ ｏｎ Ａ古Ａｌｇｏｒｉｔｈｍ ＺＨＡＯ Ｄｅ—Ｑｕｎ，ＤＵＡＮ Ｊｉａｎ—Ｙｉｎｇ，ＣＨＥＮ Ｐｅｎｇ—Ｙｕ，ＳＵ Ｊｉｎ－Ｈａｉ （Ｂｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｄｅｐａｒｔｍｅｎｔ ｏｆＩｎｆｏｒｍａｔｉｏｎ，Ｂｅｉｊｉｎｇ １００１２４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｏｐｔｉｍａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ３Ｄ ｍａｐ ｂａｓｅｄ ｏｎ Ａ ａｌｇｏｒｉｔｈｍ ｉｎ ｍｏｕｎｔａｉｎｏｕｓ ｅｎｖｉｒｏｎｍｅｎｔ ａｒｅ ｓｔｕｄｉｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｉｔ ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｃｏｎｄｉｔｉｏｎ ｏｆ ｐｏｏｒ ｃｏｖｅｒａｇｅ ｏｆ ３Ｄ ｍｏｕｎｔａｉｎ－ｆｒｅｅ ｎｅｔｗｏｒｋ ｉｎｆｏｒｍａｔｉｏｎ ｃｏｖｅｒａｇｅ，ｉｍｐｒｏｖｅｓ ｔｈｅ Ａ ａｌｇｏｒｉｔｈｍ ａｎｄ ｕｓｅｓ ３Ｄ ｔｅｒｒａｉｎ ＤＥＭ ｄａｔａ ｔｏ ｃａｌｃｕｌａｔｅ ａ ｒｅｌａｔｉｖｅｌｙ ｓｍｏｏｔｈ ａｎｄ ｓｈｏｒｔ ｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌ ｐａｔｈ．Ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｅｖａｌｕａｔｉｏｎ ｃｒｉｔｅｒｉｏｎ ｉｎ ｔｈｒｅｅ— ｄｉｍｅｎｓｉｏｎａｌ ｓｐａｃｅ ｆｒｏｍ ｔｈｅ ｏｒｉｇｉｎａｌ ｓｐａｔｉａｌ ｄｉｓｔａｎｃｅ ａｃｃｕｍｕｌａｔｉｏｎ ｔｏ ｔｈｅ ｓｈｏｒｔｅｓｔ ｄｉｓｔａｎｃｅ，ａｎｄ ｔｈｅｎ ｃａｌｃｕｌａｔｅｓ ｗｈｅｔｈｅｒ ｈｅ ｔｄｉｓｔａｎｃｅ ｉｓ ｔｈｅ ｓｈｏｒｔｅｓｔ．Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ，ｔｈｅ ｇｌｏｂａｌ ｇｒａｄｉｅｎｔ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｓｕｒｒｏｕｎｄｉｎｇｓ ｏｆ ｔｈｅ ｓｅａｒｃｈ ｐｏｉｎｔ ｉｓ ｃｏｎｓｉｄｅｒｅｄ ａｓ ｔｈｅ ｈｅｕｒｉｓｔｉｃ ｉｎｆｏｒｍａｔｉｏｎ ｔｏ ｒｅｄｕｃｅ ｔｈｅ ｐｒｏｂａｂｉｌｉｔｙ ｔｈａｔ ｔｈｅ ｐａｔｈ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｌｏｏｋｓ ｆｏｒ ｉｓ ｓｔｅｅｐ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｓｍｏｏｔｈｎｅｓｓ ａｎｄ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｏｆ ｔｈｅ ｔｈｒｅｅ－ ｄｉｍｅｎｓｉｏｎａｌ ｏｐｔｉｍａｌ ｐａｔｈ，ｗｈｉｃｈ ａｃｃｏｒｄｓ ｗｉｈ ｔｔｈｅ ｗａｌｋｉｎｇ ｈａｂｉｔｓ ｏｆ ｈｕｍａｎ ｂｅｉｎｇｓ． Ｋｅｙ ｗｏｒｄｓ：Ａ ａｌｇｏｒｉｔｈｍ；ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ ｍａｐ；ｍｏｕｎｔａｉｎ；ｏｐｔｉｍａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ；ＤＥＭ 传统地图服务已经成为人们每天外出必须的功能， 其无论是形式还是技术发展都较为成熟，在实际中得 到了广泛应用…．其中，路径规划在交通导航这个方向 几乎全部集中于大中城市，对于乡镇以及山地等偏远 地区几乎找不到路息．通过路息的辅助，可以 很容易的规划处一条最优的路径，但在没有路网的条 件下现在的路径规划算法却毫无办法． 上应用广泛，极大地方便了人们的外出．然而，现有的 各大路径规划系统全部是在二维地图平台上实现。并 且严重依赖于交通路网这些数据［２】。同时这些路息 ①基金项目：国家重大科研仪器设备研制专项（１Ｌ００１７９０２０１５０１） 在二维路网式路径规划给人们带来便利的同时， 人们对路径规划的要求也有所提高，由二维转向三 收稿时间：２０１６－１１－０２；收到修改稿时间：２０１６—１２－０８ １４６软件技术・算法Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ ２０１７年第２６卷第７期 ｈｔｔｐ：／／ｗｗｗ．Ｃ—Ｓ—ａ．ｏｒｇ．ｃｎ 计 机系统心川 维、由有路网转向无路网，例如森林救火的行进路线 自动规划、戈壁滩的行车路径规划问题，规划出结果 的同时能在三维地图上有更为直观的展示． 对于三维路径规划问题，目前主要的算法有蚁群 一个己知的蔓维实景地图模型进行栅格化处理，利用 ＤＥＭ（高程模型）数据将一个＿二维地图降维成二维栅格 地图进而利刖 二维栅格ｒ｝１仔储的数据进行计算得出最 优路径的问题． 算法、遗传算法、粒子群算法、人工势能算法、Ａ 算 法等．文献［３—５］分别对蚁群算法进行 改进并应川剑 三维路径规划问题中，取得了一定效果，但是蚁群算法 收敛速度慢、容易陷入局部最优解的问题没有得到有 效解决；文献［６］利用遗传算法提出了…种针对于ＡＵＶ 海底三维路径规划的解决方案，对ＡＵｖ的安全航 起 到１ｒ重要的参考价值，但算法容易出 早熟及稳定性 较差；文献［７，８］ 对 ｒ飞行器飞行安全问题提出Ｊ，甚 于粒子群算法的 ！维路径规划算法，简化ｒ模型及参 数调整的步骤，提升了飞行器飞行的有效性 同时该算 法也｝ＩＪ现了搜索过程过早结束难以找剑最优解的问题． 文献［９】将启发函数与人，Ｉ 势场法相结合进行Ｊ，仿 真，仿真结果可以避开障碍物同时进行了， 滑处理，但 是算法得出的结果是否最优难以确定．文献ｆ１０ １４］分 别利用Ａ 算法并进行改进，在ｌＩ维网格或者游戏地｝ 型中进行仿真，得出较为满意的路径，为三维路径规划 问题提供了参考，但是以上算法大多采用简单的 维 或三维仿真模型进行试验 数据量和复杂程度都远远 低于真实地形地图 不具备一定的实用性． 本文针对于山地没有路网覆盖的情形，利用Ａ 算 法并在考虑三维地形坡度问题的基础上对原有算法进 行改进和优化，得出一条位于三维地图两点之间的坡 度符合人步行行进且路径最短的最优路径，同时 二 维实景地图展示最后的规划路径结果，满足了人的视 觉需求，具有一定的实用性． １研究目标 本文致力于研究出一种针对于山地，适合人步行 前进的坡度平缓且路径长度最短的路径．本文采用■维 地图模型进行实验以更加接近人在山区行进的真实环 境．在给定实验区域任意两点的情况下，能够实时计算… 适合人行走的路径，同时显示在三维实景地图上． 维 实景地图的最优路径规划问题可以直观地表示为 １． ２三维路径规划算法实现 ２．１数据准备 三维地图Ｉ【Ｊ地最优路径规划的问题实质卜就足将 奉文实验所用的ＤＥＭ数据由测绘无人机进行航１毛 并通过后期数据处理得到ｇｒｄ格式的 储文件．本文程 序运行前需要预处理将ｇｒｄ文件里存储的ＤＥＭ数据解 析、读出并存储到特定形式的数据结构中． ２ ＤＥＭ数据映射 如｝冬｛２所永，本文将一片ＤＥＭ数据转化为图示卜方 的一：维映射，其中ＤＥＭ数据集合可表示为： Ｄ＝｛Ｘｍｉｎ，Ｘｍａｘ，Ｙｍｉｎ，Ｙｍａｘ，ＮｕｍＣｏｌ，ＮｕｍＲｏｗ｝（１） 其ｒｆ１Ｄ为ＤＥＭ数据集合，Ｘｍｉｎ表示整片 域最小经度． Ｘｍａｘ表示最大经度，Ｙｍｉｎ表示最小纬瞍，Ｙｍａｘ表示最 大纬度，ＮｕｍＣｏｌ表示ＤＥＭ数据的总列数，ＮｕｍＲｏｗ表示 ＤＥＭ的总行数． 二维映射可以表示为‘个由ＮｕｍＣｏｌ＊ＮｕｍＲｏ￣ｌ，个 Ｎｏｄｅ节点的：：维数组：Ｄａｔａ［ＮｕｍＣｏ１］［ＮｕｍＲｏｗ］． Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ－Ａｌｇｏｒｉｔｈｍ软件技术・算法１４７ ｈａｐ：ｌｌｗｗｗ．Ｃ—Ｓ—ａ．ｏｒｇ．ｃｎ ２０１７年第２６卷第７期 Ｎｏｄｅ：』Ｆ【Ｖ ｇ，ｘ，Ｅ Ｌｏｎｇ 打“ｄ ， “ｄ ，Ｅ 口 ，２，１ ａｌｕｅｈ，Ｖａｌｕｅｇ，Ｖａｌｕｅｆ，Ｐａｒｅｎｔ Ｊ 最短距离，其计算公式为： Ｇ（ｆ）＝Ｇ（ｉ—１）＋Ｌ （５） ＿（２） ・Ｆｌｎｇ—— ｉ南 识 其中Ｇ（ｉ—１）为栅格ｉ的父栅格ｉ．１到起始栅格Ｓ的累积最 短距离， 为栅格ｆ到其父栅格ｆ．１的距离，在通常情况下 ￡取的是两点之间的三维空间直线距离．对于上述算法， ・ ． 节点所处二维数组的横坐标： ・ｙ 一节点所处二维数据的总坐标； ・ ￡０ ｍ“ 一・ 口ｆｆｍ如一・ Ｅ 节点经度； 节点纬度： 本文称之为３ＤＢＡ＊算法． ３ＤＢＡ＊算法理论上能够搜索到一条最短的路径， 比较适合于二维地图和较为简单的规则三维游戏地图 模型．经过实验本文发现由真实ＤＥＭ数据表示的山地 区域来说，地形较为复杂，而３ＤＢＡ＊算法只考虑最短距 离却没考虑坡度问题，因此不能完全适用．如图３方框 Ｄ ——节点高程： 节点到起点走过的实际值； Ｖａｌｕｅ＿ｈ与Ｖａｌｕｅｇ的和； ＿・ Ｖａｌｕｅ Ｊｌｚ——节点到终点的启发值； ・ Ｖａｌｕｅ ・ＶａｌｕＰ卜．・ 尸口 ，２ 节点的父节点． 内的路线所示，３ＤＢＡ＊算法计算出来的路径往往走在 陡峭的山坡上，这样的路径过于危险，并不适合人的行 走．因此，在３ＤＢＡ＊算法的基础上，本文从距离最短和 Ｊ 式中节点标识Ｆｌａｇｎ－Ｓ以表示为： ， ｇ １ Ｓ ＴＡＲＴＰＯＩＮＴ，ＤＥＳ ＴＩＮＡＴＩＯＮ ・ ・ Ｌ 节点可以通行： Ｂ三 一节点不适合通行： ｆ ＶＩＡＢＬＥ，ＵＮＶＩＡＢＬＥ，ＩＮＯＰＥＮ，ＩＮＣＬＯＳＥ，１ （３） ｆ 坡度较缓两方面因素入手提出一种改进型Ａ 算法．适 合于三维山地地形，适合于人行走同时路径较短，本文 称之为３ＤＡ＊算法．本文将在下一节详细描述３ＤＡ＊算 法的实现方法． ・ ，ⅣＤ尸 ＾Ｌ下节阐述１中： ・ 节点在开放列表（开放列表将在 ＣＬＤ． ～节点在关闭列表ｆ关闭列表将在 下节阐述）中； ・ Ｒ ，Ｄ ｙＤⅣ＿节点为起始节点： 节点为终止节点． ・ ＤＥＳ ２．２基本算法介绍 Ａ 算法引入了估值函数：Ｆ（ｉ）＝Ｇ（ｉ）＋日（ｆ），Ｇ（ｆ）是 栅格ｆ到起始栅格的已知最短距离，称为代价函数； ｆ）是栅格ｆ到目标栅格的估计值［８】，称为启发函数． 如果 （ 是小于或等于从ｆ到目标的实际花费， 图３ ３ＤＢＡ＊算法危险路径 ２．３改进算法（３ＤＡ ）的实现 ２－３．１ 坡面与水平地面距离的等效 那么Ａ 算法就能确保找到最短路径， ｆ）的值越小， Ａ 算法要扩展的节点就越多，算法就越慢 ｎ】．对于三维 文献［１５］￣？Ｃｈｙｉ—Ｒｏｎｇ等人兼顾坡度及体能消耗等 多种因素并在多处山地环境下进行亲身测试得出人在 山地步行行走的速度与坡度的关系如下所示： ｌ／Ｖ＝０．７５＋１４．６ｓｌｏｐｅ （６） Ａ 算法通常 ｆ）取欧几里德距离作为启发值，由于这 个启发值通常小于栅格ｆ和终点栅格ｅ的实际距离，因此 能够保证搜索的路径距离最短，例如文献［９】和文献 ［１４】皆用到了欧几里德距离作为启发值．启发值 ｆ）取 栅格ｆ和终点栅格ｅ之间的三维距离，计算公式： 式中 人的步行速度，ｓｌｏｐｅ为地形坡度的正切值 由式（６）可以推出：Ｖｏ＝４／３（坡度为０时速度） 由式（６）和Ｖｏ＝４／３可以推出在坡度为ｓｌｏｐｅ的山地上 （ｆ）＝４［（Ｃｏｌｉ－ＣｏｌＰ） ＋（Ｒｏｗｉ－ＲｏｗＰ） 】女Ｓｉｚｅ ＋（Ｚｉ－Ｚ ） （４） 行走单位距离 与等效水平地面距离 的比值为： Ｓ Ｖ １ … 其ｑ￣（Ｒｏｗｉ，Ｃｏｌｆ）为栅格ｉ的行列号，Ｚｉ为栅格ｉ的高程， Ｓｉｚｅ为栅格的分辨率．Ｇ（ｆ）为栅格ｆ到起始栅格Ｓ的己知 １ ４８软件技术・算法Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ ０ ｌ＋１９．４６ｓｌｏｐｅ２ ２０１７年第２６卷第７期 ｈｔｔｐ：／／ｗｗｗ．ｃ—ｓ—ａ．ｏｒｇ．ｃｎ 汁算机系统应用 由式ｆ６）可以看出，在坡上行走的速度随坡度增大 平距离； 一 表示Ａ～Ｈ中的被遍历到的节点ｎ与终点ｅ的 高度差值；ｓｌｏｐｅ 一 表示Ａ￣Ｈ中的被遍历到的节点 与 终点ｅ的坡度正切值ｓｌｏｐｅ 一 ＝ｄｈ 一 ／ｄｌ 一 ；ｓｌｏｐｅ 表示 Ａ～Ｈ中的被遍历到的节点”与当前处理节点Ｃｅｎｔｅｒ的坡 减小，坡度增大的同时也会增加体能的消耗【ｌ刚．再由式 （７）可以发现利用式（５）所表达的空间距离评价己走路 径是否为最短并不科学，因为在坡面上行走单位距离 并不等于相同的水平距离，在坡面上行走较为困难，实 际等效成的水平距离要大于相对应的坡面距离．本文 提出，评价路径最短的标准可以将式（５）坡面上行走的 度正切值（￣ｓｌｏｐｅＡ）． 本文ｒＯｓｌｏｐｅ 并非简单地将遍历节点与Ｃｅｎｔｅｒ节点 的高度差除以水平距离，这样的话只是考虑了局部坡 坡面距离由式（７）先等效成水平距离，再判断距离是否 最短． ２．３．２改进算法描述 度信息对路径寻优的影响，却并未考虑到遍历节点的 整体坡度环境，从而造成２．２节提到的图２所示的路径走 在斜坡上的问题．为了尽量避免上述问题，本文在计算 坡度信息的时候还考虑了此遍历节点与Ｃｅｎｔｅｒ节点方 向垂直的方向的坡度，本文仅以图４所示Ａ（代表Ａ、 Ｃ、Ｈ、Ｆ之－－）￣ＤＤ（代表Ｂ、Ｄ、Ｇ、Ｅ之一１两点为例． 改进算法估值函数依然采用ｆ（ｎ）＝ｇ（ｎ）＋，ｚ（，１），本 文根据２．３．１节讨论，先把坡面距离等效成水平距离，再 判断距离是否最短，由此本文引入新的ｇ（ｎ）表示方法． 结合式（５）和式（７）本文得出新的 ）表示法： ｇ（ｎ）＝ｇ（ｎ一１）＋（１＋１９．４６ｓｌｏｐｅ ）｛Ｌ （８） 其他的节点计算方法与这两点一致，Ａ、Ｄ两点的坡度 计算方法如下： ｓｌｏｐｅＡ＝（ｓｌｏｐｅｃ—Ｆ＋ｓｌｏｐｅＡ—Ｃ ｒ）／２ （１ ０） 式（８）只是在考虑了坡度影响人行走速度的情况下提出 的新的评价山地地形最短路径的标准，一定程度上影 ｓｌｏｐｅＤ＝（ｓｌｏｐｅｓ—Ｇ＋ｓｌｏｐｅＤ—Ｃ洲 ｒ）／２ （１１） 响了算法寻找出的路径，使路径坡度总体变缓，但是实 验结果发现在不改变２．２节所述３ＤＢＡ＊算法启发函数 （，１）的情况下，算法寻找出的路径仍然存在２．２节提出 需要注意的是如果式ｓｌｏｐｅ 的值大于０．３５１ｊ寸，本文 将此节点的Ｆｌａｇ置为ＵＮＶＩＡＢＬＥ． ２．３＿３实现步骤 算法需要建立两个列表来存储节点数据，一个为 “开启列表”，本文称之为ＯｐｅｎＬｉｓｔ，用来存储等待检查 的节点：另一个为“关闭列表”，本文称之为ＣｌｏｓｅＬｉｓｔ，用 来存储不需要再次检查的节点． 以下为算法的流程： 的路径走在陡坡上的问题．因此本文对启发函数 （ ）进 行了改进： ｈ（ｎ）＝（１＋ｓｌｏｐｅ￣一 ）（１＋ｓｌｏｐｅ￣）（ｄｌｎ一 ＋ｄｈ 一 ） （９） 式（９）中ｎ代表当前被遍历的地图节点，ｅ代表终点节点， 图４中Ｃｅｎｔｅｒ代表当前正在处理的节点，Ｃｅｎｔｅｒ的周围 节点（图４中Ａ～Ｈ节点）代表待遍历的节点．式（９）中其他 符号表示如下所述． １）首先初始化式（２）中存放Ｎｏｄｅ节点数据的二维 数组，初始化过程中将每个Ｎｏｄｅ分别根据ＤＥＭ数据计 算出每个Ｎｏｄｅ对应的数组坐标、经纬度、高度等信 息，需要说明的是如果当前初始化的节点是起点（Ｓｔａｒｔ Ｐｏｉｎｔ）￣ＪＪ此Ｎｏｄｅ的Ｆｌａｇ赋值为式（３）中的ＳＴＡＲＴＰＯＩＮＴ， 如果当前初始化节点是终点（ＥｎｄＰｏｉｎｔ）￣０￣ＬＮｏｄｅ的 Ｆｌａｇ赋值为式（３）中的ＤＥＳＴＩＮＡＴＩＯＮ，其他的节点 Ｆｌａｇ一律初始化为式（３）中的ＶＩＡＢＬＥ．从ＳｔａｒｔＰｏｉｎｔ开始 执行，并当做当前需要处理的节点存．Ｎ．ＯｐｅｎＬｉｓｔ． ２）从ＯＰｅｎＬｉｓｔ中取ｆ（ｎ）值最小的节点（如果 ＯｐｅｎＬｉｓｔｑｂ只有起点则为Ｓｔａ￣Ｐｏｉｎｔ）作为当前待处理的 节点如图４所示Ｃｅｎｔｅｒ．遍历Ｃｅｎｔｅｒ节点周围可以到达 图４处理节点Ｃｅｎｔｅｒ与遍历节点Ａ．Ｆ 的８个节点（图４中Ａ～Ｈ），如果发现这８个节点内已经出 现Ｆｌａｇ为ＤＥＳＴＩＮＡＴＩＯＮ的节点，终点找到，退出路径 搜索，执行步骤８． Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ软件技术・算法１４９ ， 表示Ａ～Ｈ中的被遍历到的节点 与终点Ｐ的水 饥系统 ｈｔｔｐ：／／ｗｗｗ．Ｃ—Ｓ—ａ．ｏｒｇ．ｃｎ ２０ｌ７年第２６卷第７期 ３实验 本文利用一片大致１０ ｋｍ＊ｌ０ ｋｍ，节点间隔５ ｍ的 ＤＥＭ数据，进行了大约５０组实验，每一组实验分别记录 了３ＤＢＡ＊算法与改进算法３ＤＡ＊算法的路径长度、平 均坡度、算法计算时间以及实验结果的效果图。 需要说明的是本文记录的路径长度是将利用式 （７）将空间距离根据坡度信息等效成水平距离后得出的 数据，最终本文评价所得路径长度的标准为： 『】 Ｓ＝∑（１＋１９．４６ｓｌｏｐｅ２） √【（墨一Ｘｉ—Ｉ） ＋（ —ｒｉ－１） 】 Ｉｎｔｅｒｖａｌ２＋（Ｚｉ—Ｚｉ一１） （１２） ｌｔ Ｌｓｌｏｐｅ，为 点ｉ与节点ｉ一１之问的坡度正切值，Ｉｎｔｅｒｖａｌ ５０软件技术・算法Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ 在本实验中如果不在图４对角节点时为５ ｍ，否则乘１．４ 为７ ｍ． 本文记录的路径平均坡度就是计算得出的轨迹点 串相邻点的坡度正切值累加和再除以点数取均值得出 的数据，本文评价所得路径坡度的标准为： ＂一ｌ∑ ‘—一２ ｌｏ腑０３） 本文记录的算法计算时问即从开始搜素到搜索结 束找到终点程序运行的时间． ３．１实验效果分析 实验的效果图如图５所示，点线代表原始３ＤＢＡ＊算 法结果，实线代表本文改进的３ＤＡ＊算法，图下方定位 点代表起点，图上方定位点代表终点．本文从实验结果 中任意截取了两幅上坡的路径（ａ）（ｂ）与两组下坡的路径 图（ｃ）（ｄ），效果图如图５所示． 【｝ ， ．｝＾． ／／ ＼ （ｃ）Ｆ坡路径１ （ｄ）下坡路径２ 图５实验效果图 从实验结果效果图直观分析，３ＤＢＡ＊的点线路径 大多没有顾及到山坡的陡峭性，本文的算法所得出的 实线路径相对较为平缓，且基本避开了较为陡峭的山 坡转而寻找较为平缓且距离相对最近的路． ３．２实验数据分析 本文根据实验所得的５０组结果数据进行统计，将 最终的结果分别按路径从小到大的进行显示，并用 ＥＸＣＥＬ软件做出数据走向的趋势． （１）算法所得路径长度 ２０１７年第２６卷第７期 ｈｔｔｐ：Ｈ￣ｖｗ．Ｃ－Ｓ—ａ．ｏｒｇ．ｃｎ 计。算机系统应用 ８ 啪咖咖 咖咖咖咖咖ｏ ６ ４ ２ Ｏ ８ ６ ４ ２ 路径长度统计 从图８统计数据来观察，两种算法的计算时间有大 有小，很难分清哪种算法用的时间少．但是，由于本文 将数据根据路径长度由小到大的顺序重新进行了统计， 本文通过ＥＸＣＥＬ软件做出的虚线代表的趋势线可以看 出，改进算法在范围较小的区域内搜索路径时，搜索时 间大于原始算法的搜索时间，但随着搜索范围的增大， １ ３ ５ ７ ９ ｌ１ １３ １５１７ １９２１ ２３２５２７２９ ３１ ３３３５３７３９４１ ４３４５４７４９ 本文的改进算法搜索的时间有小于原始算法搜索时间 一…改进算法路径长度 一原始算法路径长度 线性（改进算法路径长度）…－“线性（原始算法路径长度） 的趋势．此外，从数据上看，本算法寻找路径的范围在 方圆１０公里左右，在这个范围内算法所用的时间基本 上小于１２００ ｍｓ，在这样复杂的地形环境下，算法时间 基本可以忍受． 图６路径长度统计 由图６可以看出，实体曲线代表的原始算法计算出 的等效水平路径长度几乎总是在改进算法路劲长度的 上方，从虚线代表的各自趋势线也可以看出，两种算法 最终算出的路径长度几乎相等，但总的趋势是改进算 法稍优一点． （２）算法所得路径平均坡度 平均坡度统计 Ｏ．３ Ｏ．２５ ０．２ ０．１５ ４总结 本文着眼于三维实景地图，并针对于地形较为复 杂的山地，在传统Ａ 最优路径搜索算法的基础上。经过 改进得出一种适合于山地行走的最优路径搜索算法． 本改进算法通过将有坡度的路径空间距离等效为水平 距离重新定义了评价路径长短的标准，并通过此标准 记录算法实际走过的路程，与此同时本文充分考虑了 搜索点周围环境的整体坡度信息作为启发信息，来降 低算法寻找的路径走在陡坡上的概率．通过实验可以 看出，本文的改进算法较之基础算法，整体坡度更为平 缓，等效为水平路径的长度比基础算法稍短，算法运算 时间随着搜索范围的增大有小于基础算法的趋势．综 合以上内容，本文可以得出结论：本文的算法在针对山 Ｏ．１ Ｏ．０５ Ｏ ｌ ３ ５ ７ ９ ｉｌ １３ ｌ５ｌ７ ｌ９ ２ｌ ２３ ２５２７２９ ３ｌ ３３３５ ３７ ３９ ４１ ４３４５４７４９ ＿一一－改进算法平均坡度 一原始算法平均坡度 线性（改进算法平均坡度）・・・・・线性（原始算法平均坡度） 图７平均坡度统计 地这一类地势较为复杂的三维地形时能够搜索出一条 坡度适于人行走，距离较短的路径，且在方圆１０公里这 样的范围内搜索时间对于人来说能够接受． 参考文献 １张栋海，韩丽华，肖雄兵，等．导航地图发展现状和趋势分 析．地理信息世界，２０１３，２Ｏ（２）：２０－２３，３６． 由图７可以看出，原始算法的平均坡度除极少数情 况小于改进算法，其他绝大部分情况明显大于改进算 法的平均坡度，由此也可以说明本算法寻找出的路径 明显要平缓很多，更适合人行走的要求． （３）算法搜索时间 算法时间统计 １２ｏ０ ｌＯｏｏ ２王俊．面向智能交通的路径规划相关技术研究『硕士学位 １０００ ９００ ８００ ７００ ６００ ５００ ４００ ３００ ２００ １００ ０ 论文】．南京：南京大学，２０１３． ３王弋．基于高程环境与蚁群算法的三维路径规划研究ｆ硕 士学位论文１．西安：西安工业大学，２０１４． ８００ ６ＯＯ ４ｏｏ ２００ Ｏ ４黄玲，胡蔚蔚．基于改进蚁群算法的果蔬采摘机器人三维 路径规划．农机化研究，２０１６，（９）：３８＿４２． ５黄劲潮．一种基于改进蚁群算法的山地三维路径规划算 法．荆楚理工学院学报，２０１４，２９（２）：４０—４４． ６郝燕玲，张京娟．基于遗传算法的ＡｕＶ三维海底路径规划． 中国工程科学，２００３，５（１ １）：５６－６０．［ｄｏｉ：１０．３９６９￣．ｉｓｓｎ． Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ￣Ａｌｇｏｒｉｔｈｍ软件技术－算法１５１ ｌ ３ ５ ７ ９ Ｉｌｌ３ｌ５ｌ７ １９２１２３２５２７２９３１３３３５ ３７３９４ｌ４３４５４７４９ ＿ＩＩＩＩ￥ｍＩ改进算法时间 一原始算法时间 线性（改进算法时间） ・・・・・线性（原始算法时间） 图８算法时间统计 计算机系统应用 ｈｔ￣：ｌｌｗｗｗ．ｃ・ｓ—ａ．ｏｒｇ．ｅｌｌ ２０１７年第２６卷第７期 １００９—１７４２．２００３．１ １．００８】 游戏中的应用研究．电子设计工程，２０１４，２２（１４）：３７—３９， ４２．【ｄｏｉ：１０．３９６９￣．ｉｓｓｎ．１６７４－６２３６．２０１４．１４．０１２】 ７张航，刘梓溪．基于量子行为粒子群算法的微型飞行器三维 路径规划．中南大学学报（自然科学版），２０１３，４４（Ｓ２）：５８－－６２． １３崔振兴，顾治华．基于Ａ＋算法的游戏地图最短路径搜索． 软件导刊，２００７，（１７）：１４５—１４７． ８李挚，宋顶立，张双江，等．两种改进的最优路径规划算法． 北京科技大学学报，２００５，２７（３）：３６７－３７０． ９陈春梅．无人机快速三维航迹规划算法的研究『硕士学位 论文１．成都：电子科技大学，２０１５． １４石俊卫，包世泰，冯煜．基于Ａ 算法的山地最优路径分析． 现代计算机，２０１３，（１４）：９－１ Ｉ，１５． １５ Ｃｈｉｏｕ ＣＲ，Ｔｓａｉ ＷＬ，Ｌｅｕｎｇ ＹＦ．Ａ ＧＩＳ—ｄｙｎａｍｉｃ １ｏ王鹏程。夏洁．基于特殊双向Ａ・搜索算法的三维航迹规划． 系统仿真学报，２００９，２０（增ＴｔＪ）：２２９－２３３． １ １邱磊．利用跳点搜索算法加速Ａ 寻路．兰州理工大学学报， ２０１５，４ｌ（３）：１０２—１０７． １２祁悦，赵洋，杨帆．一种基于Ａ 算法的分层路径规划在３Ｄ １ ５２软件技术・算法Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅ・Ａｌｇｏｒｉｔｈｍ ｓｅｇｍｅｎｔａｔｉｏｎ ａｐｐｒｏａｃｈ ｔｏ ｐｌａｎｎｉｎｇ ｔｒａｖｅｌ ｒｏｕｔｅｓ ｏｎ ｆｏｒｅｓｔ ｔｒａｉｌ ｎｅｔｗｏｒｋｓ ｉｎ Ｃｅｎｔｒａｌ Ｔａｉｗａｎ．Ｌａｎｄｓｃａｐｅ ａｎｄ Ｕｒｂａｎ Ｐｌａｎｎｉｎｇ，２０１０，９７（４）：２２１－２２８．［ｄｏｉ：１０．１０１６￣．１ａｎｄｕｒｂｐｌａｎ． ２０１０．０６．００４１
