关于四边形不等式

四边形不等式是一种比较生草常见的优化动态规划的方法

定义

一般的，如果对于任意的 $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$³$)$ ，我们可以优化到 $\Theta( n$²$ )$

定义 $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]$