《動(dòng)態(tài)規(guī)劃》ppt課件 (2)-全文預(yù)覽
【正文】 max=0。 //輸入高度 d[count1]=1。這樣，每個(gè) D（ i）的值只計(jì)算一次，并在計(jì)算的同時(shí)把計(jì)算結(jié)果保存下來，從而避免了有些子問題被重復(fù)計(jì)算的情況發(fā)生，提高了程序的效率。比如在調(diào)用遞歸函數(shù)計(jì)算 D（ 1）的時(shí)候，可能需要先計(jì)算 D（ 5）的值；之后在分別調(diào)用遞歸函數(shù)計(jì)算 D（ 2）、 D（ 3）、 D（ 4）的時(shí)候，都有可能需要先計(jì)算 D（ 5）的值。 ? 根據(jù)以上分析，可歸納出問題的動(dòng)態(tài)規(guī)劃遞歸方程為： ? 假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為 dmax（即問題的最優(yōu)值），則 ? dmax （ i為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號(hào)） ? 所以，要計(jì)算問題的最優(yōu)值 dmax，需要分別計(jì)算出 D（ 1）、 D（ 2）、 …… D（ n）的值，然后將它們進(jìn)行比較，找出其中的最大值。 ? 也就是說，在當(dāng)前狀態(tài) s≤x1 下，問題的最優(yōu)解 Y所包含的子問題（序列 X1）的解（序列 Y1）也是最優(yōu)的。 ? 題目要求我們計(jì)算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)，并依次輸出被攔截導(dǎo)彈的高度，實(shí)際上就是要求我們?cè)趯?dǎo)彈依次飛來的高度序列中尋找一個(gè)最長非遞增子序列。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 ④ 決策過程是與階段發(fā)展過程逆向而行 。 如下圖所示： 決策 決策 決策狀態(tài) 狀態(tài) 狀態(tài) 狀態(tài) 狀態(tài)1 2 n② 在處理各階段決策的選取上 ， 不僅只依賴于當(dāng)前面臨的狀態(tài) ， 而且還要注意對(duì)以后的發(fā)展 。 即 A→B 3→C 2→D 2→E 上述最短路線問題的計(jì)算過程 ， 也可借助于圖形直觀的表示出來： 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 圖中各點(diǎn)上方框的數(shù) ， 表示該點(diǎn)到 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 3 2 1=18（條 ） ， 將其一一比較才可找出最短路線： A→B 1→C 2→D 3→E 其長度為 12。 ?通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長。 a b c ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 用空間換時(shí)間 動(dòng)態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。 for(i=3。而不是可愛的AC Why？ 子問題的重疊性 ? 將上述遞歸算法展開 : ? 可以看出 f(n1) 被調(diào)用 1次 , f(n2)被調(diào)用 2次 , 等等 . ? 這將導(dǎo)致大量的調(diào)用 ? 最終解為： 樹形遞歸 計(jì)算過程中存在冗余計(jì)算，為了除去冗余計(jì)算，可以從已知條件開始計(jì)算，并記錄計(jì)算過程中的中間結(jié)果。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。 如果一個(gè)問題可將其過程劃分為若干個(gè)相互聯(lián)系的階段問題 ，且它的每一階段都需進(jìn)行決策 ， 則這類問題均可用動(dòng)態(tài)規(guī)劃方法進(jìn)行求解 。 動(dòng)態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法 。 作人生規(guī)劃要善于利用動(dòng)態(tài)規(guī)劃； 找女朋友要善于利用好貪心算法； 人生重大決策要活學(xué)活用回溯法； 算法總體思想 ? 動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 為什么動(dòng)態(tài)規(guī)劃比遞歸算法有效？ ? 但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。 n = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) POJ 2753 Fibonacci數(shù)列例子： ? 確定 Fibonacci sequence fn項(xiàng)的值 : ? 考慮 Fibonacci sequence的遞歸定義 : ? 我們將得到如下的遞歸算法 : 在 POJ上遞交之后，返回的結(jié)果是：Time Limited。 int I。 cout f[n] endl。 同一個(gè)問題可以有多種 方式刻劃 它 的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低） 例如：最短路徑問題。 ?動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 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個(gè)階段的決策問題 第一階段為從 A到 Bj（ j=1， 2， 3） ， 有三種決策方案可供選擇； 第二階段為從 Bj到 Cj（ j=1,2,3） ， 也有三種方案可供選擇； 第三階段為從 Cj到 Dj(j=1,2)， 有兩種方案可供選擇；第四階段為從 Dj到 E， 只有一種方案選擇 。 第三階段 ， 由 Cj到 Di分別均有兩種選擇 ， 即 ? ? ? ?? ? 644 33m i nDfDC DfDCm i nCf2421141113 ????????????????????? ?， 決策點(diǎn)為 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 ??????????????????? ,決策點(diǎn)為 D1 ? ? ? ?? ? 7*43 36m i nDfDC DfDCm i nCf2422141223 ???????????????????， 決策點(diǎn)為 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 ?????????????????????????????決策點(diǎn)為 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 nCfCBCfCBCfCB
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1