信息系統(tǒng)項目管理師綜合知識真題考點：動態(tài)規(guī)劃

使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃三要素：

(1)問題的階段

(2)每個階段的狀態(tài)

(3)從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系。

遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個角度來說，動態(tài)規(guī)劃往往可以用遞歸程序來實現(xiàn)，不過因為遞推可以充分利用前面保存的子問題的解來減少重復(fù)計算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢，這也是動態(tài)規(guī)劃算法的核心之處。確定了動態(tài)規(guī)劃的這三要素，整個求解過程就可以用一個最優(yōu)決策表來描述，最優(yōu)決策表是一個二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個階段某個狀態(tài)下的最優(yōu)值(如最短路徑，最長公共子序列，最大價值等)，填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運算求得問題的最優(yōu)解:f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

詳見官方教材《信息系統(tǒng)項目管理師教程》(第3版)878-881頁

考點相關(guān)真題

相關(guān)閱讀：信息系統(tǒng)項目管理師綜合知識真題考點匯總