四边形不等式是一种比较生草常见的优化动态规划的方法
定义
一般的,如果对于任意的 $a1 \leq a2 < b1 \leq b2$,
有 $m[a1,b1] + m[a2,b2] ≤ m[a1,b2] + m[a2,b1]$,
那么 $m[i,j]$ 满足四边形不等式
优化
设 $m[i,j]$ 表示动态规划的状态量
$m[i,j]$ 有类似如下的状态转移方程:
$m[i,j] = min {( m[i,k] + m[k,j] | i≤k≤j )}$
$m$ 满足四边形不等式是适用这种优化方法的必要条件
对于一道具体的题目,我们首先要证明它满足这个条件,一般来说用数学归纳法证明,根据题目的不同而不同。
通常的动态规划的复杂度是 $\Theta($$n$3$)$ ,我们可以优化到 $\Theta( n$2$ )$
定义 $s(i,j)$ 为函数 $m(i,j)$ 对应的使得 $m(i,j)$ 取得最小值的k值。
我们可以证明,$s[i,j-1] ≤ s[i,j] ≤ s[i+1,j]$
那么改变状态转移方程为:
$m[i,j] = min {{ 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]$ 时才有可能有 $mk[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] )$
$\because$ $m$ 满足四边形不等式
$\therefore$ 对于 $i < i+1 ≤ k < d$
有 $m[i+1,k] + m[i,d] ≥ m[i+1,d] + m[i,k]$
$\therefore$ $( mk[i+1,j] - md[i+1,j] ) ≥ ( mk[i,j] - md[i,j] ) ≥ 0$
$\therefore$ $s[i,j] ≤ s[i+1,j]$ ,同理可证 $s[i,j-1] ≤ s[i,j]$
证毕
扩展
以上所给出的状态转移方程只是一种比较一般的,其实,很多状态转移方程都满足四边形不等式优化的条件。
解决这类问题的大概步骤是:
- 证明 $w$ 满足四边形不等式,这里 $w$ 是 $m$ 的附属量,形如 $m[i,j] = opt {{ m[i,k] + m[k,j] + w[i,j] }}$,此时大多要先证明 $w$ 满足条件才能进一步证明 $m$ 满足条件
- 证明 $m$ 满足四边形不等式
- 证明 $s[i,j-1] ≤ s[i,j] ≤ s[i+1,j]$