四邊形不等式是一種比較常見的最佳化動態規劃的方法
基本介紹
- 中文名：四邊形不等式
- 外文名：quadrangle inequality
- 形式：a1≤a2<b1≤b2
- 特點：比較常見的
- 作用：最佳化動態規劃
定義,最佳化,證明,擴展,
定義
如果對於任意的a1≤a2<b1≤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滿足四邊形不等式是適用這種最佳化方法的必要條件
對於一道具體的題目，我們首先要證明它滿足這個條件，一般來說用數學歸納法證明，根據題目的不同而不同。
通常的動態規劃的複雜度是O(n^3)，我們可以最佳化到O(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])
∵m滿足四邊形不等式，∴對於i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]
∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0
∴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]
