【算法-动态规划】 四边形不等式优化的证明

由 联环己烷 发布

四边形不等式

对于形如$f(i,j)=\min \{ f(i,k)+f(k+1,j)+w(i,j)\}$形式的DP,若对于$i \leq i' \leq j \leq j'$,有$w(i',j) \leq w(i,j')$(即区间包含单调性)和$w(i,j)+w(i',j') \leq w(i',j)+w(i,j')$(即四边形不等式),则有:

定理1:f也满足四边形不等式,即$f(i,j)+f(i',j') \leq f(i',j)+f(i,j')$

定理2:记g(i,j)为对f(i,j)最优的k,则决策点g(i,j)满足单调性,即$g(i,j) \leq g(i+1,j) \leq g(i,j+1)$

四边形不等式可以简记为“交错小于包含”。

引理1

引理1:若有$w(i,j)+w(i+1,j+1) \leq w(i,j+1)+w(i+1,j)$,则w满足四边形不等式。

证明:

若有$w(i,j)+w(i+1,j+1) \leq w(i,j+1)+w(i+1,j)$,则:

$w(i,j) \leq w(i,j+1)+w(i+1,j)-w(i+1,j+1)$

$w(i+2,j+1) \leq w(i+1,j+1)+w(i+2,j)-w(i+1,j)$

两式联立可知$w(i,j)+w(i+2,j+1) \leq w(i,j+1)+w(i+2,j)$,故这个式子可以一直推广。

定理1

下面证明定理1。

s(i,j,k)=f(i,k)+f(k+1,j)+w(i,j)

只需证明$f(i,j)+f(i+1,j+1) \leq f(i,j+1)+f(i+1,j)$即可,对j-i+1的长度使用第二数学归纳法,即假设长度较小的已经满足了这个不等式,而长度为1时f就是w。

不妨设g(i+1,j)=x,g(i,j+1)=y,则

$$f(i,j+1)+f(i+1,j)=s(i,j+1,y)+s(i+1,j,x)=f(i+1,x)+f(x+1,j)+f(i,y)+f(y+1,j+1)+w(i,j+1)+w(i+1,j)$$

不妨设i,j,x,y的相对位置如图所示:

四边形优化.png

则则$f(i,y)+f(i+1,x) \geq f(i,x)+f(i+1,y)$

则$s(i,j+1,y)+s(i+1,j,x) \geq (f(i,x)+f(x+1,j))+(f(i+1,y)+f(y+1,j+1))+(w(i,j)+w(i+1,j+1))=s(i,j+1,y)+s(i,j,x) \geq f(i,j+1)+f(i+1,j)$

定理2

下面证明定理2。

设x<y,则由$f(x+1,j)+f(y+1,j+1) \leq f(x+1,j+1)+f(y+1,j)$可知:

$$(f(i,x)+f(x+1,j)+w(i,j))+(f(i,y)+f(y+1,j+1)+w(i,j+1)) \leq (f(i,y)+f(y+1,j)+w(i,j))+(f(i,x)+f(x+1,j)+w(i,j))$$

即$s(i,j,x)+s(i,j+1,y) \leq s(i,j,y)+s(i,j+1,x)$

即$s(i,j,x)-s(i,j,y) \leq s(i,j+1,x)-s(i,j+1,y)$

设$y=g(i,j)$,则$s(i,j,x)-s(i,j,y) \geq 0$,则$s(i,j+1,x)-s(i,j+1,y) \geq 0$

则$g(i,j+1) \geq g(i,j)$


暂无评论

发表评论


京公网安备 11010802033049号