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

　　動(dòng)態(tài)規劃的狀態(tài)表示(三)

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

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

　　下面就多路徑問(wèn)題來(lái)說(shuō)明這點(diǎn)。

　　問(wèn)題四：

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

　　2 3 2 3

　　3 4 5 3 4 5

　　9 1 9 1 9 1 9 1

　　最小的m路徑得分=15

　　顯然，這個(gè)問(wèn)題與問(wèn)題一極其類(lèi)似。

　　如果m=1, 那就是問(wèn)題一所要解決的問(wèn)題。

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

　　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時(shí)，可以采取類(lèi)似m=2采用的狀態(tài)表示。

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

　　當m恒定時(shí)，空間復雜度隨n呈多項式變化。當n恒定時(shí)，隨著(zhù)m的增大空間復雜度呈指數形式增長(cháng)。

　　比如n=100 ，

　　當 m=2時(shí)，需要104 byte;

　　當 m=3時(shí)，需要106 byte;

　　當m=4時(shí)，需要108 byte;

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

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

　　把數字梯形看成是有向圖，對任意數字U看成兩個(gè)頂點(diǎn)u1、u2,容量c(u1,u2)=1, 費用g(u1,u2)=U。若數字U沿對角線(xiàn)可到達數字V,則 c(u2,v1)=1, g(u2,v1)=0; 增加超級源s, 對于第一層數字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。

　　五、總結

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

　　1、動(dòng)態(tài)規劃的狀態(tài)表示描述的子問(wèn)題必須滿(mǎn)足最優(yōu)子結構性質(zhì)，否則無(wú)法建立正確的動(dòng)態(tài)規劃模型。

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

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

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