两大主流路径算法

① 路由算法的类型有

路由算法有很多种，如果从路由表对网络拓扑和通信量变化的自适应能力的角度划分，可以分为静态路由算法和动态路由算法两大类，这两大类又可细分为几种小类型，比较典型常见的有以下几种：

一、静态路由算法

1.Dijkstra算法（最短路径算法）

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。

Dijkstra算法执行步骤如下：

步骤一：路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i,j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。

步骤二：路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：

前序字段———表示当前节点之前的节点。

长度字段———表示从源节点到当前节点的权值之和。

标号字段———表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。

步骤三：路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。

步骤四：路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。

步骤五：路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。

步骤六：路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。

步骤七：如果这个节点不是V2（目的节点），路由器则返回到步骤5。

步骤八：如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

2.扩散法
事先不需要任何网络信息；路由器把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。将来会有多个分组的副本到达目的地端，最先到达的，可能是走了“最优”的路径常见的扩散法是选择性扩散算法。

3.LS算法

采用LS算法时，每个路由器必须遵循以下步骤：

步骤一：确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息，其中包含它自身的IP地址。

步骤二：测量相邻路由器的延时（或者其他重要的网络参数，比如平均流量）。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，路由器便可以计算出延时。（路程往返时间是网络当前延迟的量度，通过一个分组数据包从远程主机返回的时间来测量。）该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。

步骤三：向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。

在这一步中，所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够知道网络的结构以及状态。

步骤四：使用一个合适的算法，确定网络中两个节点之间的最佳路由。

路由算法有哪些类型？路由算法与路由协议的区别

在这一步中，路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点，如Dijkstra最短路径算法。在这个算法中，一个路由器通过收集到的其他路由器的信息，建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注，称为权值或成本。这个数字是延时和平均流量的函数，有时它仅仅表示节点间的跃点数。例如，如果一个节点与目的地之间有两条链路，路由器将选择权值最低的链路。

二、动态路由算法

1.距离向量路由算法

距离向量路由算法，也叫做最大流量算法，其被距离向量协议作为一个算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量，等等。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。其优点是算法简单容易实现。缺点是慢收敛问题，路由器的路径变化需要像波浪一样从相邻路由器传播出去，过程缓慢。

每一个相邻路由器发送过来的路由表都要经过以下步骤：

步骤一：对地址为X的路由器发过来的路由表，先修改此路由表中的所有项目：把”下一跳”字段中的地址改为X，并把所有”距离”字段都加1。

步骤二：对修改后的路由表中的每一个项目，进行以下步骤：

（1）将X的路由表(修改过的)，与S的路由表的目的网络进行对比。若在X中出现，在S中没出现，则将X路由表中的这一条项目添加到S的路由表中。

（2）对于目的网络在S和X路由表中都有的项目进行下面步骤：

1）在S的路由表中，若下一跳地址是x，则直接用X路由表中这条项目替换S路由表中的项目。

2）在S的路由表中，若下一跳地址不是x，若X路由表项目中的距离d小于S路由表中的距离，则进行更新。

步骤三：若3分钟还没有收到相邻路由器的更新表，则把此相邻路由器记为不可到达路由器，即把距离设置为16。

2.链路状态最短路由优先算法SPF

1）发现邻居结点，并学习它们的网络地址；

2）测量到各邻居节点的延迟或者开销；

3）创建链路状态分组；

4）使用扩散法发布链路状态分组；

5）计算到每个其它路由器的最短路径。

② 图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：

常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决着名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：

注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进

第2步 ：选取顶点 添加进 ，更新 中顶点最短距离

第3步 ：选取顶点 添加进 ，更新 中顶点最短距离

第4步 ：选取顶点 添加进 ，更新 中顶点最短距离

第5步 ：选取顶点 添加进 ，更新 中顶点最短距离

第6步 ：选取顶点 添加进 ，更新 中顶点最短距离

第7步 ：选取顶点 添加进 ，更新 中顶点最短距离

示例：node编号1-7分别代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：

示例：

找到D（4）到G（7）的最短路径：

[1] 维基网络，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

③ 常见的路由选择算法有哪些

链路状态算法（也称最短路径算法）发送路由信息到互联网上所有的结点，然而对于每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面，链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些。除了这些区别，两种算法在大多数环境下都能很好地运行。

④ 最短路径算法

Dijkstra算法，A*算法和D*算法

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。

提高Dijkstra搜索速度的方法很多，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。

A*（A-Star)算法是一种启发式算法，是静态路网中求解最短路最有效的方法。

公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}

A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。

动态路网，最短路算法 D*A* 在静态路网中非常有效（very efficient for static worlds），但不适于在动态路网，环境如权重等不断变化的动态环境下。

D*是动态A*（D-Star,Dynamic A*） 卡内及梅隆机器人中心的Stentz在1994和1995年两篇文章提出，主要用于机器人探路。是火星探测器采用的寻路算法。

主要方法：
1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。
原OPEN和CLOSE中节点信息保存。
2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y->X->G），Y是当前点。k值取h值变化前后的最小。
3.用A*或其它算法计算，这里假设用A*算法,遍历Y的子节点，点放入CLOSE,调整Y的子节点a的h值，h(a)=h(Y)+Y到子节点a的权重C(Y,a),比较a点是否存在于OPEN和CLOSE中，方法如下：
while()
{
从OPEN表中取k值最小的节点Y;
遍历Y的子节点a,计算a的h值 h(a)=h(Y)+Y到子节点a的权重C(Y,a)
{
if(a in OPEN) 比较两个a的h值
if( a的h值小于OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影响的最短路经存在
break;
}
if(a in CLOSE) 比较两个a的h值 //注意是同一个节点的两个不同路径的估价值
if( a的h值小于CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;将a节点放入OPEN表
有未受影响的最短路经存在
break;
}
if(a not in both)
将a插入OPEN表中; //还没有排序
}
放Y到CLOSE表；
OPEN表比较k值大小进行排序；
}
机器人利用第一步Dijstra计算出的最短路信息从a点到目标点的最短路经进行。

D*算法在动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。

⑤ 有哪些应用于移动机器人路径规划的算法

机器人家上了解到，在二维二值地图（FREE or OCCUPIED）场景下进行路径规划的方法。我看之前有同学在回答的时候配上了这幅图：

这幅图上的算法罗列的还是很全面的，体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类，下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类：

这幅图上的算法罗列的还是很全面的，体现了各个算法的出生顺序。但是并不能很好的对他们进行一个本质的分类。刚刚那位同学说的graph-based和sampling-based的分类方法我感觉有点概念重叠不能够对规划算法进行这样的分类，下面通过自己这一年多的研究和实践对规划算法进行一个简单的分类：

两大类：
1. 完备的（complete)
2. 基于采样的（sampling-based）又称为概率完备的

一 完备的规划算法

A*算法

所谓完备就是要达到一个systematic的标准，即：如果在起始点和目标点间有路径解存在那么一定可以得到解，如果得不到解那么一定说明没有解存在。
这一大类算法在移动机器人领域通常直接在occupancy grid网格地图上进行规划（可以简单理解成二值地图的像素矩阵）以深度优先寻路算法、广度优先寻路算法、Dijkstra(迪杰斯特拉)算法为始祖，以A*算法(Dijstra算法上以减少计算量为目的加上了一个启发式代价)最为常用，近期的Theta*算法是在A*算法的基础上增加了line-of-sight优化使得规划出来的路径不完全依赖于单步的栅格形状（答主以为这个算法意义不大，不就是规划了一条路径再简单平滑了一下么）。
完备的算法的优势在与它对于解的捕获能力是完全的，但是由此产生的缺点就是算法复杂度较大。这种缺点在二维小尺度栅格地图上并不明显，但是在大尺度，尤其是多维度规划问题上，比如机械臂、蛇形机器人的规划问题将带来巨大的计算代价。这样也直接促使了第二大类算法的产生。

二 基于采样的规划算法

RRT-connect算法
这种算法一般是不直接在grid地图进行最小栅格分辨率的规划，它们采用在地图上随机撒一定密度的粒子来抽象实际地图辅助规划。如PRM算法及其变种就是在原始地图上进行撒点，抽取roadmap在这样一个拓扑地图上进行规划；RRT以及其优秀的变种RRT-connect则是在地图上每步随机撒一个点，迭代生长树的方式，连接起止点为目的，最后在连接的图上进行规划。这些基于采样的算法速度较快，但是生成的路径代价（可理解为长度）较完备的算法高，而且会产生“有解求不出”的情况（PRM的逢Narrow space卒的情况）。这样的算法一般在高维度的规划问题中广泛运用。

三 其他规划算法
除了这两类之外还有间接的规划算法：Experience-based（Experience Graph经验图算法）算法：基于经验的规划算法，这是一种存储之前规划路径，建立知识库，依赖之进行规划的方法，题主有兴趣可以阅读相关文献。这种方法牺牲了一定的空间代价达到了速度与完备兼得的优势。此外还有基于广义Voronoi图的方法进行的Fast-marching规划，类似dijkstra规划和势场的融合，该方法能够完备地规划出位于道路中央，远离障碍物的路径。答主最近也在研究此类算法相关的工作。

APF（人工势场）算法

至于D* 、势场法、DWA(动态窗口法)、SR-PRM属于在动态环境下为躲避动态障碍物、考虑机器人动力学模型设计的规划算法。

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

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中的顶点为中间顶点的当前最短路径长度。