動態(tài)規(guī)劃ppt課件(2)-展示頁
2025-05-15 12:08本頁面
【正文】 mited。 f(5) f(3) f(2) f(1) f(2) f(4) f(0) f(1) f(0) f(3) f(2) f(1) f(1) f(0) f(1) 1 1 0 0 1 0 1 0 冗余計算 動態(tài)規(guī)劃 ? 例： POJ 2753 Fibonacci數(shù)列 int f[n+1]。 int I。i=n。 cout f[n] endl。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。 同一個問題可以有多種 方式刻劃 它 的最優(yōu)子結構，有些表示方法的求解速度更快（空間占用小，問題的維度低） 例如：最短路徑問題。 動態(tài)規(guī)劃算法的基本要素 二、重疊子問題 ?遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。 ?動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結果。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 將該問題劃分為 4個階段的決策問題 第一階段為從 A到 Bj（ j=1， 2， 3） ， 有三種決策方案可供選擇； 第二階段為從 Bj到 Cj（ j=1,2,3） ， 也有三種方案可供選擇； 第三階段為從 Cj到 Dj(j=1,2)， 有兩種方案可供選擇；第四階段為從 Dj到 E， 只有一種方案選擇 。 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 ? 顯然，這種方法是不經(jīng)濟的，特別是當階段數(shù)很多，各階段可供的選擇也很多時，這種解法甚至在計算機上完成也是不現(xiàn)實的。 第三階段 ， 由 Cj到 Di分別均有兩種選擇 ， 即 ? ? ? ?? ? 644 33m i nDfDC DfDCm i nCf2421141113 ????????????????????? ?， 決策點為 D1 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 ? ? ? ?? ? 643 *33m i nDfDC DfDCm i nCf2423141333 ??????????????????? ,決策點為 D1 ? ? ? ?? ? 7*43 36m i nDfDC DfDCm i nCf2422141223 ???????????????????， 決策點為 D2 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 第二階段，由 Bj到 Cj分別均有三種選擇，即： ? ?? ?? ?? ?11667467m i nCfCBCfCBCfCBm i nBf *33332322131112 ?????????????????????????????決策點為 C2 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 ? ?? ?? ?? ?96472*63m i nCfCBCfCBCfCBm i nBf *33332322132222 ?????????????????????????????決策點為 C1或C2 ? ?? ?? ?? ?9657266m i nCfCBCfCBCfCBm i nBf *33332323131332 ????????????????????????????? 決策點為 C2 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 第一階段 ， 由 A到 B， 有三種選擇 ， 即： ? ?? ?? ?? ?12*9394112m i nBfABBfABBfABm i nAf5252222211 ????????????????????????????? 決策點為 B3 f1（ A） =15說明從 A到 E的最短距離為 12， 最短路線的確定可按計算順序反推而得 。 圖中紅箭線表示從 A到 E的最短路線 。 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 3 4 6 7 6 9 9 11 12 所謂多階段決策問題是： 把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程 ， 也稱為序貫決策過程 。 即是從全局考慮解決局部（ 階段 ） 的問題 。 因此 ， 把這種方法稱為動態(tài)規(guī)劃方法 。 攔截導彈 （ poj1887 ） ? 某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。某天，雷達捕捉到敵國的導彈來襲。 ? 輸入 輸入數(shù)據(jù)為導彈依次飛來的高度，所有高度值均為不大于 30000的正整數(shù)。 ? 輸入樣例 389 207 155 300 299 170 158 65 ? 輸入樣例 6 題目分析 ? 因為只有一套導彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達任意高度外，以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以，被攔截的導彈應該按飛來的高度組成一個非遞增序列。 ? 設 X={x1,x2,… ,xn}為依次飛來的導彈序列，Y={y1,y2,… ,yk}為問題的最優(yōu)解（即 X的最長非遞增子序列）， s為問題的狀態(tài)（表示導彈攔截系統(tǒng)當前發(fā)送炮彈能夠到達的最大高度，初值為 s=∞ —— 第一發(fā)炮彈能夠到達任意的高度）。那么，根據(jù)題意 “ 每一發(fā)炮彈都不能高于前一發(fā)的高度 ” ，問題的狀態(tài)將由s=∞ 變成 s≤x1 （ x1為第一枚導彈的高度）； ? 在當前狀態(tài)下，序列 Y1={y2,… ,yk}也應該是序列 X1={x2,… ,xn}的最長非遞增子序列（大家用反證法很容易證明）。這就是攔截導彈問題的最優(yōu)子結構性質(zhì)。 ? 我們可以設想，當系統(tǒng)攔截了第 k枚導彈 xk，而 xk又是序列 X={x1,x2,… ,xn}中的最小值，即第 k枚導彈為所有飛來的導彈中高度最低的，則有D(k)=1；當系統(tǒng)攔
教學課件相關推薦
鄂ICP備17016276號-1