人教部編版七年級下冊第三單元第21課-清朝前期的文學藝術獲獎課件【統(tǒng)編版】

第6章動態(tài)規(guī)劃***.第6章動態(tài)規(guī)劃***.

動態(tài)規(guī)劃(dynamicprogramming)是運籌學的一個分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領域的第一本著作。百度百科動態(tài)規(guī)劃(dynamicprogramming)WIKIPEDIAThetermdynamicprogrammingwasoriginallyusedinthe1940sbyRichardBellmantodescribetheprocessofsolvingproblemswhereoneneedstofindthebestdecisionsoneafteranother.Bellman'scontributionisrememberedinthenameoftheBellmanequation,acentralresultofdynamicprogrammingwhichrestatesanoptimizationprobleminrecursiveform.TheworddynamicwaschosenbyBellmantocapturethetime-varyingaspectoftheproblems,andbecauseitsoundedimpressive.Thewordprogrammingreferredtotheuseofthemethodtofindanoptimalprogram,inthesenseofamilitaryschedulefortrainingorlogistics.WIKIPEDIAThetermdynamicprog動態(tài)規(guī)劃的應用領域領域

生物信息學(Bioinformatics).控制論(Controltheory).信息論(Informationtheory).運籌學(Operationsresearch).計算機科學,圖形處理,語音處理

,AI,….一些常見的動態(tài)規(guī)劃算法.

Viterbi隱馬爾科夫模型.Unix中diff用于比較兩個文件的不同.序列對比中Smith-Waterman算法.網絡中最短路徑算法Bellman-Ford…..動態(tài)規(guī)劃的應用領域領域算法總體思想動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法總體思想動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解但是經分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)但是經分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常Fibonacci數(shù)列Fibonacci數(shù)列:1,1,2,3,5,8,13,…

…

…

…Fibonacci數(shù)列Fibonacci數(shù)列:publicstaticintfibonacci(intn)

{

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);

}

f(n)f(n-1)f(n-2)f(n-2)f(n-3)f(n-3)f(n-4)f(n-3)f(n-4)1123581321F:publicstaticintfibonacci(in合并排序算法mergeSort的遞歸過程。第三層[49][38][65][97][76][13][27][3849][6597][1376][27]第二層第一層[38496597][132776]樹根[13273849657697]合并排序算法mergeSort的遞歸過程。第三層[49]算法總體思想用遞歸算法進行設計，很多子問題重復計算，無形的增加了算法計算量！如何減少子問題的重復計算則是動態(tài)規(guī)劃算法的關鍵解決思想！如何在計算中減少重復？算法總體思想用遞歸算法進行設計，很多子問題重復計算，無形的增如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrememberthepastaredoomedtorepeatit.-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答

動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中,進而采用至底而上的方式進行計算這就是動態(tài)規(guī)劃法的基本思路。

分治與動態(tài)規(guī)劃動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質，并刻劃其結構特征。（尋找最優(yōu)解的子問題結構）遞歸地定義最優(yōu)值。（根據(jù)子問題結構建立問題的遞歸解式求解最優(yōu)值）以自底向上的方式計算出最優(yōu)值。（動態(tài)規(guī)劃思想）根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質，并刻劃其結構特征。（尋找最多個矩陣連乘模塊設計多個矩陣連乘模塊設計軟件行業(yè)中客戶總是在變更需求銀行對我們公司開發(fā)的矩陣乘法模塊還不滿意。他們的真實想法并不是實現(xiàn)兩個矩陣的乘法，而是是能一次夠實現(xiàn)多個矩陣按照算法運算法則的乘法，因此要求我們進一步改進我們的系統(tǒng)，實現(xiàn)多個矩陣的連乘功能，并且需要看到我們設計的程序能夠滿足他們的運行效率要求時才付二期款。頭疼軟件行業(yè)中客戶總是在變更需求頭疼問題分析：分析需要變化改進的部分輸入變化：

由兩個矩陣編程多個矩陣序列輸出變化：

無問題變化：兩個矩陣的乘法問題編程多個矩陣的乘法問題數(shù)據(jù)結構的變化算法的變化問題分析：分析需要變化改進的部分數(shù)據(jù)結構的變化算法的變化？系統(tǒng)架構有無需要變化？系統(tǒng)架構有無需要變化算法改進分析算法改進分析現(xiàn)在的問題給定n個矩陣，其中與是可乘的，。考察這n個矩陣的連乘積由于矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調用2個矩陣相乘的標準算法計算出矩陣連乘積現(xiàn)在的問題給定n個矩陣，其中完全加括號的矩陣連乘積16000,10500,36000,87500,34500設有四個矩陣，它們的維數(shù)分別是：總共有五中完全加括號的方式完全加括號的矩陣連乘積16000,10500,36000pqr次標準乘法對于

pXq

矩陣

A

和一個

qXr

矩陣

B,AB

需要

？

標準乘法計算.matrixMultiply(int[][]a,int[][]b,int[][]c,intra,intca,intrb,intcb){if(ca!=rb)ThrownewIllegalArgumentException(“矩陣不可乘”);for(inti=0;i<ra;i++)for(intj=0;i<cb;j++){intsum=a[i][0]*b[0][j];for(intk=1;k<rb;k++)Sum+=a[i][k]*b[k][j];c[i][j]=sum;}}pqr次標準乘法對于pXq矩陣A和一個qXr矩陣如果

A1,A2,andA3

是

20X100,100X10,和

10X50矩陣,A1XA2XA3乘積運算次數(shù)是多少?

((A1XA2)XA3)

(A1X(A2XA3))20X100X10=2000020X10X50=1000030000次運算20X100X50=100000100X10X50=50000150000次運算20X100X10=2000020X10X矩陣連乘問題

給定n個矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1,2,…,n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。算法復雜度分析：對于n個矩陣的連乘積，設其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：((A1...Ak)(Ak+1…An))可以得到關于P(n)的遞推式如下：Catalan數(shù)

P(n)=C(n-1)矩陣連乘問題給定n個矩陣｛A1,A2,…,An｝，矩陣連乘問題最優(yōu)解結構分析將矩陣連乘積簡記為A[i:j]，這里i≤j考察計算A[i:j]的最優(yōu)計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應完全加括號方式為總計算量=A[i:k]的計算量加上A[k+1:j]的計算量，再加上A[i:k]和A[k+1:j]相乘的計算量矩陣連乘問題最優(yōu)解結構分析將矩陣連乘積分析最優(yōu)解的子問題結構特征：計算A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質。子問題不獨立，適合動態(tài)規(guī)劃算法設計分析最優(yōu)解的子問題結構特征：計算A[i:j]的最優(yōu)次序所包含建立遞歸關系設計算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當i=j時，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當i<j時，可以遞歸地定義m[i,j]為：這里的維數(shù)為

的位置只有種可能建立遞歸關系設計算A[i:j]，1≤i≤j≤n，所需要的最少建立遞歸算法經分析遞歸算法消耗指數(shù)計算時間思考：根據(jù)上面的遞歸式與前面分治遞歸部分學到的算法設計知識建立遞歸算法建立遞歸算法經分析遞歸算法消耗指數(shù)計算時間思考：根據(jù)上面的遞實際子問題數(shù)目對于1≤i≤j≤n不同的有序對(i,j)對應于不同的子問題。因此，不同子問題的個數(shù)最多只有由此可見，在遞歸計算時，許多子問題被重復計算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法實際子問題數(shù)目對于1≤i≤j≤n不同的有序對(i,j)對應于遞歸遞歸動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法用動態(tài)規(guī)劃法求最優(yōu)解publicstaticvoidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;

for(inti=1;i<=n;i++)m[i][i]=0;

for(intr=2;r<=n;r++)

for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;

for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}A1A2A3A4A5A6303535

1515

55

1010

2020

25算法復雜度分析：算法matrixChain的主要計算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內的計算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。m[i,i]m[i,i+r]用動態(tài)規(guī)劃法求最優(yōu)解publicstaticvoidm動態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結構矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質。在分析問題的最優(yōu)子結構性質時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構造出比原問題最優(yōu)解更好的解，從而導致矛盾。利用問題的最優(yōu)子結構性質，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解。最優(yōu)子結構是問題能用動態(tài)規(guī)劃算法求解的前提。注意：同一個問題可以有多種方式刻劃它的最優(yōu)子結構，有些表示方法的求解速度更快（空間占用小，問題的維度低）動態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結構矩陣連乘計算次序問題的最二、重疊子問題遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結果。

通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。二、重疊子問題遞歸算法求解問題時，每次產生的子問題并不總是新二、重疊子問題考慮用遞歸式直接計算矩陣連乘中的A[i:j]

recurMatrixChain(inti,intj){if(i==j)return0;Intu=recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j]S[i][j]=I;for(intk=i+1;k<j;k++)intt=recurMatricChain(i,k)+recurMatricChain(k+1,j)+p[i-1]*p[k]*p[j]If(t<u){u=t;S[i][j]=k;}Returnu;二、重疊子問題考慮用遞歸式直接計算矩陣連乘中的A[i:j]二、重疊子問題計算時間T(n)有指數(shù)下界：可以推得T(n)的遞歸關系式如下：

可用數(shù)學歸納法證明因此直接遞歸算法的計算時間隨n指數(shù)增長，相比之下動態(tài)規(guī)劃算法計算復雜度要低，其有效性就在于它充分利用了問題的重疊性質

可不可以在遞歸算法中通過添加表記錄已計算結果，減少計算量？二、重疊子問題計算時間T(n)有指數(shù)下界：可用數(shù)學歸納法證明三、備忘錄方法備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。備忘錄：自頂向下！備忘錄方法為每個子問題建立一個記錄項，初始化時，該記錄項存入一個特殊值，表示該子問題尚未求解。在求解過程中對每個待求子問題，首先查看其相應的記錄項。若記錄項中存儲的是初始化時存入的特殊值，則表示該子問題是第一次遇到，此時計算出該子問題的解，并保存在其相應的記錄項中，備以后查看，若記錄項中存儲的已不是初始化時存入的特殊值，表示該問題已經被計算過，此時只要從記錄項中取出該問題的解答即可。動態(tài)規(guī)劃：自底向上！三、備忘錄方法備忘錄方法的控制結構與直接遞歸方法的控制結構相遞歸算法recurMatrixChain(inti,intj){if(i==j)return0;Intu=recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j]S[i][j]=I;for(intk=i+1;k<j;k++)intt=recurMatricChain(i,k)+recurMatricChain(k+1,j)+p[i-1]*p[k]*p[j]If(t<u){u=t;S[i][j]=k;}Returnu;以遞歸方式進行計算遞歸算法recurMatrixChain(inti,in三、備忘錄方法用備忘錄方法解矩陣連乘問題m0privatestaticintlookupChain(inti,intj){

if(m[i][j]>0)returnm[i][j];

if(i==j)return0;intu=lookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;

f