浅谈平行四边形优化(包含正确性证明)

1.概述

平行四边形优化是一个神奇的东西,可以将时间复杂度为$\Theta(n^3)$的常规区间动态规划问题优化成$O(n^2)$。我们先抛出一个常规的区间DP转移方程:

$$m(i,j) =\begin{cases}
\displaystyle\min_{i<k\le j}{m(i,k-1)+m(k,j)+w(i,j)} &\text{if } i<j \
0 &\text{if } i=j \
\infty &\text{if } i>j
\end{cases}$$

如果要可以进行平行四边形优化,该式还要满足:对于所有的$i\le i'<j \le j’$,有:

$w(i’,j’)\le w(i,j’)$ (1.1)

$w(i,j)+w(i’,j’)\le w(i’,j)+w(i,j’)$ (1.2)

按照一般的递推来做的话,这玩意时间复杂度为$\Theta(n^3)$(证明略)。然后我们进行一些设定:

$m_k(i,j)=m(i,k-1)+m(k,j)+w(i,j)(i\lt k\le j) $

$$ s(i,j)=\begin{cases}
\displaystyle\max_{i<k \le j}{k|m(i,j)=m_k(i,j)}      &\text{if } i<j \
0 &\text{if } i \ge j
\end{cases} $$

2.结论,操作与时间复杂度

由于平行四边形优化的正确性证明十分难,这里先给出结论,操作流程与时间复杂度分析,后面再给出证明,如果你不想把它搞得很清楚,就把结论背下来,如果你想把它搞清楚,请先看第三部分。结论:

$m(i,j)=\begin{cases}
\displaystyle\min_{s(i,j-1)\le k \le s(i+1,j)}{m_k(i,j)} &\text{if } j>i+1 \
m(i,i)+m(j,j)+w(i,j) &\text{if } j=i+1 \
0 &\text{if } j=i \
\infty &\text{if } j<i
\end{cases}$

则:

$$s(i,j) = \begin{cases}
\displaystyle\max_{s(i,j-1) \le k \le s(i+1,j)}{k|m(i,j)=m_k(i,j)} &\text{if } j>i+1 \
j &\text{if } j=i+1 \
0 &\text{if } j<i+1
\end{cases}$$

然后你就可以按照上面那个转移方程转移,求m(i,j)的时候顺便把s(i,j)也求了,这样就可以得到一个快速的算法。时间复杂度分析(设数据规模为n的时间复杂度为T(n),常数省略):

$$T(n)=\displaystyle \sum_{len=3}^{n} \displaystyle \sum_{i=1}^{n-len+1}[s(i+1,i+len-1)-s(i,i+len-2)+1]+n-1 $$
$$=\displaystyle\sum_{len=3}^{n}[s(n-len+2,n)-s(1,len-1)+n-len+1]+n-1 $$
$$\le \displaystyle\sum_{len=3}^{n}(n+n)+n-1$$
$$=O(n^2)$$

3.平行四边形优化正确性证明

这是一个非常难的问题,我们需要先发现一些性质:

【性质1】对于任意$i\le i’ \le j \le j’$,有$m(i,j)+m(i’,j’) \le m(i’,j)+m(i,j’)$

证明:分三种情况讨论

情形1:$i=i’或j=j’$,显然成立。

情形2:$i<i’=j<j’$

则原问题转化为:$m(i,j)+m(j,j’)\le m(i,j’)$(根据m的定义)

我们对$l=j’-i+1$进行归纳证明。

设$k=s(i,j’)$

当$k\in (i,j]$时,

一个规模更小或是情形1条件下的不等式成立:

$m(k,j)+m(j,j’)\le m(k,j’)$     (2.1)

则有

$m(i,j)+m(j,j’) \le [m(i,k-1)+m(k,j)+w(i,j)]+m(j,j’)$
$\phantom{1000} \le m(i,k-1)+m(k,j)+w(i,j’)+m(j,j’)$  (由式(1.1)得)
$\phantom{1000} \le m(i,k-1)+m(k,j’)+w(i,j’)$(由式(2.1)得)
$\phantom{1000} \le m(i,j’)$

同理,当$k \in (j,j’] $时同样成立。

情形3:$i<i'<j<j’$

对$l=j’-i+1$进行归纳证明。

设:$y=s(i’,j) ,z=s(i,j’) $

假设$z\le y$则有$i<z\le y\le j$

一个规模更小,或是情形1,情形2条件下成立:

$m(z,j)+m(y,j’)\le m(y,j)+m(z,j’)$ (2.2)

则有:

$m(i,j)+m(i’,j’)\le w(i,j)+m(i,z-1)+m(z,j)+w(i’,j’)+m(i’,y-1)+m(y,j’) $
$\le w(i’,j)+w(i,j’)+m(i,z-1)+m(i’,y-1)+m(y,j)+m(z,j’) $(由式(1.2)(2.2)得)
$\le m(i,j’)+m(i’,j)$

同理,当$y<z$时同样成立。

综上所述,性质1成立。

【性质2】对于任意$j>i+1$,有$s(i,j-1)\le s(i,j) \le s(i+1,j)$

证明:

情形1:$j=i+2$,显然成立。

情形2:$j>i+2$

到这里,你或许有些晕了,我们把之前的定义和可用的式子简略地梳理一遍:

$m(i,j) =\begin{cases}
\displaystyle\min_{i<k\le j}{m(i,k-1)+m(k,j)+w(i,j)} &\text{if } i<j \
0 &\text{if } i=j \
\infty &\text{if } i>j
\end{cases} \ $

$m_k(i,j)=m(i,k-1)+m(k,j)+w(i,j)(i<k\le j)$

$s(i,j)=\begin{cases}
\displaystyle\max_{i<k \le j}{k|m(i,j)=m_k(i,j)}      &\text{if } i<j \
0 &\text{if } i \ge j
\end{cases}$

$w(i’,j’)\le w(i,j’)$ (1.1)

$w(i,j)+w(i’,j’)\le w(i’,j)+w(i,j’)$ (1.2)

$m(i,j)+m(i’,j’) \le m(i’,j)+m(i,j’)$(性质1)

$m_k(i,j)\ge m_{s(i,j)}(i,j)(k\le s(i,j))$ (3.1)

$m_k(i,j)>m_{s(i,j)}(i,j)(k>s(i,j))$(3.2)

我们先证明$s(i,j-1)\le s(i,j)$

对于任意${k|i<k<s(i,j-1)}$,由性质1得:

$m(k,j-1)+m(s(i,j-1),j)\le m(s(i,j-1),j-1)+m(k,j)$

两边同时加上$(m(i,k-1)+w(i,j-1)+m(i,s(i,j-1)-1)+w(i,j))$得:

$m_k(i,j-1)+m_{s(i,j-1)}(i,j)\le m_{s(i,j-1)}(i,j-1)+m_k(i,j)$

又由式(3.1)得:$m_{s(i,j-1)}(i,j)\le m_k(i,j)$

则由s的定义得:$s(i,j-1)\le s(i,j)$

再来证$s(i,j)\le s(i+1,j)$

对于任意${k|s(i,j+1)<k\le j}$,由性质1得:

$m(i+1,k-1)+m(i,s(i+1,j)-1)\le m(i,k-1)+m(i+1,s(i+1,j)-1)$

两边同时加上$(m(k,j)+w(i,j)+m(s(i+1,j),j)+w(i+1,j))$得:

$m_k(i+1,j)+m_{s(i+1,j)}(i,j)\le m_k(i,j)+m_{s(i+1,j)}(i+1,j)$

又由式(3.2)得:$m_{s(i+1,j)}(i,j)<m_k(i,j)$

则由s的定义得:$s(i,j)\le s(i+1,j)$

综上所述,性质2成立。

这样,我们就得到了s的单调性,就比较容易地可以得出:

$m(i,j)=\begin{cases}
\displaystyle\min_{s(i,j-1)\le k \le s(i+1,j)}{m_k(i,j)} &\text{if } j>i+1 \
m(i,i)+m(j,j)+w(i,j) &\text{if } j=i+1 \
0 &\text{if } j=i \
\infty &\text{if } j<i
\end{cases}$

现在请你再回去看第二部分。本文可能有些错误,敬请谅解。

0 条评论
发表一条评论