最短路经算法简介(Dijkstra算法,A*算法,D*算法)

时间:2022-10-17 03:10:55

据 Drew 所知最短路经算法现在重要的应用有计算机网络路由算法,机器人探路,交通路线导航,人工智能,游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*(D Star)算法。

最短路经计算分静态最短路计算和动态最短路计算。

静态路径最短路径算法是外界环境不变,计算最短路径。主要有Dijkstra算法,A*(A Star)算法。

动态路径最短路是外界环境不断发生变化,即不能计算预测的情况下计算最短路。如在游戏中敌人或障碍物不断移动的情况下。典型的有D*算法

 Dijkstra算法求最短路径:

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

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

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

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

最短路经算法简介(Dijkstra算法,A*算法,D*算法)

这是在drew 程序中4000个节点的随机路网上Dijkstra算法搜索最短路的演示,黑色圆圈表示经过遍历计算过的点由图中可以看到Dijkstra算法从起始点开始向周围层层计算扩展,在计算大量节点后,到达目标点。所以速度慢效率低。

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

基本思想

引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

操作步骤

(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3),直到遍历完所有顶点。

单纯的看上面的理论可能比较难以理解,下面通过实例来对该算法进行说明。

/*
测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大
6
1000000 1000000 10 100000 30 100
1000000 1000000 5 1000000 1000000 1000000
1000000 1000000 1000000 50 1000000 1000000
1000000 1000000 1000000 1000000 1000000 10
1000000 1000000 1000000 20 1000000 60
1000000 1000000 1000000 1000000 1000000 1000000
结果:
D[0] D[1] D[2] D[3] D[4] D[5]
0 1000000 10 50 30 60
*/
#include <stdio.h>
#define MAX 1000000 int arcs[][];//邻接矩阵
int D[];//保存最短路径长度
int p[][];//路径
int final[];//若final[i] = 1则说明 顶点vi已在集合S中
int n = ;//顶点个数
int v0 = ;//源点
int v,w;
void ShortestPath_DIJ()
{
for (v = ; v < n; v++) //循环 初始化
{
final[v] = ; D[v] = arcs[v0][v];
for (w = ; w < n; w++) p[v][w] = ;//设空路径
if (D[v] < MAX) {p[v][v0] = ; p[v][v] = ;}
}
D[v0] = ; final[v0]=; //初始化 v0顶点属于集合S
//开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中
for (int i = ; i < n; i++)
{
int min = MAX;
for (w = ; w < n; w++)
{
//我认为的核心过程--选点
if (!final[w]) //如果w顶点在V-S中
{
//这个过程最终选出的点 应该是选出当前V-S中与S有关联边
//且权值最小的顶点 书上描述为 当前离V0最近的点
if (D[w] < min) {v = w; min = D[w];}
}
}
final[v] = ; //选出该点后加入到合集S中
for (w = ; w < n; w++)//更新当前最短路径和距离
{
/*在此循环中 v为当前刚选入集合S中的点
则以点V为中间点 考察 d0v+dvw 是否小于 D[w] 如果小于 则更新
比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
*/
if (!final[w] && (min+arcs[v][w]<D[w]))
{
D[w] = min + arcs[v][w];
// p[w] = p[v];
p[w][w] = ; //p[w] = p[v] + [w]
}
}
}
} int main()
{
freopen("./Dijkstra.txt", "r", stdin);
scanf("%d", &n);
for (int i = ; i < n; i++)
{
for (int j = ; j < n; j++)
{
scanf("%d", &arcs[i][j]);
}
}
ShortestPath_DIJ();
for (int i = ; i < n; i++) printf("D[%d] = %d\n",i,D[i]);
return ;
}

A*(A Star)算法:启发式(heuristic)算法

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

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

g(n):对g*(n)的一个估计,是当前的搜索图G中s到n的最优路径费用 g(n)≥g*(n)

h(n):对h*(n)的估计,是从n到目标节点的估计代价,称为启发函数。

例如:当h(n) = 0, g(n) = d, 则f(n) = g(n)就变为了宽度优先搜索,也就是如果不需要启发,那就是宽度优先搜索的算法了。

.

g(n):对g*(n)的一个估计,是当前的搜索图G中s到n的最优路径费用 g(n)≥g*(n)

h(n):对h*(n)的估计,是从n到目标节点的估计代价,称为启发函数。

例如:当h(n) = 0, g(n) = d, 则f(n) = g(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的大小,从最小路径的节点向下进行。
}

最短路经算法简介(Dijkstra算法,A*算法,D*算法)

上图是和上面Dijkstra算法使用同一个路网,相同的起点终点,用A*算法的情况,计算的点数从起始点逐渐向目标点方向扩展,计算的节点数量明显比Dijkstra少得多,效率很高,且能得到最优解。

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

D*算法

待补充...

最短路径算法

原文网址已经被占用.

Floyd(弗洛伊德)算法( from JarryWell)

Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法,可以正确处理有向图或负权的最短路径问题。(动态规划算法是通过拆分问题规模,并定义问题状态与状态的关系,使得问题能够以递推(分治)的方式去解决,最终合并各个拆分的小问题的解为整个问题的解。)

算法思想

从任意节点i到任意节点j的最短路径不外乎2种可能:1)直接从节点i到节点j,2)从节点i经过若干个节点k到节点j。所以,我们假设arcs(i,j)为节点i到节点j的最短路径的距离,对于每一个节点k,我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立,如果成立,证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短,我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j),这样一来,当我们遍历完所有节点k,arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。(由于动态规划算法在执行过程中,需要保存大量的临时状态(即小问题的解),因此它天生适用于用矩阵来作为其数据结构,因此在本算法中,我们将不使用Guava-Graph结构,而采用邻接矩阵来作为本例的数据结构)

for (int k = ; k <= vexCount; k++) { //并入中转节点1,2,...vexCount
for (int i = ; i <= vexCount; i++) {
for (int j = ; j < vexCount; j++) {
if (arcs[i][k] + arcs[k][j] < arcs[i][j]) {
arcs[i][j] = arcs[i][k] + arcs[k][j];
path[i][j] = path[i][k]; //这里保存当前是中转的是哪个节点的信息
}
}
}
}