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

1、动态规划计算的优化利用四边形不等式，利用其他数据结构李子星四边形不等式 定义 mi,j=min mi,k+mk+1,j+wi,j | i=kj si,j=max k | mi,j=mi,k+mk+1,j+wi,j 定理 若对于任意的i=i=j=j满足wi,j=wi,j，则称函数w满足区间包含单调性区间包含单调性。 若对于任意的i=i=j=j满足wi,j+wi,j=wi,j+wi,j则称函数w满足四边形不等式四边形不等式。 若w满足区间包含单调性且满足四边形不等式，则m也满足四边形不等式。 若m满足四边形不等式，则si,j=si,j+1=si+1,j+1 证明很复杂，大家有兴趣可以网上搜，这里就

2、略去了。四边形不等式 于是 mi,j=minmi,k+mk+1,j+wi,j | si,j-1=k=si+1,j 而m的总计算量为sumsi+1,j-si,j-1, 1=i=j=n，可以发现这个值是O(n2)的。 时间复杂度就从O(n3)降到O(n2)了。石子合并问题题意：n堆石子顺序排开，每次可以合并相邻的两堆，合并的代价是两堆石子的个数的和。问最小合并代价。方法：规划方程为mi,j=minmi,k+mk+1,j+wi,j | i=kj完全满足前面的条件，于是可以用前面的方法在O(n2)搞定。石子合并问题但如果要求最大代价，就不行了，因为规划方程不再是取min，而是取max了。大家也不用去推

3、导证明，写个程序，再弄一批随机数据就可以验证了。四边形不等式优化适用范围似乎非常的窄而且推导非常的繁琐和麻烦，通用性也不强。四边形不等式其实可以直接一些：四边形不等式优化的关键就是s函数满足一定的单调性，不一定利用四边形不等式证明，靠思考和猜想都可以得到这个结论。邮局问题题意：在数轴上有n个村庄，各个村庄的位置分别在p1.n上（且p已经按从小到大排过序了），要求从中选k个建邮局，问每个村庄走到离其最近的邮局的距离的和。方法：规划方程为：fi,j=minfx-1,j-1+wx,i | j=x=iwk,i的计算可以想办法在O(1)的时间复杂度内算出，于是计算f的时间复杂度为O(n2k)。邮局问题同

4、样定义：si,j=maxk | fi,j=fk-1,j-1+wk,i且j=k=si,j-1，因为si,j实际上对应的是最后一个邮局服务的最靠左的村庄编号，如果邮局总数变少了，那么最后一个邮局没道理服务更少的村庄。已经得到了一个下限，下一步就是想办法得到一个上限。同样可以很容易想象到si,jsi+1,j的情况同样是不可能的。邮局问题1i1ii+1si,jsi,jj-1个邮局j-1个邮局si,j-1si,j-1邮局问题于是就我们通过几个很容易想到的情形就得到了结论：si,j-1=si,j=si+1,j且O(sumsi+1,j-si,j+1,1=i=n,1=j=k) = O(n*n)于是，之前的计算

5、时间复杂度就降为O(n*n)了。利用数据结构优化计算四边形不等式实质上就是减少状态转移的代价。而要减少状态转移的代价也可以利用一些数据结构来达成目标。邮局问题加强题意：有编号为1.n的n个村庄，按编号顺序依次排在一条数轴上，要求从中选任意个建邮局。已知i号村庄在数轴上的xi位置（xi=xi+1），在此建立邮局的费用为pi，在此建立邮局能够为距离不超过ri的所有村庄提供服务，若这个村庄没有邮局能够为其提供服务，则政府要为其补贴ci，问最小的费用。邮局问题加强方法： 令Li=min k | xi-xk=ri ，即i号村庄建立邮局向左最远能服务到的村庄编号。 令Ri=max k | xk-xi=i

6、, mi-1,k+ci, mi,k-1 计算的时间复杂度显然是O(n3)的。邮局问题加强 定义 fi,k=mLi-1,k-1+pi gi,k= j | Rj=i 那么 mi,k=min min fj,k | jgi,k , mi-1,k+ci, mi,k-1 gi-1,kgi,k 因为若j gi-1,k，则说明Rji-1，所以Rji也一定成立，所以j gi,k也一定成立 即若在计算mi,k时，因为Rj太小而忽略的所有的j，在计算mi+1.n, k时，也肯定会被忽略掉。邮局问题加强因此若定义二元组hi=(fi,k, Ri)，且hihj等价于fi,kfj,k，则可以设计算法从m1.n, k-1计算

7、m1.n, k如下： 先算出f1.n, k g=h1, h2, , hn for i=1 to n do begin h=min x | xg while (h.secondi) do begin g=g-h h=min x | xg end mi,k=min h.first, mi-1,k+ci, mi,k-1 end邮局问题加强如果用二叉堆二叉堆来维护集合g，初始时建堆的时间复杂度为O(n)，过程中的g=g- h 可以在O(logn)的时间复杂度内解决，而h=min x | xg 可以在O(1)的时间复杂度内解决。前面的代码中每个hi只会离开g一次，于是这段代码的时间复杂度为O(nlogn

8、)。再加上外层的k的循环，总的时间复杂度就是O(n2logn)。邮局问题加强 如果换一下i的循环方向，变为从大到小，那么g就不再是不断删除元素了，而是不断增加元素。 求一个不断增加元素的集合的极小值，只需要一个临时变量保存当前的最小值就可以了。 那么问题就变成hi会按怎样的顺序加入g集合了。 其实这个问题非常简单，显然是按Ri从大到小的顺序加入，即按hi.second从大到小的顺序加入g。 所以只要将h1.n按第二元排个序就可以了，而h1.n的第二元即R1.n都是大于等于1小于等于n的，可以用基数排序在O(n)的时间复杂度内解决。邮局问题加强若h1.n按hi.second从大到小的顺序排序后的结果为：hs1, hs2, , hsn那么可以得到从m1.n, k-1计算m1.n, k的程序如下：先算出f1.n,k，继而算出h1.n用基数排序的方法对h1.n排序得到s1.nj=1for i=n downto 1 do beginif (i=n) ei=+ else ei=ei+1while (j=n & i=hsj.