动态规划加速原理之四边形不等式

《动态规划加速原理之四边形不等式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划加速原理之四边形不等式华中师大一附中赵爽一、四边形不等式基本理论①在动态规划问题中，有一个常见的状态转移方程：ìmin{m(i,k-1)+m(k,j)+,ijïî例如“最小代价子母树”问题，都用到了这个式子。假如对于i£<£i¢¢jj，有w(i¢¢,,j)£w(ij)，那么我们称函数w满足关于区间包含的单调性。另外，假如有：w(i,j)+w(i¢,j¢)£+w(i¢¢,,j)w(ij)(1.2)那么我们称函数w满足四边形不等式。例如在“最小代价子母树”问题中，有w(i,j)+w(i¢,j¢)=

2、+w(i¢¢,,j)w(ij)。因此该问题中函数w是满足四边形不等式的。左图是四边形不等式的一种形象化理解。上面的不等式在图中可以看作在四边形ABCD中，对角线AC两个端点的权值之和，不大于对角线BD两个端点的权值之和。我们下面要研究的问题，是在w既满足关于区间包含的单调性，又满足四边形不等式的前提下进行的。【定理1】假如函数w满足上述条件，那么函数m也满足四边形不等式，即m(i,j)+m(i¢,j¢)£+m(i¢¢,,j)m(ij)，i£<£i¢¢jj证明：当ii=¢或jj=¢时，显然有m(i,j)+m(i¢,j¢)=+m(i¢¢,,j)m(ij)，不等式成立。①对于不同的问

3、题，mij(,)的边界取值可能不同。这对我们讨论的问题没有影响。下面分两种情况进行归纳证明（对l=-ji¢进行归纳）：情形1：i

4、m(k,,j)m(jj)£w(i,j¢¢)+m(i,k-+1,)m(kj)=m(ij,¢)情形2：i<<

5、j()£+w(i,j¢)w(i¢,j)+m(i¢¢,y-1)+mi(,z-1)++my(,,j)mzj()=+m(i,,j¢¢)m(ij)综上所述，由数学归纳法可知，函数m(ij,)也满足四边形不等式。证毕。我们定义s(ij,)为函数m(ij,)对应的决策变量的最大值，即：s(i,j)=max{m(i,,j)=w(ij)+m(i,k-+1,)m(kj)}(1.3)i<£kj【定理2】假如m(ij,)满足四边形不等式，那么s(ij,)单调，即：s(i,j)£s(i,j+1)£++s(ij1,1)证明：由对称性，我们仅需证明s(i,j)£+s(ij,1)。在ij>时，s(i,j)=

6、s(ij,1+)=¥，命题显然成立。ij=时，s(i,j)=0£+s(ij,1)，命题也成立。下面讨论ij<的情况。为了方便叙述，我们令m(ij,)表示决策变量取k的时候目标函数的值。即kmk(i,,j)=w(ij)+m(i,k-+1,)m(kj)。那么有ms(ij,)(i,,j)=m(ij)。由于m(ij,)满足四边形不等式，因此对于任意的k££kj¢，有：m(k,j)+m(k¢¢,j+1)£m(k,j)++m(kj,1)我们将等式两边同时加上w(i,j)+m(i,k-1)+w(i,j+1)+-m(ik,1¢)，就可以得出mk(i,j)+mk¢¢(i,j+1)£mkk(i,j

7、++1,)m(ij)，即：mk(i,,j)-mk¢¢(ij)£mkk(i,j+1)-+m(ij,1)(1.4)通过(1.4)式我们可以发现，mk¢¢(i,j)£mk(i,j)®mkk(i,j+1)£+m(ij,1)(1.5)由于kk¢³，同时对于所有的k