算法設計與分析動態(tài)規(guī)劃

算法設計與分析動態(tài)規(guī)劃第1頁，課件共42頁，創(chuàng)作于2023年2月第十一章動態(tài)規(guī)劃（一）動態(tài)規(guī)劃概念矩陣鏈乘法（過程及分析）問題描述最優(yōu)括號化分析計算最優(yōu)代價構造最優(yōu)解動態(tài)規(guī)劃的基本內(nèi)容最優(yōu)結構重疊子問題記憶化程序演示及說明第2頁，課件共42頁，創(chuàng)作于2023年2月預備知識1.分治法與動態(tài)規(guī)劃的關系

（1）分治法的基本思想：將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題類型相同。遞歸地解這些子問題，然后將各子問題的解并到原問題的解。（2）動態(tài)規(guī)劃基本思想：是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是：適合于動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是相互獨立的。

動態(tài)規(guī)劃算法通常用于求解具有某種具有最優(yōu)性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應一個值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個解。（3）20世紀50年代由貝爾曼等人提出多階段決策特性，并提出“最優(yōu)性原理”，從而創(chuàng)建了動態(tài)規(guī)劃這種新的算法設計方法。動態(tài)規(guī)劃的目標就是要在所有允許選擇的決策序列中選擇一個會獲得問題最優(yōu)解的決策序列。第3頁，課件共42頁，創(chuàng)作于2023年2月預備知識2.兩矩陣相乘的充分必要條件是第一個矩陣的列數(shù)與第二個矩陣的行數(shù)相等。第4頁，課件共42頁，創(chuàng)作于2023年2月動態(tài)程序算法設計四步曲第5頁，課件共42頁，創(chuàng)作于2023年2月矩陣鏈乘法第6頁，課件共42頁，創(chuàng)作于2023年2月矩陣鏈乘法第7頁，課件共42頁，創(chuàng)作于2023年2月矩陣鏈乘法第8頁，課件共42頁，創(chuàng)作于2023年2月矩陣鏈乘法第9頁，課件共42頁，創(chuàng)作于2023年2月計算括號化重數(shù)第10頁，課件共42頁，創(chuàng)作于2023年2月計算括號化重數(shù)P(1)=1P(2)=1P(3)=p(1)*p(2)+p(2)*p(1)=1*1+1*1=2P(4)=p(1)*p(3)+p(2)*p(2)+p(3)*p(1)=1*2+1*1+2*1=5P(5)=p(1)*p(4)+p(2)*p(3)+p(3)*p(2)+ p(4)*p(1)=1*5+1*2+2*1+5*1=14第11頁，課件共42頁，創(chuàng)作于2023年2月計算括號化重數(shù)P(n)=1n=1n>=22*第12頁，課件共42頁，創(chuàng)作于2023年2月計算括號化重數(shù)P(1)=p(2)=1P(3)=2*(P(1)*P(2))=2P(4)=2*(P(1)*P(3)+P(2)*P(2)/2) =2*2.5=5P(5)=2*(P(1)*P(4)+P(2)*P(3))=2*(5+2)=14第13頁，課件共42頁，創(chuàng)作于2023年2月計算括號化重數(shù)第14頁，課件共42頁，創(chuàng)作于2023年2月計算括號化重數(shù)第15頁，課件共42頁，創(chuàng)作于2023年2月最優(yōu)括號化的結構第16頁，課件共42頁，創(chuàng)作于2023年2月一個遞歸解第17頁，課件共42頁，創(chuàng)作于2023年2月一個遞歸解第18頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價第19頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價第20頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價第21頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價為下列矩陣序列求解最優(yōu)解第22頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價步長為0，1m[1,1]=m[2,2]=m[3,3]=m[4,4]=m[5,5]=m[6,6]=0m[1,2]=min{m[1,1]+m[2,2]+p0*p1*p2}=30*35*15=15750S[1,2]=1m[2,3]=min{m[2,2]+m[3,3]+p1*p2*p3}=35*15*5=2625S[2,3]=2m[3,4]=min{m[3,3]+m[4,4]+p2*p3*p4}=15*5*10=750S[3,4]=3m[4,5]=min{m[4,4]+m[5,5]+p3*p4*p5}=5*10*20=1000S[4,5]=4m[5,6]=min{m[5,5]+m[6,6]+p4*p5*p6}=10*20*25=5000S[5,6]=5第23頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價步長為2m[1,3]=min{m[1,1]+m[2,3]+p0*p1*p3,m[1,2]+m[2,3]+p0*p2*p3} =min{0+2625+30*35*5,15750+0+30*15*5}=min{7875,18000}=7875S[1,3]=1 m[2,4]=min{m[2,2]+m[3,4]+p1*p2*p4,m[2,3]+m[4,4]+p1*p3*p4} =min{0+750+35*15*10,2625+0+35*5*10} =min{6000,4375}=4375S[2,4]=3第24頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價m[3,5]=min{m[3,3]+m[4,5]+p2*p3*p5,m[3,4]+m[5,5]+p2*p4*p5}=min{0+1000+15*5*20,750+0+15*10*20}=min{2500,3750}=2500S[3,5]=3m[4,6]=min{m[4,4]+m[5,6]+p3*p4*p6,m[4,5]+m[6,6]+p3*p5*p6}=min{0+5000+5*10*25,1000+0+5*20*25}=min{6250,3500}=3500S[4,6]=5第25頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價步長為3m[1,4]=min{m[1,1]+m[2,4]+p0*p1*p4,m[1,2]+m[3,4]+p0*p2*p4,m[1,3]+m[4,4]+p0*p3*p4}=min{0+4375+30*35*10,15750+750+30*15*10,7875+0+35*5*10}=min{14875,21000,9375}=9375s[1,4]=3m[2,5]=min{m[2,2]+m[3,5]+p1*p2*p5,m[2,3]+m[4,5]+p1*p3*p5,m[2,4]+m[5,5]+p1*p4*p5}=min{0+2500+35*15*20,2625+1000+35*5*20,4375+0+35*10*20}=min{13000,7125,11375}=7025S[2,5]=3第26頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價M[3,6]=min{m[3,3]+m[4,6]+p2*p3*p6,m[3,4]+m[5,6]+p2*p4*p6,m[3,5]+m[6,6]+p2*p5*p6}=min{0+3500+15*5*25,750+5000+15*10*25,7500+0+15*20*25}=min{5375,9500,10000}=5375S[3,6]=3第27頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價步長為4M[1,5]=min{m[1,1]+m[2,5]+p0*p1*p5,m[1,2]+m[3,5]+p0*p2*p5,m[1,3]+m[4,5]+p0*p3*p5,m[1,4]+m[5,5]+p0*p4*p5}=min{0+7125+30*35*20,15750+2500+36*15*20,7875+1000+30*5*20,9375+0+30*10*20}=min{28125,27250,11875,15375}=11875S[1,5]=3M[2,6]=min{m[2,2]+m[3,6]+p1*p2*p6,m[2,3]+m[4,6]+p1*p3*p6,m[2,4]+m[5,6]+p1*p4*p6,m[2,5]+m[6,6]+p1*p5*p6}=min{0+5357+35*15*25,2625+3500+35*5*25,4375+5000+35*10*25,7125+0+35*20*25}=min{18500,10500,18125,24625}=10500S[2,6]=3第28頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價步長為5m[1,6]=min{m[1,1]+m[2,6]+p0*p1*p6,m[1,2]+m[3,6]+p0*p2*p6,m[1,3]+m[4,6]+p0*p3*p6,m[1,4]+m[5,6]+p0*p4*p6, m[1,5]+m[6,6]+p0*p5*p6}=min{0+10500+30*35*25,15750+5375+30*15*25,7875+3500+30*5*25,9375+5000+30*10*25, 11875+0+30*20*25}=min{36750,32375,15125,21875,26875}=15125S[1,6]=3第29頁，課件共42頁，創(chuàng)作于2023年2月計算最優(yōu)代價第30頁，課件共42頁，創(chuàng)作于2023年2月構造最優(yōu)解第31頁，課件共42頁，創(chuàng)作于2023年2月構造最優(yōu)解第32頁，課件共42頁，創(chuàng)作于2023年2月動態(tài)程序設計基礎

從工程的角度看,對一個具體問題,我們在什么樣的情況下需要有一個動態(tài)程序設計解?在這一節(jié)里,我們要介紹適合采用動態(tài)程序設計方法的最優(yōu)化問題中的兩個要素:最優(yōu)結構和重疊子問題.并討論另一個稱作記憶化的方法,以充分利用重疊子問題性質.第33頁，課件共42頁，創(chuàng)作于2023年2月最優(yōu)結構1、一個問題具有最優(yōu)子結構，則該問題的最優(yōu)解中包含了子問題的最優(yōu)解。當一個問題呈現(xiàn)出最優(yōu)子結構時，動態(tài)程序設計可能就是一個合適的侯選方法。矩陣鏈乘法問題具有最優(yōu)子結構.可以用反證法證明子問題具有最優(yōu)解.

2、一個問題的最優(yōu)子結構常常暗示了可應用動態(tài)程序設計方法的一個子問題空間。找出合適的動態(tài)程序設計的子問題空間的一個方法是通過對子問題實例的疊代來考察一個問題的最優(yōu)子結構。第34頁，課件共42頁，創(chuàng)作于2023年2月重疊子問題1、適合于動態(tài)程序設計方法解決的最優(yōu)化問題必須具有的第二個要素是子問題空間要“很小”，即用來解原來問題的一個遞歸算法可反復地解同樣的子問題，而不產(chǎn)生新的子問題。當一個遞歸算法不斷地遇到同一問題，則該最優(yōu)化問題包含有重疊子問題。動態(tài)程序設計方法總是充分利用重疊子問題，對每個子問題只解一次，把解放在一個在需要時就可查看的表中，而每一次查表的時間為常數(shù)。第35頁，課件共42頁，創(chuàng)作于2023年2月重疊子問題2、確定m[i,j]的低效的遞歸算法第36頁，課件共42頁，創(chuàng)作于2023年2月重疊子問題

調(diào)用RECURSIVE-MATRIX-CHAIN(p,1,4)所產(chǎn)生的遞歸樹如圖16.2所示第37頁，課件共42頁，創(chuàng)作于2023年2月重疊子問題3、由此遞歸過程計算m[1,n]的運行時間T（n）至少為n的指數(shù)