「算法笔记」四边形不等式

四边形不等式通过特殊性质得到决策单调性,是一种常见的优化动态规划的方法。


转移方程形式

本文讨论的四边形不等式用于优化以下常见方程:

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

这个转移方程状态有 $\mathcal O(n^2)$ 种,决策有 $\mathcal O(n)$ 种,因此直接转移的复杂度为 $\mathcal O(n^3)$。但是如果它有一些特殊性质,那么我们就可以优化复杂度!


条件

首先我们设 $i\le i'<j\le j'$,那么要求转移方程满足如下条件。

区间包含的单调性

$$ w(i', j) \le w(i, j') $$

四边形不等式

$$ w(i, j) + w(i', j') \le w(i', j) + w(i, j') $$


定理

四边形不等式

假如函数 $w$ 满足上述条件,那么函数 $f$ 也满足四边形不等式:

$$ f(i, j) + f(i', j')\le f(i', j) + f(i, j') $$

决策单调性

假如函数 $f$ 满足四边形不等式,那么决策点 $s(i,j)$ 单调,即有如下不等式:

$$ s(i, j) \le s(i, j + 1) \le s(i + 1, j + 1) $$

证明详见 动态规划加速原理之四边形不等式 - 赵爽(我才不会告诉你们我不会证明)


优化

有了如上性质和定义,我们可以对转移方程进行优化:

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

简单观察可以发现,对于确定的区间长度 $j - i + 1$,总复杂度为 $\mathcal O(n)$。故总复杂度为 $\mathcal O(n^2)$。


习题

发表评论