基于方向距离顺序处理的路线优选算法改进-论文.pdf

《基于方向距离顺序处理的路线优选算法改进-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ISSN1009-3044E—mail：eduf@dnzs．net．cnComputerKnowledgeandTechnology电脑知识与技术http：／／www．dnzs．net．cnVo1．10，No．13，May2014Teh+86—55】-6569096365690964====：?—==!=：=：======——====—一=======：—=!====：=：=========——=======：====：基于方向距离顺序处理的路线优选算法改进柴文国，唐波(困防科学技术大学电子科学与T程学院，湖

2、南长沙410073)摘要：介绍了从距离和方向角度出发对最短路径算法进行了优化，提出障碍物规避原则基础上的路线选择办法，从距离优化和方向优化着手依据路径选择的特点，形成促成算法改进的基本思想和原理。阐述了优化后算法的实现过程和原理，最后通过实例证明了优化后的算法便于使用，提高了计算效率。关键词：经典算法；路径选择；距离；方向；算法优化中图分类号：TP311文献标识码：A文章编号：1009—3044(20l4)13—3ll9—05经典的Dijkstra算法将实际交通路径划分为节点和弧，在模拟交通路径时，这些弧的权

3、值可以表示最优路径，从初始点至最优点，所有路径的连线可以表示为一个大树，起点就是大树的根，所有从树根到各节点的权值最小，最短路径即为最优路径。没有明确的方向性。Dijkstra算法思想是在搜索过程中对搜索的节点进行归类，所有节点中，只有已经搜索过的和没有搜索的两类节点，将搜索过不符合最优路径的节点排除。对已经搜索过的节点进行归类，盲目性很强，必须毫无遗漏的对所选对象进行一一排除。将区域内所有节点在搜索之前作为具有可通过性的。Oijkstra算法在搜索最优节点过程中，当图中某个或某些节点发生变化时，算法无法响应

4、这些变化，只能重新搜索整个图，重新求最优解，必然需要花费大量时间。如果没有最优路径，则搜索失败。本文紧密结合实际情况，在选择路线过程中依据方向优化和距离优化两种思想，对原有算法进行改进，提出了基于方向和距离的最短路径选择判断的改进。在实际工作中，对最优路径的选择，目的性是明确的，首先我们对起始点之间的可通过性进行判断，规避影响通过性的节点规避，其次排除靠近起始点连线方向的路径，最后对路径最短进行排序，从而得出最优路径。实际情况中，当搜索节点数量明显较多时，该文所提方法不仅能提高运算效率，还能获得较好的性能和效

5、果。1优化算法的思想选择最优路径的前提是确定已知的搜索范围，对搜索范围内的通行性进行判断。解决具体问题，我们寻求最短路径制定障碍物避让法则，引入方向优化和距离优化的思想。具体的原理是：确定搜索范围，对搜索范围栅格化，判断栅格单元格内的地形可通行性，对单元格内的可通行性进行判断，对可机动通行的区域进行判定，确定可通行的路径即为可通行结果。将以获知的搜索区域进行网格划分，将每一个单元格看作是一个节点，障碍物所在的区域会影响到网格的相邻数，每个单元格的相邻单元格个数为0—8个。起始点之外的所有单元格均可作为候选网格

6、。单元格被障碍物包围时不存在可能性，即没有可通过的单元格——节点。确定机动的起始点，将两点连线，作为参照路径，作为最优路径的选择标准。从起点单元格中心开始进行无障碍连线，以能联结至终点为作为满足选择条件的路径。可以与参照路径进行比较。筛除障碍物所占的单元格，确定能有效通过的单元格，对影响通过的单元格进行排除。对符合选择条件的单元格的连线路径进行排序，不相邻的单元格之间的距离为无穷大(被障碍阻断，无通过可能性)。规定存在可通过性相邻两个单元格的连距离为1个单位。最优路径的标准是能连接至终点，总单位数最靠近参考距

7、离的为满足条件的路径。2优化算法的过程Dijkstra算法对于国内外学者最短路径法的改进奠定了理论基础，《基于邻接点的最短路径算法》利用路径信息本身所具有距离和方向的属性特征，有效的实施了路径选择中对距离和方向的优化。2．1距离优化的基本思想以起始点所在的平面建立坐标系，可以得到起始点的坐标，起点和终点的直线距离是固定不变的，我们可以获得两点之间的空间距离。在Dijkstra算法中满足选择条件的距离有规律的不断发生变化，直线优化Dijkstra算法将候选节点到起始点最短距离的和作为算法的选取标准，在获取最短距

8、离的候选点的趋势中，缩小了选取范围，大大减少了选取点，在利用GIS数据的同时，提高了计算效率。GIS数据在遇到规则路径和投影数据时，优化效果不明显。Dijkstra距离优化示意图如图1所示，其中A为起始节点，B为终止节点，C、D分别为候选节点。收稿日期：2014—03—03本栏目责任编辑：唐一东人工智能及识另日技术⋯3119ComputerKnowledgeandTechnology电脑知识与技术第