算法設(shè)計(jì)第三章 動(dòng)態(tài)規(guī)劃

教學(xué)目標(biāo)動(dòng)態(tài)規(guī)劃的原理理解多階段決策過(guò)程及特點(diǎn)理解動(dòng)態(tài)規(guī)劃的術(shù)語(yǔ)熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程最優(yōu)性定理和基本方程充分理解最優(yōu)性定理熟記、理解兩種動(dòng)態(tài)規(guī)劃的基本方程掌握動(dòng)態(tài)規(guī)劃求解的基本步驟動(dòng)態(tài)規(guī)劃特點(diǎn)、條件和步驟熟記動(dòng)態(tài)規(guī)劃的適用條件熟記逆序、正序遞推法的可歸納為以下四個(gè)步驟第一頁(yè)，共八十三頁(yè)，2022年，8月28日1動(dòng)態(tài)規(guī)劃的原理(多階段決策問(wèn)題)

多階段決策過(guò)程多階段決策過(guò)程是活動(dòng)過(guò)程可按時(shí)間或空間順序分解成若干相互獨(dú)立、相互聯(lián)系的階段，在每個(gè)階段的狀態(tài)下做出決策，整個(gè)過(guò)程的決策構(gòu)成一個(gè)決策序列，則稱多階段決策過(guò)程為序貫決策過(guò)程。稱問(wèn)題為多階段決策問(wèn)題。狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5決策2決策3決策4決策1多階段決策問(wèn)題的特點(diǎn)過(guò)程可分為若干個(gè)相互聯(lián)系的階段；每一階段都對(duì)應(yīng)著一組可供選擇的決策；每一決策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。第二頁(yè)，共八十三頁(yè)，2022年，8月28日2動(dòng)態(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動(dòng)態(tài)規(guī)劃把多階段過(guò)程的問(wèn)題轉(zhuǎn)化為一系列單階段的問(wèn)題，逐個(gè)階段求解的最優(yōu)化數(shù)學(xué)方法。第三頁(yè)，共八十三頁(yè)，2022年，8月28日3動(dòng)態(tài)規(guī)劃的原理動(dòng)態(tài)規(guī)劃的術(shù)語(yǔ)階段：將過(guò)程劃分為k個(gè)階段，1k

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

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

允許的取值范圍，記為

。決策：表示第k階段狀態(tài)的決策變量，簡(jiǎn)記為。允許決策集合：允許的取值范圍。策略：一個(gè)按順序排列的決策序列，記。狀態(tài)轉(zhuǎn)移方程：從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段某一狀態(tài)值的轉(zhuǎn)移規(guī)律，記為。子策略：稱決策序列為k子過(guò)程策略。簡(jiǎn)稱子策略，記為第四頁(yè)，共八十三頁(yè)，2022年，8月28日4動(dòng)態(tài)規(guī)劃的原理

當(dāng)k=1時(shí)，成為全過(guò)程的一個(gè)策略，簡(jiǎn)稱策略，簡(jiǎn)記為。階段指標(biāo)函數(shù)：指第k階段從狀態(tài)出發(fā)，采取決策時(shí)的效益，用表示。過(guò)程指標(biāo)函數(shù)：從第k階段的狀態(tài)出發(fā)，采取子策略 獲得最佳效益記為。最優(yōu)性函數(shù)：若采用最優(yōu)子策略，從第k階段的出發(fā)獲得最佳效益 第五頁(yè)，共八十三頁(yè)，2022年，8月28日5動(dòng)態(tài)規(guī)劃的原理其中opt可根據(jù)具體情況取max或min。是可分函數(shù)，具有可加性或可乘性最優(yōu)性基本方程第六頁(yè)，共八十三頁(yè)，2022年，8月28日6最優(yōu)性定理和基本方程

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

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

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

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

3．，及其它階段的計(jì)算類似。，最短路徑為。第九頁(yè)，共八十三頁(yè)，2022年，8月28日9動(dòng)態(tài)規(guī)劃特點(diǎn)、條件和步驟動(dòng)態(tài)規(guī)劃的適用條件

適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足以下三個(gè)條件

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

子問(wèn)題的重疊性動(dòng)態(tài)規(guī)劃特點(diǎn)優(yōu)點(diǎn)離散性問(wèn)題：使解析數(shù)學(xué)無(wú)用武之地；建模：可用計(jì)算機(jī)計(jì)算；缺點(diǎn)無(wú)統(tǒng)一處理方法：需要數(shù)學(xué)技巧與解題經(jīng)驗(yàn)；組合爆炸：只能解決中小規(guī)模的問(wèn)題第十頁(yè)，共八十三頁(yè)，2022年，8月28日10動(dòng)態(tài)規(guī)劃特點(diǎn)、條件和步驟最優(yōu)性定理（最優(yōu)子結(jié)構(gòu)性質(zhì)）

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

無(wú)后向性

將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，只能通過(guò)當(dāng)前給定的狀態(tài)，直接影響未來(lái)的決策，而與以前各階段的狀態(tài)無(wú)關(guān)，這就是無(wú)后向性，又稱為無(wú)后效性。換句話說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。第十一頁(yè)，共八十三頁(yè)，2022年，8月28日11動(dòng)態(tài)規(guī)劃特點(diǎn)、條件和步驟子問(wèn)題的重疊性

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

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

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

G=<V，E>是一個(gè)多級(jí)圖，如下圖所示。第1階段第2階段第3階段第4階段狀態(tài)1狀態(tài)2狀態(tài)4狀態(tài)5狀態(tài)3決策1決策2決策4決策3第十七頁(yè)，共八十三頁(yè)，2022年，8月28日17動(dòng)態(tài)規(guī)劃(單源最短路徑)最優(yōu)子結(jié)構(gòu)

假設(shè)第

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

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

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

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

設(shè)過(guò)程共有k個(gè)級(jí)，即k1個(gè)階段。又設(shè)Piv表示從V

i中的頂點(diǎn)v到H的一條最短路徑，Cost(i,v)表示這條路徑的代價(jià)，按照由后向前推進(jìn)，可得：

第十八頁(yè)，共八十三頁(yè)，2022年，8月28日18動(dòng)態(tài)規(guī)劃(單源最短路徑)計(jì)算最優(yōu)值算法：Min_PathCost

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

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

1.fori←1ton12.Cost[i]←3.endfor4.Cost[n]←05.forj←n1downto16.設(shè)u使得(j,u)邊集且C[j][u]+Cost[u]為最小7.Cost[j]←C[j][u]+Cost[u]8.D[j]←u9.endfor10.returnCost[1]第十九頁(yè)，共八十三頁(yè)，2022年，8月28日19動(dòng)態(tài)規(guī)劃(單源最短路徑)構(gòu)造最優(yōu)解

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

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

時(shí)間復(fù)雜性：T(n)=(n2)空間復(fù)雜性：S(n)==(n)若A為鄰接表：則T(n)=O(n+|E|)，其中n為頂點(diǎn)數(shù)，|E|為邊集大小。第二十頁(yè)，共八十三頁(yè)，2022年，8月28日20動(dòng)態(tài)規(guī)劃(所有點(diǎn)對(duì)的最短路徑)問(wèn)題提出設(shè)G=<V，E>是一個(gè)簡(jiǎn)單有向圖，其中每條邊<i，j>長(zhǎng)度w[i，j]0。若頂點(diǎn)i到頂點(diǎn)j沒(méi)有邊，則w[i，j]=，若i=j，則w[i，j]=0。G用鄰接矩陣W表示。問(wèn)題是找出每個(gè)頂點(diǎn)到其它所有頂點(diǎn)的最短路徑。顯然，鄰接矩陣W本身表示V中每個(gè)頂點(diǎn)i到其它所有頂點(diǎn)j，而不經(jīng)過(guò)任何中間頂點(diǎn)的最短路徑，記為pij0。

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

。

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

最優(yōu)子結(jié)構(gòu)由pijk定義知：當(dāng)頂點(diǎn)i到其它所有頂點(diǎn)j，經(jīng)過(guò)中間頂點(diǎn)序號(hào)不大于k1的最短路徑恰好為pijk1，即有pijk=pijk1。第二十一頁(yè)，共八十三頁(yè)，2022年，8月28日21動(dòng)態(tài)規(guī)劃(所有點(diǎn)對(duì)的最短路徑)

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

設(shè)Dk(i，j)是任一頂點(diǎn)i到其它所有頂點(diǎn)j，且經(jīng)過(guò)中間頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度。特別D0(i，j)=W。

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

Dk1(i，k)任一頂點(diǎn)i到頂點(diǎn)k，且經(jīng)過(guò)中間頂點(diǎn)序號(hào)不大于k1的最短路徑長(zhǎng)度。

第二十二頁(yè)，共八十三頁(yè)，2022年，8月28日22動(dòng)態(tài)規(guī)劃(所有點(diǎn)對(duì)的最短路徑)

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

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

算法：Floyd

輸入：鄰接矩陣W

輸出：

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

Floyd(W，next)過(guò)程：Floyd(D，next)第二十三頁(yè)，共八十三頁(yè)，2022年，8月28日23動(dòng)態(tài)規(guī)劃(所有點(diǎn)對(duì)的最短路徑)

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第二十四頁(yè)，共八十三頁(yè)，2022年，8月28日24動(dòng)態(tài)規(guī)劃(所有點(diǎn)對(duì)的最短路徑)構(gòu)造最優(yōu)解

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

算法：Print_Path

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

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

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

1.ifnext[i][j]=jthen2.print(ij)3.return第二十五頁(yè)，共八十三頁(yè)，2022年，8月28日25動(dòng)態(tài)規(guī)劃(所有點(diǎn)對(duì)的最短路徑)4.endif5.print(i)6.print_path(next，next[i][j]，j)

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

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

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

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

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

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

舉例：X=abcbdab，Y=bdcaba4432210b74332210a63322210d53322110b42222110c32211110b21110000a1000000Xi0abacdb6543210bacb遞歸推導(dǎo)得解：bcbaYjijnulnul0第三十三頁(yè)，共八十三頁(yè)，2022年，8月28日33動(dòng)態(tài)規(guī)劃(最長(zhǎng)公共子序列問(wèn)題)

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

算法：LCSLENGTH

輸入：字母表上的兩個(gè)字符串A和B及長(zhǎng)度n,m

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

1 fori←0ton 2 L[i,0]←0 3 endfor4forj←0tom 5 L[0,j]←0 6 endfor第三十四頁(yè)，共八十三頁(yè)，2022年，8月28日34動(dòng)態(tài)規(guī)劃(最長(zhǎng)公共子序列問(wèn)題)

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復(fù)雜性分析 T(n)=(nm)改進(jìn)

T(n)=min{m,n}第三十五頁(yè)，共八十三頁(yè)，2022年，8月28日35構(gòu)造最優(yōu)解

算法：LCS

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

輸出：輸出最長(zhǎng)公共子序列xLCS(n,m,x,s)過(guò)程：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動(dòng)態(tài)規(guī)劃(最長(zhǎng)公共子序列問(wèn)題)復(fù)雜性分析

T(n)=O(n+m)第三十六頁(yè)，共八十三頁(yè)，2022年，8月28日36本節(jié)思考題1.用動(dòng)態(tài)規(guī)劃方法，編寫一個(gè)循環(huán)迭代算法，求解給定序列的最長(zhǎng)遞增子序列。第三十七頁(yè)，共八十三頁(yè)，2022年，8月28日37第四節(jié)主要內(nèi)容動(dòng)態(tài)規(guī)劃條件子問(wèn)題的重疊性

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

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

…Mk

)

(Mk+1Mk+2

…Mn

))則有：復(fù)雜性分析

見(jiàn)數(shù)據(jù)結(jié)構(gòu)P152的解法第四十一頁(yè)，共八十三頁(yè)，2022年，8月28日41動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)每個(gè)括弧化表達(dá)式，有n-1次的矩陣乘法次數(shù)，即矩陣乘法時(shí)間是(n)。因此，數(shù)乘次數(shù)的時(shí)間復(fù)雜性為：最優(yōu)子結(jié)構(gòu)性質(zhì)

設(shè)對(duì)于任意矩陣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]，則計(jì)算C[i，j]： C[i，j]=C[i，k1]+C[k，j]+rirkrj+1復(fù)雜性分析

第四十二頁(yè)，共八十三頁(yè)，2022年，8月28日42動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)這導(dǎo)致尋找一個(gè)k，i+1kj，使得C[i，j]最少，即特別地計(jì)算M1,n的一個(gè)最優(yōu)順序包含計(jì)算矩陣子鏈M1,k-1

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

舉例計(jì)算5個(gè)矩陣乘積最少數(shù)乘次數(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的計(jì)算形式348262043203200202483640324030168424040120500第四十五頁(yè)，共八十三頁(yè)，2022年，8月28日45動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)

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

算法：MATCHAIN

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

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

過(guò)程MATCHAIN(n)第四十六頁(yè)，共八十三頁(yè)，2022年，8月28日46動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)

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算法復(fù)雜度分析：MATCHAIN算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。第四十七頁(yè)，共八十三頁(yè)，2022年，8月28日47動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)構(gòu)造最優(yōu)解(最少數(shù)乘的矩陣鏈)MATCHAIN算法用s[i,j]記錄矩陣乘積的最優(yōu)計(jì)算次序全部信息，即計(jì)算Mi,j矩陣時(shí)，保存斷開(kāi)矩陣Mi,k-1和Mk,j斷開(kāi)點(diǎn)k。因?yàn)閟[1,n]記錄M1,n的最優(yōu)括弧表達(dá)式，即有：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))以此類推構(gòu)造最優(yōu)解。顯然，若要輸出矩陣鏈的最優(yōu)計(jì)算順序，還要有一個(gè)輸出最優(yōu)解的算法，請(qǐng)參見(jiàn)教材P66一節(jié)。下列MChainMuliply算法輸出Mi,j的最優(yōu)計(jì)算次序的運(yùn)算結(jié)果。

第四十八頁(yè)，共八十三頁(yè)，2022年，8月28日48動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)算法：MChainMuliply輸入：s[1n,1n]及1和n

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

MChainMuliply(1,n,s)

過(guò)程MChainMuliply(i,j,s)1ifi=jreturnMi2X←MChainMuliply(i,s[i,j]-1,s)3Y←MChainMuliply(s[i,j],j,s)4returnMultiply(XY)首先，假設(shè)算法Multiply(X，Y)表示矩陣X與Y的兩個(gè)矩陣一般乘積，那么，MChainMuliply算法描述如下：第四十九頁(yè)，共八十三頁(yè)，2022年，8月28日49動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)

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

1.最優(yōu)子結(jié)構(gòu)性質(zhì)；2.重疊子問(wèn)題；1.最優(yōu)子結(jié)構(gòu)性質(zhì)

自底向上求解子問(wèn)題的最優(yōu)解，逐步構(gòu)造問(wèn)題最優(yōu)解。2.重疊子問(wèn)題用自頂向下的直接遞歸方式求解子問(wèn)題，子問(wèn)題有重復(fù)。計(jì)算M1,4的遞歸樹(shù)第五十頁(yè)，共八十三頁(yè)，2022年，8月28日50算法：RecMatChain輸入：

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

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

過(guò)程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動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)最壞情況下復(fù)雜性分析

第五十一頁(yè)，共八十三頁(yè)，2022年，8月28日51動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題)3.備忘錄方法

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

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

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

過(guò)程MemMatChain(n)1 fori←1ton2forj←iton3C[i,j]←04endfor5endfor6returnLookupChain(1,n)第五十二頁(yè)，共八十三頁(yè)，2022年，8月28日52動(dòng)態(tài)規(guī)劃(矩陣連乘積問(wèn)題) 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復(fù)雜性分析

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

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

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

逆序、正序遞推法的可歸納為以下四個(gè)步驟最優(yōu)子結(jié)構(gòu)：找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計(jì)算最優(yōu)值：自底向上或自頂向下計(jì)算出最優(yōu)值。構(gòu)造最優(yōu)解：由計(jì)算最優(yōu)值的信息，構(gòu)造最優(yōu)解。運(yùn)用動(dòng)態(tài)規(guī)劃求解經(jīng)典實(shí)例0/1背包問(wèn)題第五十五頁(yè)，共八十三頁(yè)，2022年，8月28日55教學(xué)目標(biāo)動(dòng)態(tài)規(guī)劃適用條件充分理解子問(wèn)題的重疊性理解動(dòng)態(tài)規(guī)劃的術(shù)語(yǔ)熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動(dòng)態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結(jié)構(gòu)熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計(jì)算最優(yōu)值掌握用最優(yōu)值相關(guān)信息，求最優(yōu)解理解實(shí)例的解題步驟第五十六頁(yè)，共八十三頁(yè)，2022年，8月28日56動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)

問(wèn)題提出

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

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

最優(yōu)子結(jié)構(gòu)性質(zhì)1設(shè)(x1,x2,…,xn)為0/1背包問(wèn)題的一個(gè)最優(yōu)解，則(x2,…,xn)是相應(yīng)子問(wèn)題的一個(gè)最優(yōu)解：第五十七頁(yè)，共八十三頁(yè)，2022年，8月28日57動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)若不然，設(shè)(z2,…,zn)是上述子問(wèn)題的一個(gè)最優(yōu)解，而(x2,…,xn)不是它的最優(yōu)解。由此可知：且因此第五十八頁(yè)，共八十三頁(yè)，2022年，8月28日58動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)這說(shuō)明(x1,z2,…,zn)是所給0/1背包問(wèn)題的一個(gè)更優(yōu)解，而(x1,x2,…,xn)不是問(wèn)題0/1背包問(wèn)題的一個(gè)最優(yōu)解，此為矛盾。這說(shuō)明(x1,x2,…,xn)不是問(wèn)題0/1背包問(wèn)題的一個(gè)最優(yōu)解。最優(yōu)子結(jié)構(gòu)2

設(shè)V[i,j]表示從W中選擇最前面i個(gè)物品組成的物品子集{w1,w2,…,wi}裝入容量為j的背包總價(jià)值。于是得到：第五十九頁(yè)，共八十三頁(yè)，2022年，8月28日59動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)遞歸定義最優(yōu)值

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

vi。綜上所述，最前面i個(gè)物品的所有可行的子集中，最 優(yōu)解的價(jià)值是上述兩者中的最大者。第六十頁(yè)，共八十三頁(yè)，2022年，8月28日60動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)

舉例設(shè)物品體積集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第六十一頁(yè)，共八十三頁(yè)，2022年，8月28日61動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)

算法:

KNAPSACK

輸入:

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

輸出:

最優(yōu)

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

KNAPSACK(n,C)

過(guò)程

KNAPSACK(n,C)1

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

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

1.自底向上方法算法如下第六十二頁(yè)，共八十三頁(yè)，2022年，8月28日62動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)

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復(fù)雜性分析T(n)=(nC)第六十三頁(yè)，共八十三頁(yè)，2022年，8月28日63動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)2.備忘錄方法用自頂向下的直接遞歸方法(并非所有的子問(wèn)題都需要解)，數(shù)組V[0n,0C]存儲(chǔ)各子問(wèn)題的最優(yōu)值，數(shù)組X[0n,0C]存儲(chǔ)最優(yōu)解的信息。

算法:

KNAPSACKREC 輸入:n種物品體積數(shù)組W[1n]和V[1n,0C]價(jià)值 數(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第六十四頁(yè)，共八十三頁(yè)，2022年，8月28日64動(dòng)態(tài)規(guī)劃(0/1背包問(wèn)題)

過(guò)程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復(fù)雜性分析T(n)=(nC)第六十五頁(yè)，共八十三頁(yè)，2022年，8月28日65構(gòu)造最優(yōu)解

算法SOLUTION

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

輸出

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

SOLUTION(n,C)

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

T(n)=(n)第六十六頁(yè)，共八十三頁(yè)，2022年，8月28日66本節(jié)作業(yè)1.教材P1043-4（1）第六十七頁(yè)，共八十三頁(yè)，2022年，8月28日67第六節(jié)主要內(nèi)容動(dòng)態(tài)規(guī)劃條件子問(wèn)題的重疊性

逆序、正序遞推法的可歸納為以下四個(gè)步驟最優(yōu)子結(jié)構(gòu)：找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。最優(yōu)值定義：遞歸定義最優(yōu)值。計(jì)算最優(yōu)值：自底向上或自頂向下計(jì)算出最優(yōu)值。構(gòu)造最優(yōu)解：由計(jì)算最優(yōu)值的信息，構(gòu)造最優(yōu)解。運(yùn)用動(dòng)態(tài)規(guī)劃求解經(jīng)典實(shí)例最優(yōu)二叉搜索樹(shù)問(wèn)題第六十八頁(yè)，共八十三頁(yè)，2022年，8月28日68教學(xué)目標(biāo)動(dòng)態(tài)規(guī)劃適用條件充分理解子問(wèn)題的重疊性理解動(dòng)態(tài)規(guī)劃的術(shù)語(yǔ)熟悉最優(yōu)值函數(shù)、最優(yōu)值基本方程動(dòng)態(tài)規(guī)劃的解題步驟熟練利用基本方程刻劃最優(yōu)子結(jié)構(gòu)熟練利用基本方程遞歸定義最優(yōu)值掌握自底向上方法計(jì)算最優(yōu)值掌握用最優(yōu)值相關(guān)信息，求最優(yōu)解理解實(shí)例的解題步驟第六十九頁(yè)，共八十三頁(yè)，2022年，8月28日69二叉搜索樹(shù)

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

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

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

二叉搜索樹(shù)的平均比較次數(shù)(或路長(zhǎng))第七十三頁(yè)，共八十三頁(yè)，2022年，8月28日73蠻力方法時(shí)間復(fù)雜度

n個(gè)內(nèi)部結(jié)點(diǎn)和n+1個(gè)葉子結(jié)點(diǎn)的不同二叉搜索樹(shù)表示了不同的搜索策略。n個(gè)內(nèi)部結(jié)點(diǎn)共有 棵不同二叉搜索樹(shù)。故 ，見(jiàn)右圖。動(dòng)態(tài)規(guī)劃(最優(yōu)二叉搜索樹(shù)問(wèn)題)最優(yōu)子結(jié)構(gòu)二叉搜索樹(shù)T的一棵含有內(nèi)部結(jié)點(diǎn)xi，…，xj和葉子結(jié)點(diǎn)(xi-1，xi)，…，(xj，xj+1)的子樹(shù)可以看作是有序集{xi，…,xj}關(guān)于全集合{xi-1，…，xj+1}的一棵二叉搜索樹(shù)，其存取概率為下面的條件概率(bi、ai分別為查找xi成功、不成功概率)xkT(1,k-1)T(k+1,n)T(1,n)第七十四頁(yè)，共八十三頁(yè)，2022年，8月28日74動(dòng)態(tài)規(guī)劃(最優(yōu)二叉搜索樹(shù)問(wèn)題)

設(shè)有序集{xi，…，xj}關(guān)于存取概率的一棵最優(yōu)二叉搜索