icecream

基本動態(tài)規(guī)劃問題的擴展

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

一.   程序上的優(yōu)化：

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

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

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

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

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

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

從以上的討論可以看出，再從程序設(shè)計上對問題優(yōu)化時，要盡量減少問題的約束，盡可能的化為情況1。若不可以變?yōu)榍闆r1，那么就要仔細(xì)考慮數(shù)據(jù)上的聯(lián)系，設(shè)計好的數(shù)據(jù)結(jié)構(gòu)來解決問題。

二.   方程上的優(yōu)化：

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

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

我們可以從這個規(guī)劃方程上簡單的得到一個時間復(fù)雜度為O(n³)的算法。但是否會有更有效的算法呢？我們考慮一下w(i, j)的性質(zhì)。它表示的是結(jié)點i到結(jié)點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表示取到最優(yōu)值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]

在等式兩側(cè)同時加上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的時間復(fù)雜度為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個階段，故總時間復(fù)雜度為O(n²)。

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

我們在考慮IOI2000的POST問題。這一題的數(shù)學(xué)模型不是討論的重點，我們先不加討論，直接給出規(guī)劃方程 。從規(guī)劃方程直接得出的算法的時間復(fù)雜度為O(n³)。從這個規(guī)劃方程可以看出，它的每一階段都只與上一階段有關(guān)。故我們可以把方程變得簡單些，變?yōu)閷θ缦碌姆匠虉?zhí)行n次：

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

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

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

這一性質(zhì)對解題是應(yīng)該有所幫助的。仿照上例，在兩側(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]的大小關(guān)系之后，就可以決定是不是需要比較B[a, d]與B[b, d]的大小。[U1] 

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

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

三.   從低維向高維的轉(zhuǎn)化：

在問題擴大規(guī)模時，有一種方式就是擴大問題的維數(shù)。這時，規(guī)劃時決策變量的維數(shù)也要增加。這樣，存儲的空間也要隨著成指數(shù)級增加，導(dǎo)致無法存儲下所有的狀態(tài)，這就是動態(tài)規(guī)劃的維數(shù)災(zāi)難問題。如果我們還要在這種情況下使用動態(tài)規(guī)劃，那么就要使用極其復(fù)雜的數(shù)學(xué)分析方法。對于我們來說，使用這種方法顯然是不現(xiàn)實的。這時，我們就需要改造動態(tài)規(guī)劃的模型。通常我們都可以把這時的動態(tài)規(guī)劃模型變?yōu)榫W(wǎng)絡(luò)流模型。

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

除此之外，還有許多問題可以用該方法解決。例如最長區(qū)間覆蓋問題，在維數(shù)增加時也同樣可以用該方法解決。更進一步來說，甚至圖論的最短路問題也可以做同樣的轉(zhuǎn)化來求出特殊的最短路。不過一般來說轉(zhuǎn)化后流量最大為1，有許多特殊的性質(zhì)也沒有得到應(yīng)用，并且些復(fù)雜的動態(tài)規(guī)劃問題還無法轉(zhuǎn)化為網(wǎng)絡(luò)流問題（例如說最優(yōu)二叉樹問題），故標(biāo)準(zhǔn)的網(wǎng)絡(luò)流算法顯然有些浪費，它的解決還需要進一步的研究。

參考文獻：

[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]。它的證明如下：

我們設(shè)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]    有關(guān)這個問題的偽代碼如下：

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行的最小值，并假設(shè)Queue.H[0]=j。其中的h(a, b)函數(shù)是用二分查找法查找B(a, h)³ B(b, h)的最小的h值，h_OK為查找成功與否的標(biāo)志。在備選隊列Queue中的數(shù)據(jù)(K:i_r, H:h_r)的意義是：當(dāng)行數(shù)在區(qū)間[h_r-1, h_r-1]的范圍內(nèi)時，第i_r列為最小值。

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