1、1,IV.動(dòng)態(tài)規(guī)劃,2,4.1引言,50年代1951年，R.Bellman 等人提出 多階段決策問(wèn)題; 1957年， 出版“動(dòng)態(tài)規(guī)劃”。 優(yōu)點(diǎn)：對(duì)許多問(wèn)題，比線(xiàn)性規(guī)劃或非線(xiàn)性規(guī)劃更有效。 弱點(diǎn)： （1）得出函數(shù)方程后，尚無(wú)統(tǒng)一處理方法； （2）維數(shù)屏蔽:變量個(gè)數(shù)（維數(shù)）太大時(shí)無(wú)法解決。 模型分類(lèi) 時(shí)間參量 確定隨機(jī),3,4.2 確定連續(xù)性問(wèn)題 （1）,例4.2.1在 的約束下，或 的極大值。 對(duì)應(yīng)遞推關(guān)系 令,4,4.2 確定連續(xù)性問(wèn)題 （2）,故 得x=a/3， 用歸納法可證明 當(dāng),5,例4.2.2.最短距離（1）,求O到T的最短距離(只沿正向前進(jìn))。 解：O到T的最短路徑，也是該路徑上點(diǎn)到

2、T的最短路徑,3,3,4,6,例4.2.2.最短距離（2）,7,例4.2.2.最短距離（3）,故O到T的最短距離為11，路徑為 OBD/EHKNRT 一般地，從（0，0）到（m，n）最短距離：窮舉法 加法： 比較： 動(dòng)態(tài)規(guī)則法： 加法： 2mn（mn2） 比較： mn 即窮舉法是n的指數(shù)級(jí)，而動(dòng)態(tài)規(guī)則是平方級(jí)。,8,4.3動(dòng)態(tài)規(guī)則的基本概念,9,4.4典型應(yīng)用 最優(yōu)二叉查找樹(shù) (1),例：最優(yōu)二叉查找樹(shù) 簡(jiǎn)化的情形：只考慮找到的情形； LR,L,R,C k,10,最優(yōu)二叉查找樹(shù) (2),計(jì)算矩陣 （由查找樹(shù)的特點(diǎn)可知）,11,最優(yōu)二叉查找樹(shù) (3),計(jì)算過(guò)程： 根：1 對(duì)應(yīng)于： 2 1 1 2

3、 同樣可得 根：3 根：4 根：4,12,最優(yōu)二叉查找樹(shù) (4),計(jì)算含有三個(gè)點(diǎn)的情形： 根：1 根：4 根：4,13,最優(yōu)二叉查找樹(shù) (5),四個(gè)點(diǎn)： 根：4 根：4 最后： 根：4,14,4,5,1,3,2,得到的最優(yōu)查找樹(shù)如下,15,圖上的最短路徑 (1),例：圖上的最短路徑 令 為 到終點(diǎn)的最短距離， 為與 相鄰點(diǎn)集合： ，則一般地,16,圖上的最短路徑 (2),動(dòng)態(tài)規(guī)則算法 : k=1: k=2:,17,圖上的最短路徑 (3),k=3: k=4: k=5: 即k=5時(shí)已無(wú)改變。對(duì)n個(gè)頂點(diǎn)問(wèn)題，迭代次數(shù)不超過(guò)n1次。 求兩者最短距離時(shí) k1 最佳原理：不論前面地狀態(tài)和策略如何，以后的最

4、優(yōu)策 略只取決于由最初策略所決定的當(dāng)前狀態(tài)。,18,整數(shù)規(guī)劃問(wèn)題 (1),例：某工廠購(gòu)進(jìn)1000臺(tái)機(jī)器，準(zhǔn)備生產(chǎn)甲、乙兩種產(chǎn)品，若生產(chǎn)產(chǎn)品甲，每年收入4500元，損壞率達(dá)65；若生產(chǎn)產(chǎn)品乙，每年收入3500元，但損壞率為35；估計(jì)3年后有新機(jī)器購(gòu)進(jìn)，舊機(jī)器全部淘汰。問(wèn)應(yīng)如何安排生產(chǎn)，使3年內(nèi)收入最多？（計(jì)劃以一年為周期） 該問(wèn)題為整數(shù)規(guī)劃問(wèn)題：該生產(chǎn)產(chǎn)品甲的機(jī)器數(shù)分別為 ， 三年中生產(chǎn)產(chǎn)品乙的機(jī)器數(shù)分別為 ，則 為整數(shù)，i1，2，3。 設(shè) 為n臺(tái)機(jī)器在i年后的最大收益，若安排一年生產(chǎn)為生產(chǎn)產(chǎn)品甲的數(shù)目，則一年后最大收益:,19,整數(shù)規(guī)劃問(wèn)題 (2),考慮兩年生產(chǎn)， 為兩年中第一年生產(chǎn)產(chǎn)品甲的機(jī)

5、器數(shù)目： 三年中第一年生產(chǎn)機(jī)器甲的數(shù)目為 故第一年全部生產(chǎn)產(chǎn)品乙；第二年繼續(xù)生產(chǎn)乙；第三年生產(chǎn)產(chǎn)品甲 實(shí)際產(chǎn)品收入為,20,從頂點(diǎn) 出發(fā)，經(jīng) 回到 的最短路徑。 可能路徑：n！ 令 表示從 出發(fā)，經(jīng)V中各點(diǎn)一次，最后返回的最短路徑；其中V為一頂點(diǎn)集合，則,貨郎擔(dān)（旅行商）問(wèn)題 (1),21,貨郎擔(dān)（旅行商）問(wèn)題 (2),22,貨郎擔(dān)（旅行商）問(wèn)題 (3),23,復(fù)雜性分析 （1）,一般情況： 令結(jié)點(diǎn)為 ， 為起始點(diǎn)，,24,復(fù)雜性分析 （2）,第1層 1 第2層 第3層 第k層 故如果利用一個(gè)單元存儲(chǔ)一個(gè) ，則存儲(chǔ)單元數(shù)為 空間當(dāng)為,25,時(shí)間復(fù)雜度,第1層 n 第2層 n-1 第3層 n-2

6、 第k層 nk1 該問(wèn)題目前有效解法基本上為各式概率算法 :,26,習(xí)題,求： (1) max z=110 x1+160 x2+260 x3+210 x4 2x1+3x2+5x3+4x420 為零或正整數(shù) (2) x1+x2+x3100 x1，x2，x30,27,背包問(wèn)題(1),max z= c1x1+ c2x2+ cnxn a1x1+ a2x2+ anxnb xi=0,1. i=1,2,n. 令 計(jì)算：,28,背包問(wèn)題(2),29,背包問(wèn)題(3),故最優(yōu)解為max z=6，當(dāng)x1 x31, x20時(shí) 若 取實(shí)數(shù)，則應(yīng)當(dāng)使單位容量獲利最大 三種物品123 2/13/24/5 取x11， x21

7、，x3（61x12 x2）/5=3/5。,30,Viterbi譯碼算法,31,狀態(tài)轉(zhuǎn)移 1/10 1/01 0/01 0/10 1/00 1/11 0/11 0/00,11,10,01,00,32,狀態(tài)： 輸入1或0時(shí)，進(jìn)入新?tīng)顟B(tài)，產(chǎn)生輸出 譯碼時(shí) Code Trellis 考慮所收到碼字：11 10 11 11 01 01 11,33,矩陣鏈積可能的方法,34,例：考慮 個(gè)矩陣的積，每個(gè) 的為 10*20 20*50 50*1 1*100 M1*（M2*（M3*M4）： 125，000 （M1*（M2*M3）*M4： 2200 Mi,i=0 For l=1 to n For I=1 to n-1 j=i+1; Mij=min i=kj (mik+mk+1j+(ri-1*rk*rj),3