动态规划计算的优化 ――利用四边形不等式,利用其他数据结构

动态规划计算的优化——利用四边形不等式，利用其他数据结构李子星四边形不等式•定义–m[i,j]=min{m[i,k]+m[k+1,j]+w[i,j]|i=kj}–s[i,j]=max{k|m[i,j]=m[i,k]+m[k+1,j]+w[i,j]}•定理–若对于任意的i’=i=j=j’满足w[i,j]=w[i’,j’]，则称函数w满足区间包含单调性。–若对于任意的i’=i=j=j’满足w[i’,j]+w[i,j’]=w[i,j]+w[i’,j’]则称函数w满足四边形不等式。–若w满足区间包含单调性且满足四边形不等式，则m也满足四边形不等式。–若m满足四边形不等式，则s[i,j]=s[i,j+1]=s[i+1,j+1]–证明很复杂，大家有兴趣可以网上搜，这里就略去了。四边形不等式•于是–m[i,j]=min{m[i,k]+m[k+1,j]+w[i,j]|s[i,j-1]=k=s[i+1,j]}–而m的总计算量为sum{s[i+1,j]-s[i,j-1],1=i=j=n}，可以发现这个值是O(n2)的。–时间复杂度就从O(n3)降到O(n2)了。石子合并问题题意：n堆石子顺序排开，每次可以合并相邻的两堆，合并的代价是两堆石子的个数的和。问最小合并代价。方法：规划方程为m[i,j]=min{m[i,k]+m[k+1,j]+w[i,j]|i=kj}完全满足前面的条件，于是可以用前面的方法在O(n2)搞定。石子合并问题但如果要求最大代价，就不行了，因为规划方程不再是取min，而是取max了。大家也不用去推导证明，写个程序，再弄一批随机数据就可以验证了。四边形不等式优化适用范围似乎非常的窄而且推导非常的繁琐和麻烦，通用性也不强。四边形不等式其实可以直接一些：四边形不等式优化的关键就是s函数满足一定的单调性，不一定利用四边形不等式证明，靠思考和猜想都可以得到这个结论。邮局问题题意：在数轴上有n个村庄，各个村庄的位置分别在p[1..n]上（且p已经按从小到大排过序了），要求从中选k个建邮局，问每个村庄走到离其最近的邮局的距离的和。方法：规划方程为：f[i,j]=min{f[x-1,j-1]+w[x,i]|j=x=i}w[k,i]的计算可以想办法在O(1)的时间复杂度内算出，于是计算f的时间复杂度为O(n2k)。邮局问题同样定义：s[i,j]=max{k|f[i,j]=f[k-1,j-1]+w[k,i]且j=k=i}我们可以略过四边形不等式，直接讨论s[i,j]的单调性。很容易就可以想象到s[i,j]=s[i,j-1]，因为s[i,j]实际上对应的是最后一个邮局服务的最靠左的村庄编号，如果邮局总数变少了，那么最后一个邮局没道理服务更少的村庄。已经得到了一个下限，下一步就是想办法得到一个上限。同样可以很容易想象到s[i,j]=s[i+1,j]，因为s[i,j]s[i+1,j]的情况同样是不可能的。邮局问题1i1ii+1s[i,j]s[i,j]j-1个邮局j-1个邮局s[i,j]-1s[i,j]-1邮局问题于是就我们通过几个很容易想到的情形就得到了结论：s[i,j-1]=s[i,j]=s[i+1,j]且O(sum{s[i+1,j]-s[i,j+1],1=i=n,1=j=k})=O(n*n)于是，之前的计算时间复杂度就降为O(n*n)了。利用数据结构优化计算四边形不等式实质上就是减少状态转移的代价。而要减少状态转移的代价也可以利用一些数据结构来达成目标。邮局问题加强题意：有编号为1..n的n个村庄，按编号顺序依次排在一条数轴上，要求从中选任意个建邮局。已知i号村庄在数轴上的x[i]位置（x[i]=x[i+1]），在此建立邮局的费用为p[i]，在此建立邮局能够为距离不超过r[i]的所有村庄提供服务，若这个村庄没有邮局能够为其提供服务，则政府要为其补贴c[i]，问最小的费用。邮局问题加强方法：•令L[i]=min{k|x[i]-x[k]=r[i]}，即i号村庄建立邮局向左最远能服务到的村庄编号。•令R[i]=max{k|x[k]-x[i]=r[i]}，即i号村庄建立邮局向右最远能服务到的村庄编号。•那么m[i,k]=min{–min{m[L[j]-1,k-1]+p[j]|R[j]=i},–m[i-1,k]+c[i],–m[i,k-1]•}•计算的时间复杂度显然是O(n3)的。邮局问题加强•定义–f[i,k]=m[L[i]-1,k-1]+p[i]–g[i,k]={j|R[j]=i}•那么–m[i,k]=min{•min{f[j,k]|j∈g[i,k]},•m[i-1,k]+c[i],•m[i,k-1]–}–g[i-1,k]⊇g[i,k]•因为若j∉g[i-1,k]，则说明R[j]i-1，所以R[j]i也一定成立，所以j∉g[i,k]也一定成立–即若在计算m[i,k]时，因为R[j]太小而忽略的所有的j，在计算m[i+1..n,k]时，也肯定会被忽略掉。邮局问题加强因此若定义二元组h[i]=(f[i,k],R[i])，且h[i]h[j]等价于f[i,k]f[j,k]，则可以设计算法从m[1..n,k-1]计算m[1..n,k]如下：•先算出f[1..n,k]•g={h[1],h[2],…,h[n]}•fori=1tondobegin•h=min{x|x∈g}•while(h.secondi)dobegin•g=g-{h}•h=min{x|x∈g}•end•m[i,k]=min{h.first,m[i-1,k]+c[i],m[i,k-1]}•end邮局问题加强•如果用二叉堆来维护集合g，•初始时建堆的时间复杂度为O(n)，过程中的g=g-{h}可以在O(logn)的时间复杂度内解决，而h=min{x|x∈g}可以在O(1)的时间复杂度内解决。•前面的代码中每个h[i]只会离开g一次，于是这段代码的时间复杂度为O(nlogn)。•再加上外层的k的循环，总的时间复杂度就是O(n2logn)。邮局问题加强•如果换一下i的循环方向，变为从大到小，那么g就不再是不断删除元素了，而是不断增加元素。•求一个不断增加元素的集合的极小值，只需要一个临时变量保存当前的最小值就可以了。•那么问题就变成h[i]会按怎样的顺序加入g集合了。•其实这个问题非常简单，显然是按R[i]从大到小的顺序加入，即按h[i].second从大到小的顺序加入g。•所以只要将h[1..n]按第二元排个序就可以了，而h[1..n]的第二元即R[1..n]都是大于等于1小于等于n的，可以用基数排序在O(n)的时间复杂度内解决。邮局问题加强若h[1..n]按h[i].second从大到小的顺序排序后的结果为：h[s[1]],h[s[2]],…,h[s[n]]那么可以得到从m[1..n,k-1]计算m[1..n,k]的程序如下：•先算出f[1..n,k]，继而算出h[1..n]•用基数排序的方法对h[1..n]排序得到s[1..n]•j=1•fori=ndownto1dobegin•if(i=n)e[i]=+∞elsee[i]=e[i+1]•while(j=n&&i=h[s[j]].second)dobegin•if(h.firste[i])e[i]=h.first•j++•end•end•按i从小到大的顺序计算m[i,k]=min{e[i],m[i-1,k]+c[i],m[i,k-1]}这个过程的时间复杂度也是O(n)的，于是加上外层的k的循环，总时间复杂度就是O(n2)。