基于Dijkstra算法的一种最短路径改进算法

本文在Dijkstra算法的基础上,增加了一些数据结构,提出一种能直观地求出从一个顶点到其它各顶点的所有最短路径的算法。     

一种适于车辆导航系统的快速路径规划算法

针对城市道路网图节点数较多,经典的求解最短路径的Dijkstra算法存在计算时间较长的问题.对矢量化的城市道路网图的特点进行分析,给出了道路网图的计算机存储结构,提出一种快速求解城市道路网两节点间的最短路径近似算法.算法的实现采用双向式搜索法、投影法和夹角最小的方法.理论分析和实验结果表明,和Dijkstra算法相比,该算法尽管有时得不到最优解,但能大大减小搜索空间,提高搜索速度,时间复杂性不超过O(N),适用于车辆导航系统.     

求最短路径问题的自适应路由遗传优化算法的设计与实现

从最短路径问题的研究背景、最短路径问题概述、求解最短路径问题的自适应路由遗传优化算法的设计及其实现等方面提出了一种新的求解最短路径问题的自适应路由遗传优化算法,实验仿真比较了该算法与Dijkstra算法的路由过程、算法的收敛性和执行的效率,结果初步证明该算法高效可行,尤其适合于大规模网络.     

一种限制搜索区域的最短路径改进算法

最短路径算法效率是许多应用领域普遍关注和迫切需要解决的问题。该文在深入分析经典Dijkstra最短路径算法优化途径的基础上,从控制路网规模入手,提出了矩形限制搜索区域的最短路径算法。根据路网分布的特点,采取比值系数分段取值的方法,进一步提高了算法效率。原型系统实验显示了改进算法的高效性和可行性。     

两种改进的最优路径规划算法

在对经典Dijkstra算法和A*算法分析的基础上对它们分别进行了改进.在经典Dijkstra算法中,针对当前不相连节点间路径长度为无穷大这一特点,首先对两个节点是否相连进行判断;若发现两个节点并不相连时,则舍去相应计算,从而减小计算量.针对A*算法在实际应用中搜索效率低的缺点,将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后,再按照经典A*算法搜索出相应的新最优路径,最后再将原始最优路径与这些新最优路径进行对比,以便确定最终的最优路径.仿真研究表明:改进的Dijkstra算法可以减少大量的无关节点计算,提高运算的效率;改进的A*算法则可以提高搜索到最优路径的成功率.     

一种基于遗传算法的机器人加工路径规划方法

针对传统机器人加工路径规划采用示教再现方法很难适应复杂变化任务的问题 ,提出了基于遗传算法的路径规划方法 ,研究了遗传算法中的编码方式、交叉算子和变异算子的改进方法 .仿真实验表明 ,采用遗传算法进行机器人加工路径规划是可行的和有效的 .     

动态环境中基于遗传算法的移动机器人路径规划的仿真

动态环境中 ,移动机器人的动态路径规划是一个较难解决的课题 .提出了一种基于遗传算法的移动机器人的路径规划方法 .该方法采用实数编码和有明确物理意义的适应度函数 ,可以加快实时的运算速度和提高运算精度 .同时 ,该方法充分挖掘了可应用遗传算法解决移动机器人动态路径规划的潜力 .计算机仿真表明 ,仿真该控制方法具有良好的动态路径规划能力     

求解路网最短路的快速算法

探讨了最短路算法在交通分配中的重要地位。在此基础上．比较了现有最短路算法的优缺点,同时提出了一种改进的矩阵迭代算法．并利用该算法对一简单路网进行了验证。     

复杂网络的优化模型及最短路径求解

对大型复杂网络提出网络分级的思想，根据网络分级的情况定义网络结点的数据结构，然后使用改进的Dijkstra算法和最小生成树算法来计算网络中任意两结点之间的最短路径．     

基于启发式策略的最短路径算法

在讨论经典Dijkstra算法和启发式策略算法（A^＊,矩形算法等）的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径．该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间．该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果．实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50％的搜索节点数和搜索时间．     

求解最短路径问题的一种改进的人工蜂群算法

针对传统算法在计算大规模路网的优化问题时所表现出来的计算时间长、存储空间大等缺点,提出了一种改进的人工蜂群算法来求解最优路径选择的方法．试验结果表明,对于有向图和无向图,该算法都具有较好的全局寻优能力,即能获得满足条件的最优路径．     

自适应遗传算法在移动机器人路径规划中的应用

将一种自适应遗传算法应用于移动机器人路径规划.提出了一种基于几何避障法的初始种群产生算法;设计了基于启发式知识的交叉、变异、求精和删除算子;采用一种新的模糊逻辑控制算法自适应地调节交叉概率和变异概率;对移动机器人离线和在线规划问题进行了仿真研究.仿真结果表明:自适应遗传算法具有较快的搜索速度、较高的搜索质量以及较强的自适应能力,为移动机器人最优路径规划问题的解决提供了一种新方法.     

迷宫问题的最短距离标记法递归求解

用标记每个搜索位置离起始位置最近距离的方法,通过递归函数求解,提出了一个对复杂迷宫的简明求解算法.求解结果给出了迷宫通道中所有各点离入口的最短距离、次短距离等有意义的批量信息.     

道路网络中门到门包含重复节点的最优路径算法

设计了具有交通约束的受限路网中,基于兴趣点(POI)的门到门包含重复节点的寻路算法。该算法首先利用距离最短准则建立POI和路网间的临时拓扑关系,然后根据受限路网中最优路径的结构特征,构造包含驶入路段的节点进行寻路拓展,以此为基础进行标记设定广度优先搜索,即可获得门到门包含重复节点的最优路径。在道路密度较大的北京市路网中的试验结果表明,该算法能够根据交通约束规划出实用的最优路径,对于长度约60km路径的计算平均耗时在3s左右,可以满足车辆导航应用的实时性要求。