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