信息學聯賽知識：動態規劃的狀態表示(三)

　　動態規劃的狀態表示(三)

　　四、多路徑問題的狀態表示

　　動態規劃是一個非常高效的算法，但是對于一些問題它并不是一個理想的算法，這里面的原因很多，最主要的原因是它的維數障礙。

　　下面就多路徑問題來說明這點。

　　問題四：

　　存在一個數字梯形，最上層有m個數字，最底層有n個數字，每一層比上一層多一個數字，共有n-m+1層數字，如圖是m=2, n=4的數字梯形。從頂到底有多條路徑，每一步可沿左斜線向下或沿右斜線向下。路徑所經過的數字之和稱為路徑得分，從頂到底的m條不相交路徑的得分總和稱為m條路徑得分，求出最小的m路徑得分。

　　2 3 2 3

　　3 4 5 3 4 5

　　9 1 9 1 9 1 9 1

　　最小的m路徑得分=15

　　顯然，這個問題與問題一極其類似。

　　如果m=1, 那就是問題一所要解決的問題。

　　如果m=2, 與問題一采取的方法類似，可以用D[x,y,z]描述兩條路徑到達第x層y、z兩個位置的總得分。狀態轉移方程是

　　D[x,y,z] = Max{D[x-1,y,z],D[x-1,y,z-1],D[x-1,y-1,z],D[x-1,y-1,z-1]}

　　+A[x,y]+A[x,z],

　　D[1,y,z] = A[1,y]+A[1,z]

　　當m>=3時，可以采取類似m=2采用的狀態表示。

　　在狀態轉移方程中，第x層的得分只取決與x-1層的得分，利用這個性質，實現時只要用兩個循環數組，空間復雜度為O(nm)。

　　當m恒定時，空間復雜度隨n呈多項式變化。當n恒定時，隨著m的增大空間復雜度呈指數形式增長。

　　比如n=100 ，

　　當 m=2時，需要104 byte;

　　當 m=3時，需要106 byte;

　　當m=4時，需要108 byte;

　　我們看到當m=3時,基本的堆空間就不夠存儲了。在這個問題中，空間需要增長極為迅速，同時時間復雜度也是指數階的。目前動態規劃無法有效地處理這類問題，科學家把動態規劃這樣的缺點稱為動態規劃的維數障礙。它是兩方面的，包括空間和時間， 但是在空間要求方面的障礙顯得特別突出。

　　不論從空間上還是時間上考慮，動態規劃的維數障礙是難以克服的，這就在很大程度上限制了動態規劃的應用。所以，我們必須尋找其他的方法來解決這類問題。就這道題而言，網絡流是一個高效的算法。我們可以用最小費用流來解決問題，流網絡大致構造如下：

　　把數字梯形看成是有向圖，對任意數字U看成兩個頂點u1、u2,容量c(u1,u2)=1, 費用g(u1,u2)=U。若數字U沿對角線可到達數字V,則 c(u2,v1)=1, g(u2,v1)=0; 增加超級源s, 對于第一層數字U分成的頂點u1, c(s,u1)=1, g(s,u1)=0; 增加超級匯t，對于最底層頂點U分成的頂點u2, c(u2,t)=1,g(u2,t)=0; 其他頂點之間的容量為0。

　　五、總結

　　動態規劃實現并不復雜，適用于許多問題，在解決一般問題時是我們首選的算法之一。但是，動態規劃的數學模型的建立不是件容易的事，其中最困難也最重要的是狀態表示。通過以上分析，我們看到：

　　1、動態規劃的狀態表示描述的子問題必須滿足最優子結構性質，否則無法建立正確的動態規劃模型。

　　2、同一問題可能存在多種正確狀態表示方法，它們對應的動態規劃算法的性能各不相同，從中選擇高效的狀態表示是動態規劃優化的一個重要內容。

　　3、對同一狀態表示而言，優化它的實現方法對改進動態規劃性能很有意義。

　　4、在應用動態規劃方法解決問題時，應先估計問題的時間、空間，如果問題存在維數障礙，那么動態規劃的狀態表示很難滿足較大規模問題的空間要求， 我們必須另尋其他方法。