贪心算法-最短路径问题(从动态规划优化到贪心)
最短路径问题
问题描述
给定一个图,对于图中每条边都有一个距离。起始点是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条边的最短路径。由此我们可以得到转移方程如下:
我们要在最多经过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条边就能到,再多走一条边,路径也没有更短。后者这种在表格里就是横着平移,有很多重复的值是不需要计算的,为了找到什么时候可以不再继续计算该点的最小值(即该点不可能再被更新地更小了)。为此,我们定义一个特殊点。如下
即在最多k-1条边那列中,OPT值最小的点(s点除外),我们将每一轮k对应的添加到一个集合S中,添加后意味着OPT值在后续不会再发生变化,也就没有计算的必要了。
证明:本列最小OPT点无需再计算
由上面的定义,有的转移方程如下:
必然有(2)>(1),因为且,也就是一列的OPT最小值再经过多一条边肯定比不经过要大。所以
我们得到了第一个优化结论:
对于最多利用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的最短距离,设是所有未遍历相邻点中离已遍历点最近的点,也即。那么路径是s到的最短路径,路径长度为。
举个例子:已遍历集合为{s,x,w},相邻未遍历集合点(也可称一步到达点)为{},不相邻未遍历点为z(不用计算),对于已遍历点,我们知道d(x)=1,d(w)=2,而d(x)+d(x,y)=4,d(w)+d(w,u∗)=3,所以3是s到的最短路径长度。也就是的最短路径不会再发生变化。
为什么的最短距离不再变化?用反证法就可证明,假设存在另一个条路径要更短,即不通过w直达,则一定有,矛盾。
由此,我们可以得出第二个优化结论
与已遍历点集合S相邻的最近点 ,其到S的最短距离可以确定了。
这里的最近不要理解为最小,应该是
这就是Dijkstra算法
L7:每一列找最小的d(v)
L8:把其加入S
L9-11:从S多走1步看能否刷新s->v的最短距离
特殊case:所有点之间的距离都为1,就变成了BFS广度优先搜索
总结
经过以上两点优化,我们已经将Bellman Ford算法优化为Dijkstra算法。上面的优化就是贪心的思想,不考虑远的点,就只计算最近的相邻点,这就是一种局部最优的思想,所以Dijkstra 算法也属于贪心算法。