動態(tài)規(guī)劃實現(xiàn)中的問題

1、動態(tài)規(guī)劃實現(xiàn)中的問題應(yīng)用動態(tài)規(guī)劃解決問題，在有了基本的思路之后，一般來說，算法實現(xiàn) 是比較好考慮的。但有時也會遇到一些問題，而使算法難以實現(xiàn)。動態(tài) 規(guī)劃思想設(shè)計的算法從整體上來看基本都是按照得出的遞推關(guān)系式進 行遞推，這種遞推相對于計算機來說，只要設(shè)計得當(dāng)，效率往往是比較 高的，這樣在時間上溢出的可能性不大，而相反地，動態(tài)規(guī)劃需要很大 的空間以存儲中間產(chǎn)生的結(jié)果，這樣可以使包含同一個子問題的所有問 題共用一個子問題解，從而體現(xiàn)動態(tài)規(guī)劃的優(yōu)越性，但這是以犧牲空間 為代價的，為了有效地訪問已有結(jié)果，數(shù)據(jù)也不易壓縮存儲，因而空間 矛盾是比較突出的。另一方面，動態(tài)規(guī)劃的高時效性往往要通過大的測 試數(shù)據(jù)

2、體現(xiàn)出來（以與搜索作比較），因而，對于大規(guī)模的問題如何在 基本不影響運行速度的條件下，解決空間溢出的問題，是動態(tài)規(guī)劃解決 問題時一個普遍會遇到的問題。對于這個問題，可以考慮從以下一些方面去嘗試：一個思考方向是盡可能少占用空間。如從結(jié)點的數(shù)據(jù)結(jié)構(gòu)上考慮，僅僅 存儲必不可少的內(nèi)容，以及數(shù)據(jù)存儲范圍上精打細算（按位存儲、壓縮 存儲等）。當(dāng)然這要因問題而異，進行分析。另外，在實現(xiàn)動態(tài)規(guī)劃時， 一個我們經(jīng)常采用的方法是用一個與結(jié)點數(shù)一樣多的數(shù)組來存儲每一 步的決策，這對于倒推求得一種實現(xiàn)最優(yōu)解的方法是十分方便的，而且 處理速度也有一些提高。但是在內(nèi)存空間緊張的情況下，我們就應(yīng)該抓 住問題的主要矛盾。省去

3、這個存儲決策的數(shù)組，而改成在從最優(yōu)解逐級 倒推時，再計算一次，選擇某個可能達到這個值的上一階段的狀態(tài)，直 到推出結(jié)果為止。這樣做，在程序編寫上比上一種做法稍微多花一點時 間，運行的時效也可能會有一些（但往往很小）的下降，但卻換來了很多 的空間。因而這種思想在處理某些問題時，是很有意義的。但有時，即使采用這樣的方法也會發(fā)現(xiàn)空間溢出的問題。這時就要分析， 這些保留下來的數(shù)據(jù)是否有必要同時存在于內(nèi)存之中。因為有很多問題， 動態(tài)規(guī)劃遞推在處理后面的內(nèi)容時，前面比較遠處的內(nèi)容實際上是用不 著的。對于這類問題，在已經(jīng)確信不會再被使用的數(shù)據(jù)上覆蓋數(shù)據(jù)，從 而使空間得以重復(fù)利用，如果能有效地使用這一手段，對于

4、相當(dāng)大規(guī)模 的問題，空間也不至于溢出（為了求出最優(yōu)方案，保留每一步的決策仍 是必要的，這同樣需要空間）。一般地說，這種方法可以通過兩種思路來實現(xiàn)：一種是遞推結(jié)果僅使用 Data 1和Data2這樣兩個數(shù)組，每次將Datal作為上一階段，推得Data2 數(shù)組，然后，將Data2通過復(fù)制覆蓋到Datal之上，如此反復(fù)，即可推 得最終結(jié)果。這種做法有一個局限性，就是對于遞推與前面若干階段相 關(guān)的問題，這種做法就比較麻煩；而且，每遞推一級，就需要復(fù)制很多 的內(nèi)容，與前面多個階段相關(guān)的問題影響更大。另外一種實現(xiàn)方法是， 對于一個可能與前N個階段相關(guān)的問題，建立數(shù)組Data0.N，其中各 項為最近N各階段的保存數(shù)據(jù)。這樣不采用這種內(nèi)存節(jié)約方式時對于階 段k的訪問只要對應(yīng)成對數(shù)組Data中下標為k mod （N+1）的單元的訪問 就可以了。這種處理方法對于程序修改的代碼很少，速度幾乎不受影響， 而且需要保留不同的階段數(shù)也都能很容易實現(xiàn)。當(dāng)采用以上方法仍無法解決內(nèi)存問題時，也可以采用對內(nèi)存的動態(tài)申請 來使絕大多數(shù)情況