icecream

基本動態規劃問題的擴展

應用動態規劃可以有效的解決許多問題，其中有許多問題的數學模型，尤其對一些自從57年就開始研究的基本問題所應用的數學模型，都十分精巧。有關這些問題的解法，我們甚至可以視為標準——也就是最優的解法。不過隨著問題規模的擴大化，有些模型顯出了自身的不足和缺陷。這樣，我們就需要進一步優化和改造這些模型。

一.   程序上的優化：

程序上的優化主要依賴問題的特殊性。我們以f(X^T)= opt{f(u^T)}+ A(X^T), u^TÎ Pred_Set(X^T)這樣的遞推方程式為例（其中A(X^T)為一個關于X^T的確定函數，Pred_Set(X^T)表示X^T的前趨集）。我們設狀態變量X^T的維數為t，每個X^T與前趨中有e維改變，則我們可以通過方程簡單的得到一個時間復雜度為O(n^t+e)的算法。

當然，這樣的算法并不是最好的算法。為了簡化問題，得到一個更好的算法。我們設每個X^T所對應的g(X^T)=opt{f(u^T)}，則f(X^T)=g(X^T)+A(X^T)，問題就變為求g(X^T)的值。下面分兩個方面討論這個問題：

1.       Pred_Set(X^T)為連續集：

在這樣的情況下，我們可以用g(X^T)= opt{g(Pred(X^T)), f(Pred(X^T))}這樣一個方程式來求出g(X^T)的值，并再用g(X^T)的值求出f(X^T)的值。這樣，雖然我們相當于對g(X^T)和f(X^T)分別作了一次動態規劃，但由于兩個規劃是同時進行的，時間復雜度卻降為了O(n^t)。由于我們在實際使用中的前趨即通常都是連續的，故這個方法有很多應用。例如IOI’99的《小花店》一題就可以用該方法把表面上的時間復雜度O(FV²)降為O(FV)。

2.       Pred_Set(X^T)為與X^T有關的集合：

這樣的問題比較復雜，我們以最長不下降子序列問題為例。規劃方程為：f(i)=max{f(j)}+1, d[i]≥ d[j]; i>j。通常認為，這個問題的最低可行時間復雜度為O(n²)。不過，這個問題只多了一個d[i]≥d[j]的限制，是不是也可以優化呢？我們注意到max{f(j)}的部分，它的時間復雜度為O(n)。但對于這樣的式子，我們通常都可以用一個優先隊列來使這個max運算的時間復雜度降至O(log n)。對于該問題，我們也可以用這樣的方法。在計算d[i]時，我們要先有一個平衡排序二叉樹（例如紅黑樹）對d[1]~d[i-1]進行排序。并且我們在樹的每一個節點新增一個MAX域記錄它的左子樹中的函數f的最大值。這樣，我們在計算f(i)時，只需用O(log n)時間找出不比d[i]大的最大數所對應的節點，并用O(1)的時間訪問它的MAX域就可以得出f(i)的值。并且，插入操作和更新MAX域的操作也都只用O(log n)的時間（我們不需要刪除操作），故總時間復雜度為O(n log n)。實際運行時這樣的程序也是十分快的，n=10000時用不到1秒就可以得出結果，而原來的程序需要30秒。

從以上的討論可以看出，再從程序設計上對問題優化時，要盡量減少問題的約束，盡可能的化為情況1。若不可以變為情況1，那么就要仔細考慮數據上的聯系，設計好的數據結構來解決問題。

二.   方程上的優化：

對于方程上的優化，其主要的方法就是通過某些數學結論對方程進行優化，避免不必要的運算。對于某一些特殊的問題，我們可以使用數學分析的方法對寫出的方程求最值，這樣甚至不用狀態之間的遞推計算就可以解決問題。不過用該方法解決的問題數量是在有限，并且這個方法也十分復雜。不過，卻的確有相當數量的比較一般的問題，在應用某些數學結論后，可以提高程序的效率。

一個比較典型的例子是最優排序二叉樹問題（CTSC96）。它的規劃方程如下：

我們可以從這個規劃方程上簡單的得到一個時間復雜度為O(n³)的算法。但是否會有更有效的算法呢？我們考慮一下w(i, j)的性質。它表示的是結點i到結點j的頻率之和。很明顯，若有[i, j]Í[i’, j’]，則有w[i, j]£ w[i’, j’]，這樣可知C[i, j]具有凸性^[1]。為了表示方便，我們記C_k(i, j)=w(i, j)+C[i, k-1]+C[k, j]，并用K_i,j表示取到最優值C[i, j]時的C_k(i, j)的k值。我們令k=K_i,j-1，并取i< k’< k。由于k’< k£ j-1< j，故有：

C[k’, j-1]+ C[k, j]£ C[k’, j]+ C[k, j-1]

在等式兩側同時加上w(i, j-1)+ w(i, j)+C[i,. k-1]+ C[i, k’-1]，可得：

C_k’(i, j-1)+ C_k(i, j)£ C_k’(i, j)+ C_k(i, j-1)

由k的定義可知C_k(i, j-1)£ C_k’(i, j-1)，故C_k(i, j)£ C_k’(i, j)，所以k’¹ K_i,j，故K_i,j³ K_i,j-1。同理，我們可得K_i,j£ K_i+1,j，即K_i,j-1£K_i,j£K_i+1,j。這樣，我們就可以按對角線來劃分階段（就是按照j-i劃分階段）來求K_i,j。求K_i,j的時間復雜度為O(K_i+1,j-K_i,j-1+1)，故第d階段（即計算K_1,1+d~K_n-d,n）共需時O(K_n-d+1,n-K_1,d+n-d)£ O(n)。有共有n個階段，故總時間復雜度為O(n²)。

雖然這道題由于空間上的限制給這個算法的實際應用造成了困難，不過這種方法卻給我們以啟示。

我們在考慮IOI2000的POST問題。這一題的數學模型不是討論的重點，我們先不加討論，直接給出規劃方程 。從規劃方程直接得出的算法的時間復雜度為O(n³)。從這個規劃方程可以看出，它的每一階段都只與上一階段有關。故我們可以把方程變得簡單些，變為對如下的方程執行n次：

在遞推時，階段之間時沒有優化的余地的，故優化的重點就在于這個方程的優化上。我們用B[i, j]表示D[i]+w(i, j)，而原算法就是求出B并對每一列求最小值。

事實上，這一題的w有其特殊的性質：

對于a£ b£ c£ d，我們有w(a, c)+ w(b, d)£ w(a, d)+ w(b, c)。

這一性質對解題是應該有所幫助的。仿照上例，在兩側加上D[a]+ D[b]，可得B[a, c]+ B[b, d]£ B[a, d]+ B[b, c]。

也就是說，若B[a, c]³ B[b, c]，則有B[a, d]³ B[b, d]。于是我們在確定了B[a, c]與B[b, c]的大小關系之后，就可以決定是不是需要比較B[a, d]與B[b, d]的大小。[U1] 

更進一步的，我們只要找出滿足B[a, h]³ B[b, h]的最小的h，就可以免去h之后對第a列的計算。而這樣的h，我們可以用二分查找法在O(log n)時間內找到（若w更特殊一些，例如說是確定的函數，我們甚至可以在O(1)的時間找到）。并且對于每一行來說，都只需要執行一次二分查找。在求出所有的h之后，只需用O(n)的時間對每列的第h行求值就可以了。這樣得出的總時間為O(n)+O(n log n)= O(n log n)。至于程序設計上的問題，雖然并不復雜，但不是15分鐘所可以解決的，也不是重點，略過不談。^[2]不過由于該題目可以用滾動數組的技巧解決空間的問題，故在大數據量時該算法有優異的表現。

從上面的敘述可以看出，對于方程的優化主要取決于權函數w的性質。其中應用最多的就是w(a, c)+ w(b, d)£ w(a, d)+ w(b, c)這個不等式。實際上，這個式子被稱作函數的凸性判定不等式。在實際問題中，權函數通常都會滿足這個不等式或這是它的逆不等式。故這樣的優化應用是比較廣泛的。還有許多特殊的不等式，若可以在程序中應用，都可以提高程序的效率。

三.   從低維向高維的轉化：

在問題擴大規模時，有一種方式就是擴大問題的維數。這時，規劃時決策變量的維數也要增加。這樣，存儲的空間也要隨著成指數級增加，導致無法存儲下所有的狀態，這就是動態規劃的維數災難問題。如果我們還要在這種情況下使用動態規劃，那么就要使用極其復雜的數學分析方法。對于我們來說，使用這種方法顯然是不現實的。這時，我們就需要改造動態規劃的模型。通常我們都可以把這時的動態規劃模型變為網絡流模型。

對于模型的轉化方法，我們有一些一般的規律。若狀態轉移方程只與另一個狀態有關，我們可以肯定得到一個最小費用最大流的模型^[3]。這個模型必然有其規律的地方，甚至用對偶算法在對網絡流的求解時也還要用到動態規劃的方法。不過這不是重點，我們關心的只是動態規劃問題如何轉化。例如說IOI’97《火星探測器》一題。這一題的一維模型是可以用動態規劃來解決的（這里的維數概念是指探測器的數目）。在維數增加時，我們就可以用該方法來用網絡流的方法解決問題。

除此之外，還有許多問題可以用該方法解決。例如最長區間覆蓋問題，在維數增加時也同樣可以用該方法解決。更進一步來說，甚至圖論的最短路問題也可以做同樣的轉化來求出特殊的最短路。不過一般來說轉化后流量最大為1，有許多特殊的性質也沒有得到應用，并且些復雜的動態規劃問題還無法轉化為網絡流問題（例如說最優二叉樹問題），故標準的網絡流算法顯然有些浪費，它的解決還需要進一步的研究。

參考文獻：

[EGG88] David Eppstein, Zvi Galil and Raffaele Giancarlo, Speeding up Dynamic Programming

[GP90] Zvi Galil and Kunsoo Park, Dynamic Programming with Convexity, Concavity, and Sparsity

[附錄]

[1]    C[i, j]的凸性是指對于任意的a£ b£ c£ d，都有C[a, c]+ C[b, d]£ C[a, d]+ C[b, c]。它的證明如下：

我們設k=K_b,c，則有C[a, c]+ C[b, d]£ C[a, k-1]+ C[k, c]+ C[b, k-1]+ C[k, d]+ w(a, c)+ w(b, d)= C[a, k-1]+ C[k, d]+ w(a, d)+ C[b, k-1]+ C[k, c]+ w(b, c)= C[a, d]+ C[b, c]。得證。

[2]    有關這個問題的偽代碼如下：

begin

  E[1]ßD[1];

  Queue.Add(K:1, H:n);

  for jß2 to n do

  begin

    if B(j-1, j)£ B(Queue.K[head], j) then

    begin

      E[j]ßB(j-1, j);

      Queue.Empty;

      Queue.Add(K:j-1, H:n+1);

    end else

    begin

      E[j]ßB(Queue.K[head], j);

      while B(j-1, Queue.H[tail-1])£ B(Queue.K[tail], Queue.H[tail-1]) do Queue.Delete(tail);

      Queue.H[tail]ßh(Queue.K[tail], j-1);

      if h_OK then Queue.Add(K:j-1, H:n+1);

    end;

    if Queue.H[head]=j+1 then Queue.SkipHead;

  end;

end;

其中的隊列Queue可以稱作備選隊列，其中的隊列頭為第j行的最小值，并假設Queue.H[0]=j。其中的h(a, b)函數是用二分查找法查找B(a, h)³ B(b, h)的最小的h值，h_OK為查找成功與否的標志。在備選隊列Queue中的數據(K:i_r, H:h_r)的意義是：當行數在區間[h_r-1, h_r-1]的范圍內時，第i_r列為最小值。

[3]    我們知道，動態規劃實際是求無向圖的最短路的一種方法，故我們可以把動態規劃中的每一個狀態看成一個點，并將狀態的轉移過程變為一個圖。在轉化為最小費用最大流時，我們把這一個點拆成兩個點，一個出點和一個入點，所有指向原來這個點的邊都與入點相連，且所有由原來這個點發出的邊現都以出點為起點。原來的邊的容量設為正無窮，邊權值一般不變。新增的入點與出點之間連一條邊，它的權值為點權值，容量為每一點可以經過的次數（一般為一）。并且建立一個超級源和一個超級匯，并與可能的入點和出點連邊。若有必要，超級源（或匯）也要拆成兩個點，并且兩個點之間的邊的容量為最大的可能容量，邊權值為0。這樣，用最小費用流的方法得出的解就是該問題多維情況下的接。