词条 | 四边形不等式 |
释义 | 介绍及证明:四边形不等式是一种比较常见的优化动态规划的方法: 设m[i,j]表示动态规划的状态量。 m[i,j]有类似如下的状态转移方程: m[i,j]=opt{m[i,k]+m[k,j]}(i≤k≤j) 如果对于任意的a≤b≤c≤d,有m[a,c]+m[b,d]≤m[a,d]+m[b,c],那么m[i,j]满足四边形不等式。 以上是适用这种优化方法的必要条件 对于一道具体的题目,我们首先要证明它满足这个条件,一般来说用数学归纳法证明,根据题目的不同而不同。 通常的动态规划的复杂度是O(n^3),我们可以优化到O(n^2) 设s[i,j]为m[i,j]的决策量,即m[i,j]=m[i,s[i,j]]+m[s[i,j],j] 我们可以证明,s[i,j-1]≤s[i,j]≤s[i+1,j] (证明过程见下) 那么改变状态转移方程为: m[i,j]=opt{m[i,k]+m[k,j]}(s[i,j-1]≤k≤s[i+1,j]) 复杂度分析:不难看出,复杂度决定于s的值,以求m[i,i+L]为例, (s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]≤n 所以总复杂度是O(n) 对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明: 设mk[i,j]=m[i,k]+m[k,j],s[i,j]=d 对于任意k<d,有mk[i,j]≥md[i,j](这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似),接下来只要证明mk[i+1,j]≥md[i+1,j],那么只有当s[i+1,j]≥s[i,j]时才有可能有ms[i+1,j][i+1,j]≤md[i+1,j] (mk[i+1,j]-md[i+1,j])-(mk[i,j]-md[i,j]) =(mk[i+1,j]+md[i,j])-(md[i+1,j]+mk[i,j]) =(m[i+1,k]+m[k,j]+m[i,d]+m[d,j])-(m[i+1,d]+m[d,j]+m[i,k]+m[k,j]) =(m[i+1,k]+m[i,d])-(m[i+1,d]+m[i,k]) ∵m满足四边形不等式,∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k] ∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0 ∴s[i,j]≤s[i+1,j],同理可证s[i,j-1]≤s[i,j] 证毕 扩展:以上所给出的状态转移方程只是一种比较一般的,其实,很多状态转移方程都满足四边形不等式优化的条件。 解决这类问题的大概步骤是: 0.证明w满足四边形不等式,这里w是m的附属量,形如m[i,j]=opt{m[i,k]+m[k,j]+w[i,j]},此时大多要先证明w满足条件才能进一步证明m满足条件 1.证明m满足四边形不等式 2.证明s[i,j-1]≤s[i,j]≤s[i+1,j] |
随便看 |
|
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。