動態規劃的四邊形不等式最佳化

動態規劃問題中有一類問題的幼稚解法需要

的時間複雜度來填完

空間的矩陣，但是假如輸入資料和轉移方程的設定滿足一定的數學邊界，即四邊形不等式，那麼這個時間複雜度可以被最佳化為

。這種最佳化方法的學名叫做 Knuth‘s Optimization，最開始是高納德大佬引入來解決最優二叉搜尋樹問題的，之後姚儲楓大佬對此進行了進一步的研究和總結並且證明了相關定理。這篇文章就簡單地結合原始的問題來解釋一下該定理的部分證明以及如何在程式碼中應用。

最優二叉搜尋樹問題：

現有 n 個排序過的數，記為陣列 a。為敘述方便使 a 的下標從 1 開始。已知給定兩組機率

和

，

為“每一次搜尋的目標正好為

”的機率，

為“每一次搜尋的目標正好在

$a_{i}$

和

$a_{i+1}$

之間”的機率，其中設邊界值

為負無窮，邊界值

$a_{n+1}$

為正無窮。求根據這些機率組成一個高效的二叉搜尋樹，使得每次搜尋的平均時間最小化。只需要返回該樹的最優平均時間，不需要表達或者返回樹的結構。

解答：

設定在二叉樹中一次遞迴為單位時間，那麼時間期待值的表示式為：

$\sum_{1 \leq i \leq n}p_i(1 + d(p_i)) + \sum_{0 \leq j \leq n}q_jd(q_j)$

其中 d（x）表示目標 x 所在的層數。以上表達式實際就是一個數學期待的和，也就是給定的已知機率陣列的加權和。直觀的理解就是，每次搜尋的值在越深的層數，花費在遞迴棧上的時間越長，所以我們要根據給定的機率陣列來確定怎麼排列二叉搜尋樹來使以上表達式達到最小值。比如，如果一個值的被搜尋機率相比其它的值要大很多，我們就傾向於把它安排得接近根節點。

該問題可以用 bottom-up 動態規劃來解，因為最優二叉樹左右兩個子樹的期待值之和必然是在所有可能的兩個子樹期待值之和中最優，易得動態規劃表和轉移方程（其實一點也不易得反正我不是自己想出來的）：

$w(i, j) = p_{i + 1} + ... + p_{j} + q_i + ... + q_j$

$c(i, j) = w(i, j) + min_{i < k \leq j}(c[i, k - 1] + c[k, j])$

$(0 \leq i < j \leq n)$

其中，

是動態規劃表，

就是我們所要求的最終的解，也就是整棵樹的平均搜尋時間的最小值。

是特殊的 base case，它代表空樹，比如表示

相關的最優機率的表示式並不是

而是

。

是一個很抽象的值，可能有些難以理解。試再看一下轉移方程中這項：

$c(i, j) = w(i, j) + min_{i < k \leq j}(c[i, k - 1] + c[k, j])$

。這一行的過程是在 i 到 j 的範圍中，找到兩棵長度和為

的樹作為當前樹的左右子樹，並且把夾在它們中間的

作為當前的根節點。以上操作過程的實際影響則是將左右兩棵子樹的所有節點的層數都增加了 1，那麼根據我們的時間期待的表示式，只要簡單地給所有受影響的範圍的機率都增加一項就好了。這就是

的意義。

理解了該動態規劃的原理後，不難發現它的執行過程是一個三層的迴圈巢狀。最外層是子樹的長度，由長度為 2 開始往上計算。中間層是當前長度的子樹“視窗”在整個陣列中滑動的過程。最裡層是為當前視窗逐項比較所有可能的左右子樹並且取最小值。

於是這是一個

時間複雜度的過程。但是實際上存在一定的條件，若滿足條件就可以把裡面的兩層迴圈最佳化到

時間。這裡先給出兩個關鍵概念的定義：

若 w 滿足四邊形不等式（QI： quadrangle inequality）則：

$\forall i \leq i$

若 w 滿足區間單調（MLI： monotone on the lattice of intervals）則：

$\forall i \leq i$

根據姚儲楓大佬的 Speedup Theorem，如果 w 滿足以上兩個條件，那麼這個動態規劃的裡面兩層迴圈可以最佳化到

時間，總時間複雜度就可以被最佳化到

$\Theta(n^2)$

。只要 w 滿足：

$\forall i \leq i$

那麼以上的動態規劃便可以被最佳化到

時間。

顯然 w 是滿足 MLI 的，因為根據 w 的定義（也就是機率和），w 中的項都不為負，而 MLI 定義中的區間

包含區間

，所以

永遠成立。

那為什麼 w 滿足 QI 呢？根據 w 的定義

：

於是我們發現 w 永遠擦邊滿足四邊形不等式。

為了近一步接近最終的結論，姚儲楓證明了兩個 Lemma 來輔助證明這個定理（具體證明不在這裡給出）：

Lemma 1： If

satisfies the QI and is MLI then

also satisfies the QI。

Lemma 2： Let

。 Let

$K_c(i, j) = max{k: c_k(i, j) = c(i, j)}$

be the largest index

at which minimum occurs in the current DP entry

。 Then if

satisfies QI the following inequality must hold：

$K_c(i, j) \leq K_c(i, j + 1) \leq K_c(i + 1, j + 1)$

這個問題中我們已經知道了 Lemma 1 可以被應用，那麼於是 Lemma 2 也可以被應用。所以

$K_c(i, j) \leq K_c(i, j + 1) \leq K_c(i + 1, j + 1)$

在這個問題中是成立的。這是一個很重要的結論，因為這個不等式成立的話，我們就知道在同一個固定長度視窗滑動的時候，如果我們已經知道了當前視窗的子樹的 k 值，那麼滑動到的下一個視窗的 k 值肯定大於等於當前的 k 值。也就是說，子樹［i， j］的最優根節點的座標是必然小於等於子樹［i + 1， j + 1］的最優根節點的座標的。於是在下一個視窗計算最小的兩個子樹的時候，我們的迴圈只要從當前的 k 開始，這就避免了很多重複計算。以上只是證明了這樣節省重複計算之後程式仍然是正確的，那麼怎麼證明這樣最佳化之後裡面兩層迴圈就是

$\Theta(n)$

的複雜度呢？

假設當前視窗長度為 l，那麼要進行當前視窗在整個陣列上的滑動需要的總時間為：

$l + \sum_{i = 1}^{n - l}(1 - K_c(i - 1, i + l - 1) + K_c(i, i + l)) =$

$K_c(n - l, n) - K_c(0, l) + n \leq 2n$

對於以上數列的求和過程中大多數項都抵消了，於是最終顯然裡面兩層迴圈的複雜度為

，算上最外層的迴圈，總時間複雜度就是

了。這個最佳化在程式碼上的體現則是，在進行一個固定長度視窗的滑動時，我們要記錄下每一個視窗位置的 k 來避免重複計算。如此，對於 1 到 n 每一個長度的視窗，我們都可以在

$\Theta(n)$

時間完成視窗的滑動和計算。

以下為該問題的幼稚解法的簡單 C++ 實現。這裡的 w 在程式碼實現上是 LeetCode 上一道經典題目 Range Sum Query Immutable 的最優解。我們只要花

時間來預處理一下得到

空間的陣列 wSum，其中 wSum［i］就相當於數學表示式上的

，而要求任意

的話我們只要計算 i ？ wSum［j］ - wSum［i -1］： wSum［j］這個表示式就行了。

double

optimalBST

（

vector

double

，

vector

double

）

{

input：

p： vector of size n + 1 where p［0］ is meaningless

q： vector of size n + 1

（

。

size

（）

）

return

0。

；

int

。

size

（）

；

// dp table setup

vector

double

（

，

vector

double

（

，

））；

// w preprocessing

vector

double

wSum

（

）；

wSum

［

］

；

for

（

int

；

）

{

wSum

［

］

wSum

［

］

［

］

［

］；

}

for

（

int

；

）

{

for

（

int

windowOffset

；

windowOffset

；

windowOffset

）

{

int

windowOffset

，

windowOffset

；

int

；

［

］［

］

［

］［

］

［

］［

］；

for

（

；

）

{

（

［

］［

］

［

］［

］

［

］［

］）

{

［

］［

］

［

］［

］

［

］［

］；

}

［

］［

］

？

wSum

［

］

wSum

［

］

：

wSum

［

］；

}

return

［

］［

］；

}

以下為該問題的最佳化解法的簡單 C++ 程式碼實現。與幼稚解法基本一樣，但是唯一也是最關鍵的最佳化點是使用了變數 kPrev（請看 #0 到 #2）。變數 kPrev 對於內兩層迴圈是一直保留並且在迴圈過程中一直遞增的。該變數的維持和使用是這個最佳化技巧的核心。

double

optimalBST

（

vector

double

，

vector

double

）

{

input：

p： vector of size n + 1 where p［0］ is meaningless

q： vector of size n + 1

（

。

size

（）

）

return

0。

；

int

。

size

（）

；

// dp table setup

vector

double

（

，

vector

double

（

，

））；

// w preprocessing

vector

double

wSum

（

）；

wSum

［

］

；

for

（

int

；

）

{

wSum

［

］

wSum

［

］

［

］

［

］；

}

for

（

int

；

）

{

int

kPrev

；

// #0

for

（

int

windowOffset

；

windowOffset

；

windowOffset

）

{

int

windowOffset

，

windowOffset

；

int

max

（

kPrev

，

）；

// #1

［

］［

］

［

］［

］

［

］［

］；

for

（

；

）

{

（

［

］［

］

［

］［

］

［

］［

］）

{

［

］［

］

［

］［

］

［

］［

］；

kPrev

；

// #2

}

［

］［

］

？

wSum

［

］

wSum

［

］

：

wSum

［

］；

}

return

［

］［

］；

}

所以，在有類似轉移方程的動態規劃問題中，比如

$c(i, j) = w(i, j) + min_{i < k \leq j}(c[i, k - 1] + c[k, j])$

或者

$c(i, j) = w(i, j) + max_{i < k \leq j}(c[i, k - 1] + c[k, j])$

，只要我們確定了轉移方程中相當於這裡的 w 的項同時滿足 MLI 和 QI，就可以採用這種最佳化方法。注意 min 版本和 max 版本需要滿足的 QI 不同，具體請參考姚儲楓的論文。只要滿足了相對應的條件，那麼記錄並且利用每一個視窗的 k 的小技巧就可以被應用，在程式仍然正確的前提下把整個程式從

最佳化到

。

參考：

［1］ Proof for Knuth Optimization

［2］ DonaldE。Knuth，“OptimumBinarySearchTrees，”

Acta Informatica

1， pp。 14-25 （1971）。

［3］ F。 F。 Yao， “Efficient Dynamic Programming Using Quadrangle Inequalities，”

Proceedings of the 12 Annual ACM Symposium on Theory of Computing （STOC’80），

pp。 429-43，（1980）。

小蜜蜂問答

小蜜蜂問答

動態規劃的四邊形不等式最佳化

推薦文章

小蜜蜂問答

小蜜蜂問答

動態規劃的四邊形不等式最佳化

相關文章

人工智慧遊戲輔助用什麼語言開發？

cc++入門習題100例

美工設計的介面是px，佈局的時候需要換算成dp 嗎

寵物小精靈DP什麼時候出186

推薦文章