動態(tài)規(guī)劃的使用條件

1、動態(tài)規(guī)劃的適用條件任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。 同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化 原理和無后效性。最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀 態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu) 成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問 題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì) 。圖2例如圖2中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理， 路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑 J是B到C的最優(yōu)路徑，則A到C的路線取I和

2、J比I和J更優(yōu)，矛盾。 從而證明J必是B到C的最優(yōu)路徑。最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支 持，就不可能用動態(tài)規(guī)劃方法計算。動態(tài)規(guī)劃的最優(yōu)化理在其指標函數(shù) 的可分離性和單調(diào)性中得到體現(xiàn)。根據(jù)最優(yōu)化原理導(dǎo)出的動態(tài)規(guī)劃基本 方程是解決一切動態(tài)規(guī)劃問題的基本方法?？梢钥闯觯?是滿足最優(yōu)化原理的。無后向性將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以 前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當前的這個狀 態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向 性，又稱為無后效性。如果用前面的記號來描述無后向性，就是：對于確定的xk，無論p

3、,k-1 如何，最優(yōu)子策略pkn*是唯一確定的，這種性質(zhì)稱為無后向性。例3 Bitonic旅行路線問題歐幾里德貨郎擔(dān)問題是對平面給定的n個點確定一條連結(jié)各點的、閉合 的最短游歷路線問題。圖3(a)給出了七個點問題的解。Bitonic旅行路線 問題是歐幾里德貨郎擔(dān)問題的簡化，這種旅行路線先從最左邊開始，嚴 格地由左至右到最右邊的點，然后再嚴格地由右至左到出發(fā)點，求路程 最短的路徑長度。圖3(b)給出了七個點問題的解。這兩個問題看起來很相似。但實質(zhì)上是不同的。為了方便討論，我將每 個頂點標記了號碼。由于必然經(jīng)過最右邊的頂點7,所以一條路(P1-P2) 可以看成兩條路(P1-7)與(P2-7)的結(jié)合

4、。所以，這個問題的狀態(tài)可以 用兩條道路結(jié)合的形式表示。我們可以把這些狀態(tài)中，兩條路中起始頂 點相同的狀態(tài)歸于一個階段，設(shè)為階段P1,P2。那么，對于Bitonic旅行路線問題來說，階段P1,P2如果可以由階段 Q1,Q2推出，則必須滿足的條件就是:P1Q1或P2Q2。例如，階段3,4 中的道路可以由階段3,5中的道路加一條邊4-5得出，而階段3,5的狀 態(tài)卻無法由階段3,4中的狀態(tài)得出，因為Bitonic旅行路線要求必須嚴 格地由左到右來旅行。所以如果我們已經(jīng)知道了階段3,4中的狀態(tài)，則 階段3,5中的狀態(tài)必然已知。因此我們可以說，Bitonic問題滿足無后向 性，可以用動態(tài)規(guī)劃來解決。有些問

5、題乍一看好像有后向性，但如果按照某種合理的方式重新劃分階 段，就可以發(fā)現(xiàn)其本質(zhì)上是無后向性的，所以關(guān)鍵是階段的合理劃分， 這一點將在動態(tài)規(guī)劃的技巧中詳細闡述。子問題的重疊性在例1中我們看到，動態(tài)規(guī)劃將原來具有指數(shù)級復(fù)雜度的搜索算法改進 成了具有多項式時間的算法。其中的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃 算法的根本目的。動態(tài)規(guī)劃實質(zhì)上是一種以空間換時間的技術(shù)，它在實 現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度 要大于其它的算法。以Bitonic旅行路線問題為例，這個問題也可以用 搜索算法來解決。動態(tài)規(guī)劃的時間復(fù)雜度為O(n2)，搜索算法的時間復(fù) 雜度為O(n!)，但從空間復(fù)雜度來看，動態(tài)規(guī)劃算法為O(n2)，而搜索 算法為O(n)，搜索算法反而優(yōu)于動態(tài)規(guī)劃算法。選擇動態(tài)規(guī)劃算法是因 為動態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受， 所以我們舍空間而取時間。設(shè)原問題的規(guī)模為n，容易看出，當子問題樹中的子問題總數(shù)是n的超 多項式函數(shù)，而不同的子問題數(shù)只是n的多項式函數(shù)時，動態(tài)規(guī)劃法顯 得特別有意義，此時動態(tài)規(guī)劃法具有線性時間復(fù)雜性