昆仑-昆仑娱乐-注册登录站

昆仑-昆仑娱乐-注册登录站 咨询热线:

昆仑新闻 >>当前位置: 首页 > 昆仑新闻

贪心算法-最短路径问题(从动态规划优化到贪心)

时间:2024-09-09 13:12:46

给定一个图 G = ? V , E ? G=?V,E? G=?V,E?,对于图中每条边 e = ? i , j ? e=?i,j? e=?i,j?都有一个距离 d i , j d_{i,j} di,j?。起始点是s,终点是t,问从s到t的最短路径是多少?
在这里插入图片描述

1.动态规划

最短路径问题是一个多步决策问题,所以可以先考虑用动态规划来求解。如果我们用OPT(i,j)表示点i到点j的最短路径,如果图中存在负值的边、负值环路,就转移方程会出现类似陷入循环等问题,而且转移方程无法与明确的d(u,v)做关联。所以我们通过引入一个新变量k,使得OPT(i,j)变成OPT(i,j,k)(从i到j经过最多k条边的最短路径),因为起点是固定的,我们只用考虑终点即可,最终定义OPT(v,k):从s到点v最多经过k条边的最短路径。由此我们可以得到转移方程如下:
O P T ( v , k ) = min ? { O P T ( v , k ? 1 ) min ? ? u , v ? ∈ E { O P T ( u , k ? 1 ) + d u , v } OPT(v,k) = \min \begin {cases} OPT(v,k-1) \\ \min_{\lang u,v\rang \in E}\{OPT(u,k-1)+d_{u,v}\} \end{cases} OPT(v,k)=min{OPT(v,k?1)min?u,v?E?{OPT(u,k?1)+du,v?}?
我们要在最多经过k条边内到达v,有两种可能,一是直接最多经过k-1条边就可以到达;二是先经过最多k-1条边到达u,存在一条边从u到v,经过此边到达v(可能有多个u满足,取最小者),二者取较小即OPT(v,k)。

这个是Bellman Ford算法,是一种求解单源最短路径的算法。

伪代码如下:
在这里插入图片描述
通过上面算法,我们可以算出s到v的最短路径为4,下面表格还可以继续延申(k最多可能为8)。
在这里插入图片描述

2.贪心算法

在有了动态规划算法之后,我们观察上图示例可以发现是存在冗余计算的。

优化1:去除冗余计算

这个表格里的值的计算,要么是走了k-1条边后再走一条边从而让路径更短,要么是走k-1条边就能到,再多走一条边,路径也没有更短。后者这种在表格里就是横着平移,有很多重复的值是不需要计算的,为了找到什么时候可以不再继续计算该点的最小值(即该点不可能再被更新地更小了)。为此,我们定义一个特殊点 v ? v^? v?。如下
O P T ( v ? , k ? 1 ) = m i n v O P T ( v , k ? 1 ) OPT(v^*,k-1) = min_vOPT(v,k-1) OPT(v?,k?1)=minv?OPT(v,k?1)
即在最多k-1条边那列中,OPT值最小的点(s点除外),我们将每一轮k对应的 v ? v^? v?添加到一个集合S中,添加后意味着OPT值在后续不会再发生变化,也就没有计算的必要了。

证明:本列最小OPT点无需再计算
由上面的定义,有 v ? v^? v?的转移方程如下:
O P T ( v ? , k ) = min ? { O P T ( v ? , k ? 1 ) ; ( 1 ) min ? ? u , v ? ? ∈ E { O P T ( u , k ? 1 ) + d u , v ? } ; ( 2 ) OPT(v^*,k) = \min \begin {cases} OPT(v^*,k-1) ;(1) \\ \min_{\lang u,v^*\rang \in E}\{OPT(u,k-1)+d_{u,v^*}\} ; (2) \end{cases} OPT(v?,k)=min{OPT(v?,k?1);(1)min?u,v??E?{OPT(u,k?1)+du,v??};(2)?
必然有(2)>(1),因为 O P T ( u , k ? 1 ) ≥ O P T ( v ? , k ? 1 ) OPT(u,k?1)≥OPT(v^?,k?1) OPT(u,k?1)OPT(v?,k?1) d u , v ? ≥ 0 d_{u,v^?}≥0 du,v??0,也就是一列的OPT最小值再经过多一条边肯定比不经过要大。所以
O P T ( v ? , k ) = O P T ( v ? , k ? 1 ) OPT(v^*,k) = OPT(v^*,k-1) OPT(v?,k)=OPT(v?,k?1)

我们得到了第一个优化结论:
对于最多利用k-1条边走到v的最近点(即表中每列OPT值最小的点),它以后的OPT值不会再变化。

初始化一个集合S={s},每次找出那一列的最小值的点,就把其添加进S,之后就不用算了,也就是下图绿色的是不需要计算的。
在这里插入图片描述
伪代码如下:
在这里插入图片描述

优化2:只考虑相邻最近点

前面我们已经加入了贪婪规则:一旦算出该点的最短距离后不再冗余计算该点OPT,但我们仍然需要遍历所有没加入集合S中点。其实每次我们只是多看一步,有很多相隔几步的点是不需要计算的,比如y与t离s比较远、不相邻,在k=1的时候应该不需要计算OPT(y,1),OPT(t,1)(注意这里的远是指离已遍历点远),同样地,在k=2时,已遍历集合中多了u,此时y离已遍历集合近了,但t仍然离S={s,u}远(不相邻)。

举个例子:
当k=1时,S={s},其更新了u,v.x三个点(它们与s相邻,一步可达),而y,t与s不相邻,因此没必要对y,t做计算。
当k=2时,S={s,u},其更新了v,x,y(相邻),但t不相邻,虽然t被更新到了5,但是这个数字更不更新对最终结果并没有影响
当k=3时,S={s,u,v,x},其更新了y,t(相邻),发现此时t被更新了,但它的更新来源于x,与之前的5没有关系(5换成无穷也是一样结果)

由此,我们知道,那些与已遍历集合S不相邻的点无需计算。
再进一步,那些相邻的点我们是否全部需要计算?

记d(v)表示从s到v的最短距离,设 u ? u^? u?是所有未遍历相邻点中离已遍历点最近的点,也即 d ( u ? ) = m i n w ∈ S d ( w ) + d ( w , u ) d(u^?)=min_{w∈S}{d(w)+d(w,u)} d(u?)=minwS?d(w)+d(w,u)。那么路径 P : s → . . . → w → u ? P:s→...→w→u^? P:s...wu?是s到 u ? u^? u?的最短路径,路径长度为 d ( u ? ) d(u^?) d(u?)

举个例子:已遍历集合为{s,x,w},相邻未遍历集合点(也可称一步到达点)为{ y , u ? y,u^? y,u?},不相邻未遍历点为z(不用计算),对于已遍历点,我们知道d(x)=1,d(w)=2,而d(x)+d(x,y)=4,d(w)+d(w,u?)=3,所以3是s到 u ? u^? u?的最短路径长度。也就是 u ? u^? u?的最短路径不会再发生变化。
在这里插入图片描述

为什么 u ? u^? u?的最短距离不再变化?用反证法就可证明,假设存在另一个条路径 P ′ : s → . . . → x → y → . . . → u ? P′:s→...→x→y→...→u^? P:s...xy...u?要更短,即 u ? u^? u?不通过w直达,则一定有 ∣ P ′ ∣ ≥ d ( s , x ) + d ( x , y ) ≥ d ( w ) + d ( w , u ? ) = d ( u ? ) ∣P′∣≥d(s,x)+d(x,y)≥d(w)+d(w,u^?) = d(u^?) Pd(s,x)+d(x,y)d(w)+d(w,u?)=d(u?),矛盾。

由此,我们可以得出第二个优化结论
与已遍历点集合S相邻的最近点 u ? u^? u? ,其到S的最短距离可以确定了。

这里的最近不要理解为 d ( v , u ? ) d(v,u^?) d(v,u?)最小,应该是 d ( v ) + d ( v , u ? ) d(v)+d(v,u^?) d(v)+d(v,u?)

这就是Dijkstra算法

在这里插入图片描述
L7:每一列找最小的d(v)
L8:把其加入S
L9-11:从S多走1步看能否刷新s->v的最短距离

特殊case:所有点之间的距离都为1,就变成了BFS广度优先搜索

经过以上两点优化,我们已经将Bellman Ford算法优化为Dijkstra算法。上面的优化就是贪心的思想,不考虑远的点,就只计算最近的相邻点,这就是一种局部最优的思想,所以Dijkstra 算法也属于贪心算法。

返回
Copyright © 2012-2018 昆仑-昆仑娱乐-注册登录站  电话:0898-08980898
地址:海南省海口市  ICP备案编号:琼ICP备xxxxxxxx号
找我

全国统一服务热线7*24小时为您在线服务

平台注册入口