信息學(xué)聯(lián)賽知識：動態(tài)規(guī)劃的狀態(tài)表示(三)

　　動態(tài)規(guī)劃的狀態(tài)表示(三)

　　四、多路徑問題的狀態(tài)表示

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

　　下面就多路徑問題來說明這點(diǎn)。

　　問題四：

　　存在一個數(shù)字梯形，最上層有m個數(shù)字，最底層有n個數(shù)字，每一層比上一層多一個數(shù)字，共有n-m+1層數(shù)字，如圖是m=2, n=4的數(shù)字梯形。從頂?shù)降子卸鄺l路徑，每一步可沿左斜線向下或沿右斜線向下。路徑所經(jīng)過的數(shù)字之和稱為路徑得分，從頂?shù)降椎膍條不相交路徑的得分總和稱為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]描述兩條路徑到達(dá)第x層y、z兩個位置的總得分。狀態(tài)轉(zhuǎn)移方程是

　　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]

　　當(dāng)m>=3時，可以采取類似m=2采用的狀態(tài)表示。

　　在狀態(tài)轉(zhuǎn)移方程中，第x層的得分只取決與x-1層的得分，利用這個性質(zhì)，實(shí)現(xiàn)時只要用兩個循環(huán)數(shù)組，空間復(fù)雜度為O(nm)。

　　當(dāng)m恒定時，空間復(fù)雜度隨n呈多項(xiàng)式變化。當(dāng)n恒定時，隨著m的增大空間復(fù)雜度呈指數(shù)形式增長。

　　比如n=100 ，

　　當(dāng) m=2時，需要104 byte;

　　當(dāng) m=3時，需要106 byte;

　　當(dāng)m=4時，需要108 byte;

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

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

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

　　五、總結(jié)

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

　　1、動態(tài)規(guī)劃的狀態(tài)表示描述的子問題必須滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，否則無法建立正確的動態(tài)規(guī)劃模型。

　　2、同一問題可能存在多種正確狀態(tài)表示方法，它們對應(yīng)的動態(tài)規(guī)劃算法的性能各不相同，從中選擇高效的狀態(tài)表示是動態(tài)規(guī)劃優(yōu)化的一個重要內(nèi)容。

　　3、對同一狀態(tài)表示而言，優(yōu)化它的實(shí)現(xiàn)方法對改進(jìn)動態(tài)規(guī)劃性能很有意義。

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