算法設計第三章 動態(tài)規(guī)劃

教學目標動態(tài)規(guī)劃的原理理解多階段決策過程及特點理解動態(tài)規(guī)劃的術語熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程最優(yōu)性定理和基本方程充分理解最優(yōu)性定理熟記、理解兩種動態(tài)規(guī)劃的基本方程掌握動態(tài)規(guī)劃求解的基本步驟動態(tài)規(guī)劃特點、條件和步驟熟記動態(tài)規(guī)劃的適用條件熟記逆序、正序遞推法的可歸納為以下四個步驟第1頁，課件共83頁，創(chuàng)作于2023年2月1動態(tài)規(guī)劃的原理(多階段決策問題)

多階段決策過程多階段決策過程是活動過程可按時間或空間順序分解成若干相互獨立、相互聯(lián)系的階段，在每個階段的狀態(tài)下做出決策，整個過程的決策構成一個決策序列，則稱多階段決策過程為序貫決策過程。稱問題為多階段決策問題。狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5決策2決策3決策4決策1多階段決策問題的特點過程可分為若干個相互聯(lián)系的階段；每一階段都對應著一組可供選擇的決策；每一決策的選定即依賴于當前面臨的狀態(tài)，又影響以后總體的效果。第2頁，課件共83頁，創(chuàng)作于2023年2月2動態(tài)規(guī)劃的原理(單源最短路徑)第1階段第2階段第3階段第4階段狀態(tài)1狀態(tài)2狀態(tài)4狀態(tài)5狀態(tài)3決策1決策2決策4決策3動態(tài)規(guī)劃把多階段過程的問題轉(zhuǎn)化為一系列單階段的問題，逐個階段求解的最優(yōu)化數(shù)學方法。第3頁，課件共83頁，創(chuàng)作于2023年2月3動態(tài)規(guī)劃的原理動態(tài)規(guī)劃的術語階段：將過程劃分為k個階段，1k

n。狀態(tài)：第k個階段的狀態(tài)變量為

。為初態(tài)，為終態(tài)。狀態(tài)集合：

允許的取值范圍，記為

。決策：表示第k階段狀態(tài)的決策變量，簡記為。允許決策集合：允許的取值范圍。策略：一個按順序排列的決策序列，記。狀態(tài)轉(zhuǎn)移方程：從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段某一狀態(tài)值的轉(zhuǎn)移規(guī)律，記為。子策略：稱決策序列為k子過程策略。簡稱子策略，記為第4頁，課件共83頁，創(chuàng)作于2023年2月4動態(tài)規(guī)劃的原理

當k=1時，成為全過程的一個策略，簡稱策略，簡記為。階段指標函數(shù)：指第k階段從狀態(tài)出發(fā)，采取決策時的效益，用表示。過程指標函數(shù)：從第k階段的狀態(tài)出發(fā)，采取子策略 獲得最佳效益記為。最優(yōu)性函數(shù)：若采用最優(yōu)子策略，從第k階段的出發(fā)獲得最佳效益 第5頁，課件共83頁，創(chuàng)作于2023年2月5動態(tài)規(guī)劃的原理其中opt可根據(jù)具體情況取max或min。是可分函數(shù)，具有可加性或可乘性最優(yōu)性基本方程第6頁，課件共83頁，創(chuàng)作于2023年2月6最優(yōu)性定理和基本方程

兩種方式的動態(tài)規(guī)劃初始狀態(tài)出發(fā)到終止狀態(tài)的正序?qū)?yōu)；從終止狀態(tài)出發(fā)到初始狀態(tài)逆序?qū)?yōu)。

動態(tài)規(guī)劃求解的基本步驟

1.劃分階段2.定義決策變量，確定決策集合是最優(yōu)策略的充要條件是：對任一k(1kn),當初狀態(tài)為s1時,有即在最優(yōu)策略，必然包含最優(yōu)子策略。換句話說，問題的最優(yōu)解必包含子問題的最優(yōu)解。最優(yōu)性定理第7頁，課件共83頁，創(chuàng)作于2023年2月7最優(yōu)性定理和基本方程式中opt可根據(jù)題意取max或min。正序基本方程：此為逐段遞推計算的依據(jù)，一般為：式中opt可根據(jù)題意取max或min。逆序基本方程：此為逐段遞推計算的依據(jù)，一般為：3.確定階段指標函數(shù)4.建立狀態(tài)轉(zhuǎn)移方程5.確定過程指標函數(shù)6.建立遞歸方程第8頁，課件共83頁，創(chuàng)作于2023年2月8動態(tài)規(guī)劃實例計算逆序遞推計算方法(單源最短路徑)

用表示在第k階段由初始狀態(tài)到下一階段的狀態(tài)的距離。用表示從第k階段的狀態(tài)到終點E的最短距離。1．階段k=4第4階段有兩個初始狀態(tài)和。若全過程最短路徑經(jīng)過狀態(tài)，則有=4；若全過程最短路徑經(jīng)過狀態(tài)，則有=3。2．階段k=3假設全過程最短路徑在第3階段經(jīng)過狀態(tài)，若由，則有。

3．，及其它階段的計算類似。，最短路徑為。第9頁，課件共83頁，創(chuàng)作于2023年2月9動態(tài)規(guī)劃特點、條件和步驟動態(tài)規(guī)劃的適用條件

適用動態(tài)規(guī)劃的問題必須滿足以下三個條件

最優(yōu)化原理無后效性

子問題的重疊性動態(tài)規(guī)劃特點優(yōu)點離散性問題：使解析數(shù)學無用武之地；建模：可用計算機計算；缺點無統(tǒng)一處理方法：需要數(shù)學技巧與解題經(jīng)驗；組合爆炸：只能解決中小規(guī)模的問題第10頁，課件共83頁，創(chuàng)作于2023年2月10動態(tài)規(guī)劃特點、條件和步驟最優(yōu)性定理（最優(yōu)子結構性質(zhì)）

一個最優(yōu)性策略具有這樣的性質(zhì)：不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)性原理又稱其具有最優(yōu)子結構性質(zhì)。

無后向性

將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，只能通過當前給定的狀態(tài)，直接影響未來的決策，而與以前各階段的狀態(tài)無關，這就是無后向性，又稱為無后效性。換句話說，每個狀態(tài)都是過去歷史的一個完整總結。第11頁，課件共83頁，創(chuàng)作于2023年2月11動態(tài)規(guī)劃特點、條件和步驟子問題的重疊性

動態(tài)規(guī)劃算法的關鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質(zhì)上是一種以空間換時間的技術，它在實現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復雜度可能要大于其它的算法。選擇動態(tài)規(guī)劃算法是因為動態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。

舉例1：求二項式系數(shù)的計算(用分治遞歸)時間復雜性：T(n)=(2n)

第12頁，課件共83頁，創(chuàng)作于2023年2月12動態(tài)規(guī)劃特點、條件和步驟動態(tài)規(guī)劃的逆序遞推法的可歸納為以下四個步驟最優(yōu)子結構：找出最優(yōu)解的性質(zhì)，并刻畫其結構特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計算最優(yōu)值：自底向上或自頂向下計算出最優(yōu)值。構造最優(yōu)解：由計算最優(yōu)值的信息，構造最優(yōu)解。時間復雜性：T(n)=O(n-1)=1.61803，n1舉例2：Fibonacci序列問題動態(tài)規(guī)劃的正序遞推法的步驟與逆序類似第13頁，課件共83頁，創(chuàng)作于2023年2月13本節(jié)作業(yè)1.用動態(tài)規(guī)劃方法，編寫一個循環(huán)迭代算法計算如下的組合數(shù)。要求如下時間復雜性為(mn)空間復雜性為(m)思考：若用分治法計算同樣的組合數(shù)，時間復雜性如何推導計算？第14頁，課件共83頁，創(chuàng)作于2023年2月14第二節(jié)主要內(nèi)容動態(tài)規(guī)劃條件子問題的重疊性逆序、正序遞推法的可歸納為以下四個步驟最優(yōu)子結構：找出最優(yōu)解的性質(zhì)，并刻畫其結構特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計算最優(yōu)值：自底向上或自頂向下計算出最優(yōu)值。構造最優(yōu)解：由計算最優(yōu)值的信息，構造最優(yōu)解。運用動態(tài)規(guī)劃求解經(jīng)典實例單源最短路徑所有點對的最短路徑第15頁，課件共83頁，創(chuàng)作于2023年2月15教學目標動態(tài)規(guī)劃適用條件充分理解子問題的重疊性理解動態(tài)規(guī)劃的術語熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結構熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計算最優(yōu)值掌握用最優(yōu)值相關信息，求最優(yōu)解理解實例的解題步驟第16頁，課件共83頁，創(chuàng)作于2023年2月16動態(tài)規(guī)劃(單源最短路徑)問題提出

G=<V，E>是一個多級圖，如下圖所示。第1階段第2階段第3階段第4階段狀態(tài)1狀態(tài)2狀態(tài)4狀態(tài)5狀態(tài)3決策1決策2決策4決策3第17頁，課件共83頁，創(chuàng)作于2023年2月17動態(tài)規(guī)劃(單源最短路徑)最優(yōu)子結構

假設第

i+1級的狀態(tài)集V

i+1中的任意一個頂點u到終點H的最短路徑已經(jīng)確定，第i級的狀態(tài)集V

i中的任意一個頂點v到終點H的最短路徑，是頂點v經(jīng)過集V

i+1中某個頂點u到終點H的所有路徑中最短的那條路徑。這說明問題具有最優(yōu)子結構性質(zhì)。最優(yōu)值定義

設過程共有k個級，即k1個階段。又設Piv表示從V

i中的頂點v到H的一條最短路徑，Cost(i,v)表示這條路徑的代價，按照由后向前推進，可得：第18頁，課件共83頁，創(chuàng)作于2023年2月18動態(tài)規(guī)劃(單源最短路徑)計算最優(yōu)值算法：Min_PathCost

輸入：鄰接矩陣A[1…n,1…n]

輸出：從源點1到匯點n的最短路徑長度在Cost[1]dist←Min_PathCost(A，n)過程：Min_PathCost(C，n)

1.fori←1ton12.Cost[i]←3.endfor4.Cost[n]←05.forj←n1downto16.設u使得(j,u)邊集且C[j][u]+Cost[u]為最小7.Cost[j]←C[j][u]+Cost[u]8.D[j]←u9.endfor10.returnCost[1]第19頁，課件共83頁，創(chuàng)作于2023年2月19動態(tài)規(guī)劃(單源最短路徑)構造最優(yōu)解

計算最優(yōu)值時用數(shù)組D[1…k]記錄頂點u，因為(j,u)邊集且C[j][u]+Cost[u]為最小，所以u是j的后繼頂點。從而p[1]←1

p[k]←nforj←2tok1p[j]←D[p[j1]]endfor算法復雜性分析

時間復雜性：T(n)=(n2)空間復雜性：S(n)==(n)若A為鄰接表：則T(n)=O(n+|E|)，其中n為頂點數(shù)，|E|為邊集大小。第20頁，課件共83頁，創(chuàng)作于2023年2月20動態(tài)規(guī)劃(所有點對的最短路徑)問題提出設G=<V，E>是一個簡單有向圖，其中每條邊<i，j>長度w[i，j]0。若頂點i到頂點j沒有邊，則w[i，j]=，若i=j，則w[i，j]=0。G用鄰接矩陣W表示。問題是找出每個頂點到其它所有頂點的最短路徑。顯然，鄰接矩陣W本身表示V中每個頂點i到其它所有頂點j，而不經(jīng)過任何中間頂點的最短路徑，記為pij0。

定義pijk是頂點i到其它所有頂點j，且經(jīng)過中間頂點序號不大于k的最短路徑

。

pijn表示頂點i到其它所有頂點j，任意一個頂點都可作為最短路徑上的中間頂點。

最優(yōu)子結構由pijk定義知：當頂點i到其它所有頂點j，經(jīng)過中間頂點序號不大于k1的最短路徑恰好為pijk1，即有pijk=pijk1。第21頁，課件共83頁，創(chuàng)作于2023年2月21動態(tài)規(guī)劃(所有點對的最短路徑)

另一方面，由pijk定義又知：pikk1是頂點i到頂點k，且經(jīng)過中間頂點序號不大于k1的最短路徑，而pkjk1是從頂點k到頂點j，且經(jīng)過中間頂點序號不大于k1的最短路徑。這正說明pijk的最短路徑包含pikk1和pkjk1的最短路徑。綜上所述，可知問題具有最優(yōu)子結構的性質(zhì)，即得：pijk=min{pijk1，pikk1+pkjk1}。

設Dk(i，j)是任一頂點i到其它所有頂點j，且經(jīng)過中間頂點序號不大于k的最短路徑長度。特別D0(i，j)=W。

Dk1(i，j)是任一頂點i到其它所有頂點j，且經(jīng)過中間頂點序號不大于k1的最短路徑長度。

Dk1(i，k)任一頂點i到頂點k，且經(jīng)過中間頂點序號不大于k1的最短路徑長度。

第22頁，課件共83頁，創(chuàng)作于2023年2月22動態(tài)規(guī)劃(所有點對的最短路徑)

Dk1(k，j)任一頂點k到頂點j，且經(jīng)過中間頂點序號不大于k1的最短路徑長度。最優(yōu)值定義

綜上所述可得：計算最優(yōu)值

算法：Floyd

輸入：鄰接矩陣W

輸出：

D[1…n,1…n]及next[1…n,1…n]分別為最優(yōu)值及最 短路徑矩陣

Floyd(W，next)過程：Floyd(D，next)第23頁，課件共83頁，創(chuàng)作于2023年2月23動態(tài)規(guī)劃(所有點對的最短路徑)

1.fori←1ton2.forj←1ton3.next[i][j]←j4.endfor5.endfor6.fork←1ton7.fori←1ton8.forj←1ton9.ifD[i][k]+D[k][j]<D[i][j]then10.D[i][j]←D[i][k]+D[k][j]11.next[i][j]←next[i][k]

12.endif13.endfor14.endfor15.endfor第24頁，課件共83頁，創(chuàng)作于2023年2月24動態(tài)規(guī)劃(所有點對的最短路徑)構造最優(yōu)解

在計算最優(yōu)值時，利用數(shù)組next[1…n,1…n]記載當前經(jīng)過的中間頂點信息k，即數(shù)組next[1…n,1…n]記載任一頂點i到其它所有頂點j最短路徑。

算法：Print_Path

輸入：最短路徑矩陣next[1…n,1…n]及i，j

輸出：i到j的最短路徑next[1…n,1…n]

Print_Path(next，i，j)過程：Print_Path(next，i，j)

1.ifnext[i][j]=jthen2.print(ij)3.return第25頁，課件共83頁，創(chuàng)作于2023年2月25動態(tài)規(guī)劃(所有點對的最短路徑)4.endif5.print(i)6.print_path(next，next[i][j]，j)

算法復雜性分析Floyd算法時間復雜性為T(n)=(n3)，而Print_Path算法時間復雜性為T(n)=(n)。算法時間復雜性：

T(n)=(n3)算法空間復雜性：

S(n)=(n2)Warshall傳遞閉包算法(略)第26頁，課件共83頁，創(chuàng)作于2023年2月26本節(jié)作業(yè)1.設G=(V，E)是n個頂點的簡單有向圖，A是G的關系R的關系矩陣。要求用動態(tài)規(guī)劃方法，編寫一個循環(huán)迭代算法，求R的傳遞閉包(即稱Warshall算法)。第27頁，課件共83頁，創(chuàng)作于2023年2月27第三節(jié)主要內(nèi)容動態(tài)規(guī)劃條件子問題的重疊性逆序、正序遞推法的可歸納為以下四個步驟最優(yōu)子結構：找出最優(yōu)解的性質(zhì)，并刻畫其結構特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計算最優(yōu)值：自底向上或自頂向下計算出最優(yōu)值。構造最優(yōu)解：由計算最優(yōu)值的信息，構造最優(yōu)解。運用動態(tài)規(guī)劃求解經(jīng)典實例最長公共子序列問題第28頁，課件共83頁，創(chuàng)作于2023年2月28教學目標動態(tài)規(guī)劃適用條件充分理解子問題的重疊性理解動態(tài)規(guī)劃的術語熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結構熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計算最優(yōu)值掌握用最優(yōu)值相關信息，求最優(yōu)解理解實例的解題步驟第29頁，課件共83頁，創(chuàng)作于2023年2月29動態(tài)規(guī)劃(最長公共子序列問題)

相關概念若給定序列A={a1,a2,…,an}，則另一序列C={c1,c2,…,ck}為A的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：cj=aij。例如，序列C={b，c，d，b}是序列A={a，b，c，b，d，a，b}的子序列，相應的遞增下標序列為{2，3，5，7}。公共子序列給定2個序列A和B，當另一序列C既是A的子序列又是B的子序列時，稱C是序列A和B的公共子序列。問題提出—最長公共子序列。給定2個序列A={a1,a2,…,an}和B={b1,b2,…,bm}，找出A和B的最長公共子序列。顯然，用蠻力策略，A有2n個子序列。若用(m)時間內(nèi)可確定它也是B的一個子序列，其時間復雜性(m2n)。第30頁，課件共83頁，創(chuàng)作于2023年2月30動態(tài)規(guī)劃(最長公共子序列問題)

最優(yōu)子結構性質(zhì)設序列A={a1,a2,…,an}和B={b1,b2,…,bm}的最長公共子序列為C={c1,c2,…,ck}，則(1)若an=bm，則ck=an=bm，且Ck-1是An-1和Bm-1的最長 公共子序列。(2)若an≠bm且ck≠an，則C是An-1和B的最長公共子 序列。(3)若an≠bm且ck≠bm，則C是A和Bm-1的最長公共子 序列。由此可見，(1)說明A、B兩個序列的最長公共子序列包含了它們前綴An-1、Bm-1的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結構性質(zhì)。

第31頁，課件共83頁，創(chuàng)作于2023年2月31動態(tài)規(guī)劃(最長公共子序列問題)遞歸定義最優(yōu)值由最優(yōu)子結構性質(zhì)知：計算A和B的最長公共子序列時，都要計算A和Bm-1及An-1和B的最長公共子序列，而這兩個子問題都包含一個公共子問題（重迭子問題），即計算Bm-1和An-1最長公共子序列。從上述可知：最長公共子序列問題的最優(yōu)子結構性質(zhì)決定了建立子問題最優(yōu)值的遞歸關系。于是，令L[i,j]記錄a1,a2,…,ai和b1,b2,…,bj的最長公共子序列的長度。顯然，當i=0或j=0時，則L[i,j]=0表示Ai和Bj的最長公共子序列為空序列。其它情況，則由最優(yōu)子結構性質(zhì)建立遞歸關系如下：第32頁，課件共83頁，創(chuàng)作于2023年2月32動態(tài)規(guī)劃(最長公共子序列問題)

舉例：X=abcbdab，Y=bdcaba4432210b74332210a63322210d53322110b42222110c32211110b21110000a1000000Xi0abacdb6543210bacb遞歸推導得解：bcbaYjijnulnul0第33頁，課件共83頁，創(chuàng)作于2023年2月33動態(tài)規(guī)劃(最長公共子序列問題)

計算最優(yōu)值算法由遞歸關系直接計算，公共子問題求解會被重復計算?；诳臻g考慮，總共有(mn)個不同的子問題，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。

算法：LCSLENGTH

輸入：字母表上的兩個字符串A和B及長度n,m

輸出：最長公共子序列的長度及最優(yōu)解數(shù)組s[1…n][1…m]L←LCSLENGTH(n,m)過程：LCSLENGTH(n,m)

1 fori←0ton 2 L[i,0]←0 3 endfor4forj←0tom 5 L[0,j]←0 6 endfor第34頁，課件共83頁，創(chuàng)作于2023年2月34動態(tài)規(guī)劃(最長公共子序列問題)

7 fori←1ton 8 forj←1tom 9 ifA[i]=B[j]then 10 L[i,j]←L[i-1,j-1]+1 12 s[i,j]←‘↖’13 elseifL[i-1,j]>=L[i,j-1]then14 L[i,j]←L[i-1,j] 15 s[i,j]←‘’ 16 else 17 L[i,j]←L[i,j-1]18 s[i,j]←‘’ 19 endif20 endif21endfor22endfor23returnL[n,m]和s復雜性分析 T(n)=(nm)改進

T(n)=min{m,n}第35頁，課件共83頁，創(chuàng)作于2023年2月35構造最優(yōu)解

算法：LCS

輸入：s[1n,1m]及n,m

輸出：輸出最長公共子序列xLCS(n,m,x,s)過程：LCS(i,j,x,s)1ifi=0orj=0thenreturn 2ifs[i,j]=

‘↖’then3LCS(i-1,j-1,x,s)4 輸出x[i]5 elseifs[i,j]=‘’then6 LCS(i-1,j,x,s)7 else8 LCS(i,j-1,x,s)9endif10endif動態(tài)規(guī)劃(最長公共子序列問題)復雜性分析

T(n)=O(n+m)第36頁，課件共83頁，創(chuàng)作于2023年2月36本節(jié)思考題1.用動態(tài)規(guī)劃方法，編寫一個循環(huán)迭代算法，求解給定序列的最長遞增子序列。第37頁，課件共83頁，創(chuàng)作于2023年2月37第四節(jié)主要內(nèi)容動態(tài)規(guī)劃條件子問題的重疊性

逆序、正序遞推法的可歸納為以下四個步驟最優(yōu)子結構：找出最優(yōu)解的性質(zhì)，并刻畫其結構特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計算最優(yōu)值：自底向上或自頂向下計算出最優(yōu)值。構造最優(yōu)解：由計算最優(yōu)值的信息，構造最優(yōu)解。運用動態(tài)規(guī)劃求解經(jīng)典實例矩陣連乘積問題第38頁，課件共83頁，創(chuàng)作于2023年2月38教學目標動態(tài)規(guī)劃適用條件充分理解子問題的重疊性理解動態(tài)規(guī)劃的術語熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結構熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計算最優(yōu)值掌握用最優(yōu)值相關信息，求最優(yōu)解理解實例的解題步驟第39頁，課件共83頁，創(chuàng)作于2023年2月39動態(tài)規(guī)劃(矩陣連乘積問題)

問題提出設有矩陣M1，M2和M3及其維數(shù)分別是210，102和210，計算它們的乘積，即M1M2M3。矩陣的乘法順序若按M1(M2M3)順序計算，共有10210+21010=400數(shù)乘次數(shù)。而若按(M1M2)M3順序計算，則數(shù)乘次數(shù)只有2102+2210=80。由上述可知：高效的矩陣乘積算法與矩陣的乘法結合律有關。這種結合順序數(shù)隨矩陣個數(shù)增長而增加。顯然，算法就是尋找一個數(shù)乘次數(shù)最少的乘法運算順序。蠻力的方法考察n個可乘的矩陣的M1M2…Mn，共有n-1個乘法運算順序。如(M1M2M3M4)有3個乘法運算順序，但它們的結合順序數(shù)則有5種：第40頁，課件共83頁，創(chuàng)作于2023年2月40動態(tài)規(guī)劃(矩陣連乘積問題)顯然，結合順序數(shù)是n個矩陣加括弧的方法數(shù)。設f(n)為求n個矩陣乘積的所有放置括弧的方法數(shù)，假定矩陣乘法為： ((M1M2

…Mk

)

(Mk+1Mk+2

…Mn

))則有：復雜性分析

見數(shù)據(jù)結構P152的解法第41頁，課件共83頁，創(chuàng)作于2023年2月41動態(tài)規(guī)劃(矩陣連乘積問題)每個括弧化表達式，有n-1次的矩陣乘法次數(shù)，即矩陣乘法時間是(n)。因此，數(shù)乘次數(shù)的時間復雜性為：最優(yōu)子結構性質(zhì)

設對于任意矩陣Mi，其行數(shù)為ri，列數(shù)為ri+1且1in，則(MiMi+1)可乘是Mi列數(shù)等于Mi+1行數(shù)。于是，M1，M2，…，Mn的行數(shù)分別為r1，r2，…，rn及rn+1，其中rn+1為Mn的列數(shù)。令Mi,j為矩陣乘積，Mi,j=MiMi+1…Mj，1ijn。由上述可知存在k，i+1kj，Mi,j=Mi,k-1

Mk,j。Mi,j的數(shù)乘次數(shù)記為C[i，j]，則計算C[i，j]： C[i，j]=C[i，k1]+C[k，j]+rirkrj+1復雜性分析

第42頁，課件共83頁，創(chuàng)作于2023年2月42動態(tài)規(guī)劃(矩陣連乘積問題)這導致尋找一個k，i+1kj，使得C[i，j]最少，即特別地計算M1,n的一個最優(yōu)順序包含計算矩陣子鏈M1,k-1

和Mk,n，1<k<=n的最優(yōu)順序。若不然，存在一個數(shù)乘次數(shù)更少的子鏈M1,k-1，替換原來的M1,k-1的順序，于是得到M1,n另一個最優(yōu)的順序，這是一個矛盾。同理可知，計算M1,n的一個最優(yōu)順序包含計算矩陣子鏈Mk,n的最優(yōu)順序。遞歸定義最優(yōu)值第43頁，課件共83頁，創(chuàng)作于2023年2月43動態(tài)規(guī)劃(矩陣連乘積問題)顯然C[i，j]是Mi,j的一個最優(yōu)順序，i+1kj，即數(shù)乘次數(shù)最少，而原問題M1,n的一個最優(yōu)順序便是C[1，n]。當i=j時，即為單一矩陣，數(shù)乘次數(shù)顯然為0。當i<j時，即存在k，i+1kj，使得C[i，j]是Mi,j的一個最優(yōu)順序。從而C[i，j]可遞歸定義：計算最優(yōu)值算法從(1≤i≤j≤n)知：不同的有序?qū)?i,j)對應于不同的子問題。因此，不同子問題的個數(shù)最多只有第44頁，課件共83頁，創(chuàng)作于2023年2月44動態(tài)規(guī)劃(矩陣連乘積問題)

舉例計算5個矩陣乘積最少數(shù)乘次數(shù)。設：M1：510M2：104M3：46M4：610M5：102C[6,6]C[1,6]C[1,5]C[1,4]C[1,3]C[1,2]C[1,1]C[2,6]C[2,5]C[2,4]C[2,3]C[2,2]C[3,6]C[3,5]C[3,4]C[3,3]C[4,6]C[4,5]C[4,4]C[5,6]C[5,5]d=0d=2d=1d=3d=4d=5(M1(

M2(

M3(

M4M5))))例如：n=6的計算形式348262043203200202483640324030168424040120500第45頁，課件共83頁，創(chuàng)作于2023年2月45動態(tài)規(guī)劃(矩陣連乘積問題)

由此可見，用遞歸計算，許多子問題被重復計算多次。動態(tài)規(guī)劃算法恰好可克服這缺陷。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其最優(yōu)值遞歸定義以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法，算法如下。

算法：MATCHAIN

輸入：n個矩陣的鏈的維數(shù)r[1n+1]，其中r[1n]是n 個矩陣的行數(shù)，r[n+1]是Mn列數(shù)

輸出：C[1,n]最優(yōu)值和最優(yōu)計算次序的s[1n,1n]1.MATCHAIN(n)

過程MATCHAIN(n)第46頁，課件共83頁，創(chuàng)作于2023年2月46動態(tài)規(guī)劃(矩陣連乘積問題)

1fori←1ton2C[i,i]←03endfor4ford←1ton15 fori←1tond6j←i+d7 C[i,j]←C[i,i]+C[i+1,j]+r[i]r[i+1]r[j+1]8s[i,j]←i+19fork←i+2toj10t←C[i,k-1]+C[k,j]+r[i]*r[k]*r[j+1]11ift<C[i,j]then12 C[i,j]←t13s[i,j]←k14endif15endfor16endfor17endfor18returnC[1,n]和s算法復雜度分析：MATCHAIN算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。第47頁，課件共83頁，創(chuàng)作于2023年2月47動態(tài)規(guī)劃(矩陣連乘積問題)構造最優(yōu)解(最少數(shù)乘的矩陣鏈)MATCHAIN算法用s[i,j]記錄矩陣乘積的最優(yōu)計算次序全部信息，即計算Mi,j矩陣時，保存斷開矩陣Mi,k-1和Mk,j斷開點k。因為s[1,n]記錄M1,n的最優(yōu)括弧表達式，即有：M1,n=(M1,s[1,n]-1)(Ms[1,n],n)=((M1,s[1,s[1,n]-1]-1) (Ms[1,s[1,n]-1],s[1,n]-1))((Ms[1,n],s[s[1,n],n]-1)(Ms[s[1,n],n],n))以此類推構造最優(yōu)解。顯然，若要輸出矩陣鏈的最優(yōu)計算順序，還要有一個輸出最優(yōu)解的算法，請參見教材P66一節(jié)。下列MChainMuliply算法輸出Mi,j的最優(yōu)計算次序的運算結果。

第48頁，課件共83頁，創(chuàng)作于2023年2月48動態(tài)規(guī)劃(矩陣連乘積問題)算法：MChainMuliply輸入：s[1n,1n]及1和n

輸出：輸出最優(yōu)計算次序的Mi,j

MChainMuliply(1,n,s)

過程MChainMuliply(i,j,s)1ifi=jreturnMi2X←MChainMuliply(i,s[i,j]-1,s)3Y←MChainMuliply(s[i,j],j,s)4returnMultiply(XY)首先，假設算法Multiply(X，Y)表示矩陣X與Y的兩個矩陣一般乘積，那么，MChainMuliply算法描述如下：第49頁，課件共83頁，創(chuàng)作于2023年2月49動態(tài)規(guī)劃(矩陣連乘積問題)

動態(tài)規(guī)劃的基本要素

1.最優(yōu)子結構性質(zhì)；2.重疊子問題；1.最優(yōu)子結構性質(zhì)

自底向上求解子問題的最優(yōu)解，逐步構造問題最優(yōu)解。2.重疊子問題用自頂向下的直接遞歸方式求解子問題，子問題有重復。計算M1,4的遞歸樹第50頁，課件共83頁，創(chuàng)作于2023年2月50算法：RecMatChain輸入：

n個矩陣的鏈的維數(shù)r[1n+1]，其中r[1n]是n個矩陣的行數(shù) ，r[n+1]是Mn列數(shù)

輸出：記錄矩陣乘積的最優(yōu)計算次序的s[1n,1n]RecMatChain(1,n)

過程RecMatChain(i,j)1ifi=jreturn02u←RecMatChain(i,i)+RecMatChain(i+1,j)+r[i]*r[i+1]*r[j+1]3s[i,j]←i+14fork←i+2toj5t←RecMatChain(i,k)+RecMatChain(k+1,j)+r[i]*r[k]*r[j+1]6ifu<tthen7u←t8s[i,j]←k9endif10endfor11returns動態(tài)規(guī)劃(矩陣連乘積問題)最壞情況下復雜性分析

第51頁，課件共83頁，創(chuàng)作于2023年2月51動態(tài)規(guī)劃(矩陣連乘積問題)3.備忘錄方法

備忘錄方法與自頂向下的直接遞歸方式的控制結構相同，區(qū)別在于備忘錄方法備忘了每個子問題的解，以備需要時查看。它是動態(tài)規(guī)劃的一種變形。

算法：MemMatChain輸入：整數(shù)n

輸出：最優(yōu)值數(shù)組C[1n,1n]和最優(yōu)計算次序的s[1n,1n]MemMatChain(n)

過程MemMatChain(n)1 fori←1ton2forj←iton3C[i,j]←04endfor5endfor6returnLookupChain(1,n)第52頁，課件共83頁，創(chuàng)作于2023年2月52動態(tài)規(guī)劃(矩陣連乘積問題) 1if(C[i,j]>0)thenreturnC[i,j] 2ifi=jthenreturn0 3u←LookupChain(i,i)+LookupChain(i+1,j)+r[i]*r[i+1]*r[j+1]; 4s[i,j]←i+1;5fork←i+2toj6t←LookupChain(i,k)+LookupChain(k+1,j)+r[i]*r[k]*r[j+1];7ift<uthen8u←t9s[i,j]←k10endif11C[i,j]←u12endfor13returns復雜性分析

算法：LookupChain輸入：維數(shù)數(shù)組r[1n+1]及C[1n,1n]

輸出：最優(yōu)計算次序的s[1n,1n]1.LookupChain(1,n)

過程LookupChain(i,j)第53頁，課件共83頁，創(chuàng)作于2023年2月53本節(jié)作業(yè)1.對于以下5個矩陣應用本節(jié)算法MATCHAIN。M1：23，M2：36，M3：64，M4：42，M5：42找出這5個矩陣相乘需要的最少數(shù)乘乘法次數(shù)。請給出一個括號表達式，使在這種次序下達到乘法的次數(shù)最少。2.用備忘錄方法，編寫一個遞歸算法，計算斐波那契序列。第54頁，課件共83頁，創(chuàng)作于2023年2月54第五節(jié)主要內(nèi)容動態(tài)規(guī)劃條件子問題的重疊性

逆序、正序遞推法的可歸納為以下四個步驟最優(yōu)子結構：找出最優(yōu)解的性質(zhì)，并刻畫其結構特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計算最優(yōu)值：自底向上或自頂向下計算出最優(yōu)值。構造最優(yōu)解：由計算最優(yōu)值的信息，構造最優(yōu)解。運用動態(tài)規(guī)劃求解經(jīng)典實例0/1背包問題第55頁，課件共83頁，創(chuàng)作于2023年2月55教學目標動態(tài)規(guī)劃適用條件充分理解子問題的重疊性理解動態(tài)規(guī)劃的術語熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結構熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計算最優(yōu)值掌握用最優(yōu)值相關信息，求最優(yōu)解理解實例的解題步驟第56頁，課件共83頁，創(chuàng)作于2023年2月56動態(tài)規(guī)劃(0/1背包問題)

問題提出

設有n個物品的集合W={w1,w2,…，wn}，wj和vj分別為的物品體積和價值，C為背包容量，且C,wj,vj為正整數(shù)。要求從W中選擇物品裝入背包，使得裝入背包的物品總價值最大。數(shù)學模型

0-1背包問題是一個特殊的整數(shù)規(guī)劃問題

最優(yōu)子結構性質(zhì)1設(x1,x2,…,xn)為0/1背包問題的一個最優(yōu)解，則(x2,…,xn)是相應子問題的一個最優(yōu)解：第57頁，課件共83頁，創(chuàng)作于2023年2月57動態(tài)規(guī)劃(0/1背包問題)若不然，設(z2,…,zn)是上述子問題的一個最優(yōu)解，而(x2,…,xn)不是它的最優(yōu)解。由此可知：且因此第58頁，課件共83頁，創(chuàng)作于2023年2月58動態(tài)規(guī)劃(0/1背包問題)這說明(x1,z2,…,zn)是所給0/1背包問題的一個更優(yōu)解，而(x1,x2,…,xn)不是問題0/1背包問題的一個最優(yōu)解，此為矛盾。這說明(x1,x2,…,xn)不是問題0/1背包問題的一個最優(yōu)解。最優(yōu)子結構2

設V[i,j]表示從W中選擇最前面i個物品組成的物品子集{w1,w2,…,wi}裝入容量為j的背包總價值。于是得到：第59頁，課件共83頁，創(chuàng)作于2023年2月59動態(tài)規(guī)劃(0/1背包問題)遞歸定義最優(yōu)值

根據(jù)以上分析，定義如下遞推關系：若V[i,j]對應子集不包含第i個物品wi，有V[i,j]=V[i1,j]。若V[i,j]對應子集包含第i個物品wi，即最優(yōu)子集由第i個 物品wi及在最前面i1個物品中適合容量為jwi的子集 構成的，有V[i,j]=V[i1,jwi]+

vi。綜上所述，最前面i個物品的所有可行的子集中，最 優(yōu)解的價值是上述兩者中的最大者。第60頁，課件共83頁，創(chuàng)作于2023年2月60動態(tài)規(guī)劃(0/1背包問題)

舉例設物品體積集W={2,3,4,5}，V={3,4,5,7}及C=9，V[0…n,0…C]，H[1…n,0…C]和X[1n]

H[]0123456789100111111112000111111130000111111400000111111197308121087543007541298754300543777744300432333333300321000000000VWi976543210CV[]X[]0011X[]1110第61頁，課件共83頁，創(chuàng)作于2023年2月61動態(tài)規(guī)劃(0/1背包問題)

算法:

KNAPSACK

輸入:

n種物品體積數(shù)組W[1n]和V[0n,0C]價值數(shù) 組，背包容量C

輸出:

最優(yōu)

值V[n,C]及最優(yōu)解信息數(shù)組H[0n,0C]

KNAPSACK(n,C)

過程

KNAPSACK(n,C)1

fori←0ton2V[i,0]←03endfor4forj←0toC5V[0,j]←06endfor

計算最優(yōu)值及算法

1.自底向上方法算法如下第62頁，課件共83頁，創(chuàng)作于2023年2月62動態(tài)規(guī)劃(0/1背包問題)

7fori←1ton8forj←1toC9V[i,j]←V[i-1,j]10ifwi<=jthen11ifV[i,j]<V[i-1,j-wi]+vithen12V[i,j]←V[i-1,j-wi]+vi13H[i,j]←114else15H[i,j]←016endif17endif18endfor19endfor20returnV[n,C]和H復雜性分析T(n)=(nC)第63頁，課件共83頁，創(chuàng)作于2023年2月63動態(tài)規(guī)劃(0/1背包問題)2.備忘錄方法用自頂向下的直接遞歸方法(并非所有的子問題都需要解)，數(shù)組V[0n,0C]存儲各子問題的最優(yōu)值，數(shù)組X[0n,0C]存儲最優(yōu)解的信息。

算法:

KNAPSACKREC 輸入:n種物品體積數(shù)組W[1n]和V[1n,0C]價值 數(shù)組，背包容量C 輸出:

最優(yōu)值V[n,C]及最優(yōu)解信息數(shù)組H[0n,0C]1

fori←0ton2forj←0toC3V[i,j]←14endfor5endfor6maxv←knapsack(n,C)7returnmaxv,H第64頁，課件共83頁，創(chuàng)作于2023年2月64動態(tài)規(guī)劃(0/1背包問題)

過程knapsack(i,j)1ifV[i,j]=1then2ifi=0orj=0thenV[i,j]←03else 4b←knapsack(i-1,j)5ifw[i]<=jthen6a←knapsack(i-1,j-w[i])+v[i]；7ifa>=bthen8V[i,j]←a;H[i,j]←19else10V[i,j]←b;H[i,j]←011endif12endif13endif14endif15returnV[n,C],H復雜性分析T(n)=(nC)第65頁，課件共83頁，創(chuàng)作于2023年2月65構造最優(yōu)解

算法SOLUTION

輸入n種物品體積數(shù)組W[1n]和V[1n,0C]價值 數(shù)組，背包容量C及H[0n,0C]

輸出

C中最大總價值及最優(yōu)解信息數(shù)組X[1n]

SOLUTION(n,C)

過程SOLUTION(n,C)1y←C2X[n]←H[n,C]3fori←ndownto14ifX[i]=1theny←y-w[i]5X[i-1]←H[i-1,y]6endfor7returnX動態(tài)規(guī)劃(0/1背包問題)復雜性分析

T(n)=(n)第66頁，課件共83頁，創(chuàng)作于2023年2月66本節(jié)作業(yè)1.教材P1043-4（1）第67頁，課件共83頁，創(chuàng)作于2023年2月67第六節(jié)主要內(nèi)容動態(tài)規(guī)劃條件子問題的重疊性

逆序、正序遞推法的可歸納為以下四個步驟最優(yōu)子結構：找出最優(yōu)解的性質(zhì)，并刻畫其結構特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計算最優(yōu)值：自底向上或自頂向下計算出最優(yōu)值。構造最優(yōu)解：由計算最優(yōu)值的信息，構造最優(yōu)解。運用動態(tài)規(guī)劃求解經(jīng)典實例最優(yōu)二叉搜索樹問題第68頁，課件共83頁，創(chuàng)作于2023年2月68教學目標動態(tài)規(guī)劃適用條件充分理解子問題的重疊性理解動態(tài)規(guī)劃的術語熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結構熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計算最優(yōu)值掌握用最優(yōu)值相關信息，求最優(yōu)解理解實例的解題步驟第69頁，課件共83頁，創(chuàng)作于2023年2月69二叉搜索樹

設X={x1，x2，…，xn}是一個有序集，即x1<x2<…<xn。用二叉樹的結點存儲X中的元素，這此結點稱為內(nèi)部結點。X的二叉搜索樹T具有如下性質(zhì)：(1)若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；(2)若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；(3)它的左、右子樹也分別為二叉搜索樹451253337249961動態(tài)規(guī)劃(最優(yōu)二叉搜索樹問題)

在隨機的情況下，二叉搜索樹的查找成功或者不成功比較次數(shù)最多不超過第70頁，課件共83頁，創(chuàng)作于2023年2月70動態(tài)規(guī)劃(最優(yōu)二叉搜索樹問題)問題提出 設X={x1，x2，…,xn}是一個有序集。若其元素在“等概率”前提下，在搜索樹下的二分查找，其性能最優(yōu)。若去除“等概率”的前提，在搜索樹下的二分查找，其性并不一定能最優(yōu)?，F(xiàn)在，考慮X有序集中的各個元素在“不等概率”情況下，如何構造一棵平均查找次數(shù)(或路徑)最少的二叉搜索樹，稱之為最優(yōu)二叉搜索樹，簡稱最優(yōu)搜索樹。最優(yōu)搜索樹是客觀存在的事實。首先，考察靜態(tài)最優(yōu)搜索樹(或稱次優(yōu)搜索樹)，設5個關鍵字的有序表及其元素相應權值(或查找成功概率)為： 關鍵字ABCDE 權值1302293則構造次優(yōu)搜索樹如下：

第71頁，課件共83頁，創(chuàng)作于2023年2月71（1）構造算法次優(yōu)查找樹的時間復雜度：O(nlogn)（2）次優(yōu)查找樹的特點它與最優(yōu)查找樹時間復雜度相差不超過3%，但構造容易；其平均查找長度和logn成正比；在元素的查找概率不等時，可用次優(yōu)查找樹表示靜態(tài)查找樹，故稱靜態(tài)查找樹表。ECDABEADBC平均查找路長為132的搜索樹動態(tài)規(guī)劃(最優(yōu)二叉搜索樹問題)平均查找路長為105的搜索樹第72頁，課件共83頁，創(chuàng)作于2023年2月72現(xiàn)在，不僅要考察查找成功概率，也要考察查找不成功概率的情況，于是，在T中搜索一個元素x，返回的結果是：(1)找到T中的內(nèi)部結點xi=x，設bi為xi的查找成功概率；(2)沒找到，即有葉子結點(xi，xi+1)。設ai為x的查找不成 功概率。有：動態(tài)規(guī)劃(最優(yōu)二叉搜索樹問題)

二叉搜索樹的平均比較次數(shù)(或路長)第73頁，課件共83頁，創(chuàng)作于2023年2月73蠻力方法時間復雜度

n個內(nèi)部結點和n+1個葉子結點的不同二叉搜索樹表示了不同的搜索策略。n個內(nèi)部結點共有 棵不同二叉搜索樹。故 ，見右圖。動態(tài)規(guī)劃(最優(yōu)二叉搜索樹問題)最優(yōu)子結構二叉搜索樹T的一棵含有內(nèi)部結點xi，…，xj和葉子結點(xi-1，xi)，…，(xj，xj+1)的子樹可以看作是有序集{xi，…,xj}關于全集合{xi-1，…，xj+1}的一棵二叉搜索樹，其存取概率為下面的條件概率(bi、ai分別為查找xi成功、不成功概率)xkT(1,k-1)T(k+1,n)T(1,n)第74頁，課件共83頁，創(chuàng)作于2023年2月74動態(tài)規(guī)劃(最優(yōu)二叉搜索樹問題)

設有序集{xi，…，xj}關于存取概率的一棵最優(yōu)二