环路中一条路径已占用找出不同路径算法有哪些

软件 2024-07-25

最短路径算法

最短路径的算法主要有三种：floyd算法、Dijkstra算法、Bellman-Ford(贝尔曼-福特)

一、floyd算法

基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。

二、Dijkstra算法

算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

执行过程如图所示：

三、Bellman-Ford(贝尔曼-福特)

算法的流程如下：

给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，

1.数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；

2.以下操作循环执行至多n-1次，n为顶点数：
对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

3.为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说该图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

最短路径四大算法

最短路径问题是图论中的经典问题，常用的最短路径算法有Dijkstra算法、贝尔曼福特算法、弗洛伊德算法、A算法。

Dijkstra算法Dijkstra's Algorithm：Dijkstra算法用于求解单源最短路径问题，即从给定起点到其它所有节点的最短路径。它通过逐步扩展路径长度来不断确定当前距离起点最近的节点，并更新其它节点的距离值，直到找到所有节点的最短路径。

贝尔曼福特算法Bellman-Ford Algorithm：贝尔曼-福特算法用于求解单源最短路径问题，包括处理带有负权边的图。它通过对所有边进行松弛操作，反复迭代修改节点的距离值，直到找到最短路径或检测到负权环。

弗洛伊德算法Floyd-Warshall Algorithm：弗洛伊德算法用于求解全源最短路径问题，即找出任意两个节点之间的最短路径。它通过动态规划的思想，维护一个距离矩阵，依次考虑经过不同中间节点的路径，不断更新距离矩阵，最终得到所有节点之间的最短路径。

A算法AStar Algorithm：A算法用于在具有启发式函数的图中求解单源最短路径问题。它在搜索过程中综合考虑了从起点到目标节点的启发式估计值和实际已走路径的代价，通过优先级队列的机制选择最有希望的节点进行扩展，以提高搜索效率。

最短路径问题的应用领域

1、导航系统：最短路径算法被广泛应用于导航系统中，帮助用户找到从起点到目标地点的最短路径。这可以用于驾车导航、步行导航以及公共交通导航等。

2、物流规划：在物流和运输领域，最短路径算法被用来规划货物的运输路线，以最小化运输成本和时间。这样可以提高物流效率，降低运输成本，并确保货物按时到达目的地。

3、网络路由：在计算机网络中，最短路径算法用于确定数据包在网络中的传输路径，以确保数据能够快速且高效地到达目标节点。例如，路由器会使用最短路径算法来选择下一跳的路由器。

路径规划详细资料大全

路径规划是运动规划的主要研究内容之一。运动规划由路径规划和轨迹规划组成，连线起点位置和终点位置的序列点或曲线称之为路径，构成路径的策略称之为路径规划。

路径规划在很多领域都具有广泛的套用。在高新科技领域的套用有：机器人的自主无碰行动；无人机的避障突防飞行；巡航飞弹躲避雷达搜寻、防反弹袭击、完成突防爆破任务等。在日常生活领域的套用有：GPS导航；基于GIS系统的道路规划;城市道路网规划导航等。在决策管理领域的套用有：物流管理中的车辆问题(VRP)及类似的资源管理资源配置问题。通信技术领域的路由问题等。凡是可拓扑为点线网路的规划问题基本上都可以采用路径规划的方法解决。

基本介绍

中文名：路径规划
外文名：Path Planning
类目：电子信息技术
套用领域：高科技、日常生活、物流管理等
常用算法：Dijkstra算法、遗传算法等

路径规划问题分类,路径规划的一般步骤,常用算法,传统算法,图形学的方法,智慧型仿生学算法,路径规划套用,离散域范围内的最短路径规划问题,离散域范围内的遍历式最优路径问题,连续域范围内的全局路径规划问题,连续域范围内的局部路径规划问题,连续域范围内的遍历式路径规划问题,路径规划的未来发展,

路径规划问题分类

根据对环境信息的把握程度可把路径规划划分为基于先验完全信息的全局路径规划和基于感测器信息的局部路径规划。其中，从获取障碍物信息是静态或是动态的角度看，全局路径规划属于静态规划(又称离线规划)，局部路径规划属于动态规划(又称线上规划)。全局路径规划需要掌握所有的环境信息，根据环境地图的所有信息进行路径规划；局部路径规划只需要由感测器实时采集环境信息，了解环境地图信息，然后确定出所在地图的位置及其局部的障碍物分布情况，从而可以选出从当前结点到某一子目标结点的最优路径。根据所研究环境的信息特点，路径规划还可分为离散域范围内的路径规划问题和连续域范围内的路径规划问题。离散域范围内的路径规划问题属于一维静态最佳化问题，相当于环境信息简化后的路线最佳化问题；而连续域范围内的路径规划问题则是连续性多维动态环境下的问题。

路径规划的一般步骤

一般的连续域范围内路径规划问题，如机器人、飞行器等的动态路径规划问题，其一般步骤主要包括环境建模、路径搜寻、路径平滑三个环节。（1）环境建模。环境建模是路径规划的重要环节，目的是建立一个便于计算机进行路径规划所使用的环境模型，即将实际的物理空间抽象成算法能够处理的抽象空间，实现相互间的映射。（2）路径搜寻。路径搜寻阶段是在环境模型的基础上套用相应算法寻找一条行走路径，使预定的性能函式获得最优值。（3）路径平滑。通过相应算法搜寻出的路径并不一定是一条运动体可以行走的可行路径，需要作进一步处理与平滑才能使其成为一条实际可行的路径。对于离散域范围内的路径规划问题，或者在环境建模或路径搜寻前己经做好路径可行性分析的问题，路径平滑环节可以省去。

常用算法

路径规划的方法有很多，根据其自身优缺点，其适用范围也各不相同。根据对各领域常用路径规划算法的研究，按照各种算法发现先后时序及算法基本原理，将算法大致分为四类:传统算法、图形学的方法、智慧型仿生学算法和其他算法。

传统算法

传统的路径规划算法有：模拟退火算法、人工势场法、模糊逻辑算法、禁忌搜寻算法等。（1）模拟退火算法（Simulated Annealing），简称SA)是一种适用于大规模组合最佳化问题的有效近似算法。它模仿固体物质的退火过程，通过设定初温、初态和降温率控制温度的不断下降，结合机率突跳特性，利用解空间的邻域结构进行随机搜寻。具有描述简单、使用灵活、运行效率高、初始条件限制少等优点，但存在着收敛速度慢、随机性等缺陷，参数设定是套用过程中的关键环节。（2）人工势场法是一种虚拟力法。它模仿引力斥力下的物体运动，目标点和运动体间为引力，运动体和障碍物间为斥力，通过建立引力场斥力场函式进行路径寻优。优点是规划出来的路径平滑安全、描述简单等，但是存在局部最优的问题，引力场的设计是算法能否成功套用的关键。（3）模糊逻辑算法网模拟驾驶员的驾驶经验，将生理上的感知和动作结合起来，根据系统实时的感测器信息，通过查表得到规划信息，从而实现路径规划。算法符合人类思维习惯，免去数学建模，也便于将专家知识转换为控制信号，具有很好的一致性、稳定性和连续性。但总结模糊规则比较困难，而且一旦确定模糊规则线上调整困难，应变性差。最优的隶属度函式、控制规则及线上调整方法是最大难题。（4）禁忌搜寻算法（TS）是一种全局逐步寻优算法，是对人类智力过程的一种模拟。通过引入一个灵活的存储结构和相应的晋级规则来避免与会搜寻，并通过藐视准则来赦免一些被紧急的优良状态，以实现全局最佳化。

图形学的方法

传统算法在解决实际问题时往往存在着建模难的问题，图形学的方法则提供了建模的基本方法，但是图形学的方法普遍存在着搜寻能力的不足，往往需要结合专门的搜寻算法。图形学的方法有：C空间法、栅格法、自由空间法、voronoi图法等。（1）C空间法又称可视图空间法，即在运动空间中扩展障碍物为多边形，以起始点、终点和所有多边形顶点间的可行直线连线（ *** 过障碍物的连线）为路径范围来搜寻最短路径。C空间法的优点是直观，容易求得最短路径；缺点是一旦起始点和目标点发生改变，就要重新构造可视图，缺乏灵活性。即其局部路径规划能力差，适用于全局路径规划和连续域范围内的路径规划。尤其适用于全局路径规划中的环境建模。（2）自由空间法针对可视图法应变性差的缺陷，采用预先定义的基本形状（如广义锥形，凸多边形等）构造自由空间，并将自由空间表示为连通图，然后通过对图的搜寻来进行路径规划。由于起始点和终点改变时，只相当于它们在己构造的自由空间中位置变化，只需重新定位，而不需要整个图的重绘。缺点是障碍物多时将加大算法的复杂度，算法实现困难。（3）栅格（grid）法，即用编码的栅格来表示地图，把包含障碍物的栅格标记为障碍栅格，反之则为自由栅格，以此为基础作路径搜寻。栅格法一般作为路径规划的环境建模技术来用，作为路径规划的方法它很难解决复杂环境信息的问题，一般需要与其他智慧型算法相结合。（4） voronoi图是关于空间邻近关系的一种基础数据结构。它是用一些被称为元素的基本图形来划分空间，以每两点间的中垂线来确定元素的边，最终把整个空间划分成结构紧凑的voronoi图，而后运用算法对多边形的边所构成的路径网进行最优搜寻。优点是把障碍物包围在元素中，能实现有效避障，缺点图的重绘比较费时，因而不适用于大型动态环境。

智慧型仿生学算法

处理复杂动态环境信息情况下的路径规划问题时，来自于自然界的启示往往能起到很好的作用。智慧型仿生学算法就是人们通过仿生学研究，发现的算法，常用到的有:蚁群算法、神经网路算法、粒子群算法、遗传算法等。（1）蚁群算法，（Ant Colony Algorithm简称ACA）的思想来自于对蚁群觅食行为的探索，每个蚂蚁觅食时都会在走过的道路上留下一定浓度的信息素，相同时间内最短的路径上由于蚂蚁遍历的次数多而信息素浓度高，加上后来的蚂蚁在选择路径时会以信息素浓度为依据，起到正反馈作用，因此信息素浓度高的最短路径很快就会被发现。算法通过叠代来模拟蚁群觅食的行为达到目的。具有良好的全局最佳化能力、本质上的并行性、易于用计算机实现等优点，但计算量大、易陷入局部最优解，不过可通过加入精英蚁等方法改进。（2）神经网路算法是人工智慧领域中的一种非常优秀的算法，它主要模拟动物神经网路行为，进行分散式并行信息处理。但它在路径规划中的套用却并不成功，因为路径规划中复杂多变的环境很难用数学公式进行描述，如果用神经网路去预测学习样本分布空间以外的点，其效果必然是非常差。尽管神经网路具有优秀的学习能力，但是泛化能力差是其致命缺点。但因其学习能力强鲁棒性好，它与其他算法的结合套用己经成为路径规划领域研究的热点。（3）遗传算法（Geic Algorithms，简称GA）是当代人工智慧科学的一个重要研究分支，是一种模拟达尔文遗传选择和自然淘汰的生物进化过程中的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是按照基因遗传学原理而实现的一种叠代过程的搜寻算法。最大的优点是易于与其他算法相结合，并充分发挥自身叠代的优势，缺点是运算效率不高，不如蚁群算法有先天优势，但其改进算法也是目前研究的热点。

路径规划套用

路径规划的套用领域非常广泛，如：机器人机械臂的路径规划、飞行器航迹规划、巡航飞弹路径规划、旅行商问题（TSP）以及其衍生的各种车辆（VRP）路径规划、虚拟装配路径规划、基于道路网的路径规划、电子地图GPS导航路径搜寻与规划、路由问题等。

离散域范围内的最短路径规划问题

属于离散域范围内最短路径规划的问题有：基于道路网的路径规划问题、电子地图CPS导航路径搜寻规划问题、路由问题等。（1）基于道路网和基于电子地图GPS导航的路径规划都可视作基于GIS (Geographical Information System)的路径规划问题。这些问题的解决都是从复杂的数据信息中提取出所需道路信息，以路口为节点，道路信息为路径信息，构造出复杂的路径信息拓扑网路，将起始点和目标点定位为这个拓扑网路上两个节点，而后运用路径搜寻算法进行最短路径寻优规划。（2）路由问题属于通信技术领域研究的重点。路由问题的主要功能是使数据信息顺利地从源节点传送到目标节点。根据Qos的设计需求，可在路径上设定不同的权重，定义路径参数。在网路拓扑结构中稳定高效地搜寻最优路径，快速聚合。实时地进行网路拥堵控制，根据具体情况进行动态路由选择。（3）从最短路径规划的角度看，这一类问题的特点大同小异，都是在己知路径信息(节点数，路径参数信息，拓扑结构等)情况下，从己知起始节点到目标节点的最优路径路径规划问题，路径信息多为静态信息，即使有信息变动，智慧型算法也有足够的能力进行及时的应变规划。常用的算法有：Dijkstra算法、A*搜寻算法、模拟退火算法、蚁群算法、遗传算法、粒子群算法、Floyd算法、Fallback算法等。

离散域范围内的遍历式最优路径问题

属于离散域范围内遍历式最优路径的问题有：虚拟装配路径规划、旅行商问题(TSP)以及其衍生的各种车辆问题(VRP)和物流问题等。由于虚拟装配路径规划的核心是装配序列规划问题，而序列规划问题属于典型的TSP问题。这类问题的一般特点是:己知路径信息为静态信息，对于脚踏车辆问题，起始点唯一，最终目标节点为起始点，中间有多个子目标节点。要求车辆以最短的路径从起始点出发，遍历所有子目标节点后，回到起始点。当然，有的问题是以最短时间或最少费用等为规划目标，这样的路径规划问题可把相应路径信息调整为路径时间信息或路径费用信息，对应节点不变。此外，也有多车辆、多起点、考虑载重等因素的整体调控问题，此类问题是基于脚踏车辆路径规划问题的延展套用。解决此类路径问题的常用智慧型算法有：蚁群算法、禁忌搜寻算法、模拟退火算法、神经网路算法、遗传算法、粒子群算法等。

连续域范围内的全局路径规划问题

属于连续域范围内全局路径规划图的问题有:机器人机械臂自主移动路径规划、无人机飞行器航迹规划、巡航飞弹航迹规划等。从路径规划角度来看，这类问题都是己知环境信息，且环境信息为静态信息的情况下，如何在安全范围内避开障碍物找到到达目的地的最短路径问题。解决此类问题通常依靠智慧型算法与环境建模结合使用。直接套用于此类问题的路径规划算法有：可视图法、自由空间法、Voronoi图法、栅格法、惩罚函式法、模拟退火算法等。间接套用的智慧型算法有：A*搜寻算法、蚁群算法、遗传算法、粒子群算法、人工势场法等。

连续域范围内的局部路径规划问题

连续域范围内的局部路径规划和全局路径规划套用领域基本相同，它们在其套用领域内而对的环境不同，解决的问题也不同。局部规划而对的是动态的实时的环境信息，属于线上规划，对算法要求实时性好、高效、稳定，是目前研究的热点。套用于此类问题的路径规划算法有：蚁群算法、遗传算法、粒子群算法、A*搜寻算法、人工势场法、量子粒子群算法、神经网路算法等。

连续域范围内的遍历式路径规划问题

连续域范围内的遍历式路径规划主要套用于：清洁机器人、草坪修剪机、扫雷机器人、搜救机器人、矿藏探测器等。其特点是：机器人需用最短的路径去覆盖所工作区域的每个角落，要求最大的覆盖率和最小的重复率。解决此类问题需先进行环境建模，最常用的方法是栅格法，后来Neumann de Carvalho R等人发明了模板模型法。解决此类问题的常用算法有:神经网路算法、A*算法、遗传算法、粒子群算法、蚁群算法等。

路径规划的未来发展

随着科学技术的不断发展，路径规划技术而对的环境将更为复杂多变。这就要求路径规划算法要具有迅速回响复杂环境变化的能力。这不是目前单个或单方而算法所能解决问题，因此在未来的路径规划技术中，除了研究发现新的路径规划算法外，还有以下几方而值得关注：（1）先进路径规划算法的改进。任何一种算法在实际套用过程中都要而对诸多困难，特别是自身的局限性。例如：A*算法作为一种启发式搜寻算法具有鲁棒性好，快速回响的特点，但是套用于实际中还是存在弊端，对于A*算法套用于无人机航迹规划时的弊端，李季等提出了改进A*算法，解决了A*算法难以满足直飞限制并且有飞机最小转弯半径等约束的局限性这一问题。（2）路径规划算法的有效结合（即混合算法）。任何的单一路径规划算法都不可能解决所有实际套用中的路径规划问题，特别是在而对交叉学科的新问题时，研究新算法的难度大，路径规划算法间的优势互补为解决这一问题提供了可能。对于多空间站路径规划问题，金飞虎等把蚁群算法和神经网路方法相结合解决了这一问题，并避免了单纯运用神经网路算法时出现的局部最小问题。（3）环境建模技术和路径规划算法的结合。而对复杂的二维甚至三维连续动态环境信息时，算法所能做的是有限的，好的建模技术和优秀路径规划算法相结合将成为解决这一问题的一种方法。如栅格法和蚁群算法的结合， C空间法和Dijkstra算法的结合等。（4）多智慧型体并联路径规划算法设计。随着科学技术的套用发展，多智慧型体并行协作己经得到套用。其中，多机器人协作和双机械臂协作中的路径冲突问题日渐为人们所关注，如何实现其无碰路径规划将成为日后研究的热点之一。

路径分析的最优路径分析方法

1．道路预处理
进行道路数据录入时，往往在道路的交叉接合处出现重叠或相离的情况，不宜计算机处理。因此，需要对原始数据进行预处理，使道路接合符合处理要求。进行预处理时，取每条线段的首末节点坐标为圆心，以给定的阈值为半径作圆域，判断其他线段是否与圆域相交，如果相交，则相交的各个线对象共用一个节点号。
2．道路自动断链
对道路进行预处理之后即可获得比较理想的数据，在此基础上再进行道路的自动断链。步骤如下：
（1）取出所有线段记录数n，从第一条线段开始；
（2）找出所有与之相交的线段并求出交点数m；
（3）将m个交点和该线段节点在判断无重合后进行排序；
（4）根据交点数量，该线段被分成m+1段；
（5）第一段在原始位置不变，后m段从记录尾开始递增；
（6）重复（2）～（5），循环至n。
3．节点匹配
拓扑关系需使用统一的节点。节点匹配方法是按记录顺序将所有线段的始末点加上相应节点号，坐标相同的节点共用一个节点号，与前面所有线段首末点都不相同的节点按自然顺序递增1。
4．迪杰克斯特拉（Dijkstra）算法
经典的图论与计算机算法的有效结合，使得新的最短路径算法不断涌现。目前提出的最短路径算法中，使用最多、计算速度比较快，又比较适合于计算两点之间的最短路径问题的数学模型就是经典的Dijkstra算法。
该算法是典型的单源最短路径算法，由Dijkstra EW于1959年提出，适用于所有弧的权均为非负的情况，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。该算法的基本思想是：认为两节点间最佳路径要么是直接相连，要么是通过其他已找到的与起始点的最佳路径的节点中转点。定出起始点P0后，定能找出一个与之直接相连且路径长度最短的节点，设为P1，P0到P1就是它们间的最佳路径。
Dijkstra算法的基本流程如下：首先将网络中所有节点分成两组，一组包含了已经确定属于最短路径中点的集合，记为S（该集合在初始状态只有一个源节点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了）；另一组是尚未确定最短路径的节点的集合，记为V，按照最短路径长度递增的次序依次把第二组的顶点加入到第一组中，在加入的过程中总保持从源点到S中各顶点的最短路径长度不大于从源点到V中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点距离就是从源点到此顶点的最短路径长度，V中的顶点距离是从源点到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。