程序設計思路
在動態(tài)規(guī)劃中，可將一個問題的解決方案視為一系列決策的結果，要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列。所以在最短路徑問題中，假如在的第一次決策時到達了某個節(jié)點v，那么不管v 是怎樣確定的，此后選擇從v 到d 的路徑時，都必須采用最優(yōu)策略。利用最優(yōu)序列由最優(yōu)子序列構成的結論，可得到f 的遞歸式。f ( 1 ,c) 是初始時背包問題的最優(yōu)解。可使用（1）中所示公式通過遞歸或迭代來求解f ( 1 ,c)。從f (n, * )開始迭式， f (n, * )由第一個式子得出，然后由第二式遞歸計算f (i,*) ( i=n- 1，n- 2，⋯ ， 2 )，最后得出f ( 1 ,c)。動態(tài)規(guī)劃方法采用最優(yōu)原則（ principle of optimality）來建立用于計算最優(yōu)解的遞歸式。所謂最優(yōu)原則即不管前面的策略如何，此后的決策必須是基于當前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。由于對于有些問題的某些遞歸式來說并不一定能保證最優(yōu)原則，因此在求解問題時有必要對它進行驗證。若不能保持最優(yōu)原則，則不可應用動態(tài)規(guī)劃方法。
標簽：
程序設計
動態(tài)規(guī)劃
上傳時間：
2016-12-03
上傳用戶：kristycreasy
