第八章 動(dòng)態(tài)規(guī)劃

1、12 動(dòng)態(tài)規(guī)劃(Dynamic Programming)是應(yīng)用數(shù)學(xué)是應(yīng)用數(shù)學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域中一個(gè)非常重要的算法設(shè)計(jì)技和計(jì)算機(jī)科學(xué)領(lǐng)域中一個(gè)非常重要的算法設(shè)計(jì)技術(shù)術(shù) 美國(guó)數(shù)學(xué)家美國(guó)數(shù)學(xué)家Richard Bellman于于20世紀(jì)世紀(jì)50年代發(fā)年代發(fā)明，用于明，用于解決多階段決策過(guò)程最優(yōu)問(wèn)題解決多階段決策過(guò)程最優(yōu)問(wèn)題 這里的這里的Programming是計(jì)劃和規(guī)劃的意思是計(jì)劃和規(guī)劃的意思3 1.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） 一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問(wèn)題滿一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問(wèn)題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)足最優(yōu)化原理又稱其具有

2、最優(yōu)子結(jié)構(gòu)性質(zhì) 使我們可以使我們可以自底向上自底向上的方式從的方式從子問(wèn)題的最優(yōu)解子問(wèn)題的最優(yōu)解逐步逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。 最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問(wèn)題，如果失最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問(wèn)題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算計(jì)算 若路線若路線I I和和J J是是A A到到C C的最優(yōu)路徑，則的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線根據(jù)最優(yōu)化原理，路線J J必是從必是從B B到到C C的最優(yōu)路線。的最優(yōu)路線。4 2.無(wú)后向性無(wú)后向性 將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給將各階段按照一定

3、的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無(wú)法直接影響定的階段狀態(tài)，它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策，而只能通過(guò)當(dāng)前的這個(gè)狀態(tài)。它未來(lái)的決策，而只能通過(guò)當(dāng)前的這個(gè)狀態(tài)。換句話說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。換句話說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱為無(wú)后效性。這就是無(wú)后向性，又稱為無(wú)后效性。 5 3.子問(wèn)題的重疊性子問(wèn)題的重疊性(非必要條件非必要條件) 該條件為非必要條件，該條件為非必要條件，但是缺少此條件，則動(dòng)態(tài)規(guī)劃方法與別的方法相比毫無(wú)優(yōu)勢(shì)。但是缺少此條件，則動(dòng)態(tài)規(guī)劃方法與別的方法相比毫無(wú)優(yōu)勢(shì)。 每次產(chǎn)生的子問(wèn)題并不是新的子問(wèn)題，

4、有些子問(wèn)題被重復(fù)計(jì)每次產(chǎn)生的子問(wèn)題并不是新的子問(wèn)題，有些子問(wèn)題被重復(fù)計(jì)算。算。 在解某一問(wèn)題中，相同的子問(wèn)題反復(fù)出現(xiàn)，并且不同子問(wèn)題在解某一問(wèn)題中，相同的子問(wèn)題反復(fù)出現(xiàn)，并且不同子問(wèn)題的個(gè)數(shù)又相對(duì)較少時(shí)，用動(dòng)態(tài)規(guī)劃是有效的。的個(gè)數(shù)又相對(duì)較少時(shí)，用動(dòng)態(tài)規(guī)劃是有效的。 動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。所以它的空間復(fù)雜度要大于其它的算法。6 基本思路：基本思路： （1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。）找出最優(yōu)解的

5、性質(zhì)，并刻畫其結(jié)構(gòu)特征。 （2）遞歸地定義最優(yōu)值。）遞歸地定義最優(yōu)值。 （3）以）以自底向上自底向上的方式計(jì)算出最優(yōu)值。的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。最優(yōu)解。 與分治法比較與分治法比較 都將問(wèn)題劃分為若干個(gè)子問(wèn)題都將問(wèn)題劃分為若干個(gè)子問(wèn)題 分治法中各子問(wèn)題相互獨(dú)立，而動(dòng)態(tài)規(guī)劃中各子問(wèn)分治法中各子問(wèn)題相互獨(dú)立，而動(dòng)態(tài)規(guī)劃中各子問(wèn)題允許相互交疊題允許相互交疊7 注意：注意： 動(dòng)態(tài)規(guī)劃一般用于多階段最優(yōu)化問(wèn)題動(dòng)態(tài)規(guī)劃一般用于多階段最優(yōu)化問(wèn)題 但是書中但是書中 8.1 計(jì)算二項(xiàng)式系數(shù)計(jì)算二項(xiàng)式系數(shù) 8.2.1 warsha

6、ll 并不是最優(yōu)化問(wèn)題。并不是最優(yōu)化問(wèn)題。 8.2.2 floyed 8.3 最優(yōu)二叉查找樹最優(yōu)二叉查找樹 8.4 背包問(wèn)題背包問(wèn)題 才是最優(yōu)化問(wèn)題才是最優(yōu)化問(wèn)題對(duì)于交疊的子問(wèn)題，對(duì)于交疊的子問(wèn)題，無(wú)需一次又一次的求無(wú)需一次又一次的求解，只需將每個(gè)較小解，只需將每個(gè)較小子問(wèn)題求解一次并把子問(wèn)題求解一次并把結(jié)果記錄在表中。結(jié)果記錄在表中。8 二項(xiàng)式系數(shù)，記作二項(xiàng)式系數(shù)，記作C(n,k)或者或者 ，是來(lái)自于一個(gè)，是來(lái)自于一個(gè)n元素元素集合的集合的k元素組合元素組合(子集子集)的數(shù)量的數(shù)量(0kn) 該名字來(lái)源于二項(xiàng)式公式該名字來(lái)源于二項(xiàng)式公式 遞推式遞推式(特性特性) C(n, k) = C(n-

7、1, k-1) + C(n-1, k), 當(dāng)當(dāng)n k 0 C(n, 0) = C(n, n) = 1 因此計(jì)算因此計(jì)算C(n, k) 變?yōu)樽優(yōu)镃(n-1, k-1) 和和C(n-1, k)兩兩個(gè)較小的交疊問(wèn)題個(gè)較小的交疊問(wèn)題nk ()( ,0).( , ).( , )nnn iinabC naC n i abC n n b9 動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法 把二項(xiàng)式系數(shù)記錄在一張把二項(xiàng)式系數(shù)記錄在一張n+1行行k+1列的表中列的表中C(i,j)的值記錄的值記錄在第在第i行，第行，第j列列10 算法算法 Binomial(n,k) /用動(dòng)態(tài)規(guī)劃算法計(jì)算用動(dòng)態(tài)規(guī)劃算法計(jì)算C(n,k) /輸入：輸入：對(duì)非

8、負(fù)整數(shù)對(duì)非負(fù)整數(shù)n=k=0 /輸出：輸出：C(n,k)的值的值 for i 0 to n do for j 0 to min(i,k) do if j=0 or j=i Ci,j 1 else Ci,j Ci-1,j-1+Ci-1,j return Cn,k 11 時(shí)間效率分析時(shí)間效率分析 基本操作：加法基本操作：加法12 Warshall 算法用于計(jì)算有向圖傳遞閉包算法用于計(jì)算有向圖傳遞閉包 Floyd算法用于計(jì)算全部最短路徑算法用于計(jì)算全部最短路徑13 傳遞閉包定義傳遞閉包定義: 一個(gè)一個(gè)n頂點(diǎn)有向圖的傳遞閉包可頂點(diǎn)有向圖的傳遞閉包可以定義為一個(gè)以定義為一個(gè)n階布爾矩陣階布爾矩陣T=tij

9、，如果從第如果從第i個(gè)個(gè)頂點(diǎn)到第頂點(diǎn)到第j個(gè)頂點(diǎn)之間存在一條有效的有向路徑個(gè)頂點(diǎn)之間存在一條有效的有向路徑，矩陣第矩陣第i行行(1in)第第j列列(1jn)的元素為的元素為1；否則，；否則，tij為為 014dcba鄰接矩陣鄰接矩陣 a b c da 0 1 0 0b 0 0 0 1c 0 0 0 0d 1 0 1 0傳遞閉包傳遞閉包 a b c da 1 1 1 1b 1 1 1 1c 0 0 0 0d 1 1 1 115 求傳遞閉包是圖論中一個(gè)非常重要的問(wèn)題，求傳遞閉包是圖論中一個(gè)非常重要的問(wèn)題，例如給定了一個(gè)城市的交通地圖，可利用例如給定了一個(gè)城市的交通地圖，可利用求傳遞閉包的方法獲知任

10、意兩個(gè)地點(diǎn)之間求傳遞閉包的方法獲知任意兩個(gè)地點(diǎn)之間是否有路相連通。是否有路相連通。 用深度優(yōu)先查找和廣度優(yōu)先查找如何生成傳遞閉用深度優(yōu)先查找和廣度優(yōu)先查找如何生成傳遞閉包？包？16 void WARSHALL 輸入輸入:M，圖的鄰接矩陣，圖的鄰接矩陣 輸出輸出:M*，圖的傳遞閉包矩陣，圖的傳遞閉包矩陣 for (i=1; i n; i+ ) for (j1; j n; j+ ) if(M j，iT) for (k=1; i n; i+ ) m j，k + m i，k; (4) 該算法由鄰接矩陣在原地構(gòu)建傳遞閉包該算法由鄰接矩陣在原地構(gòu)建傳遞閉包上述算法必上述算法必定會(huì)在有限時(shí)間內(nèi)結(jié)束運(yùn)行。定會(huì)

11、在有限時(shí)間內(nèi)結(jié)束運(yùn)行。 WARSHALL算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(n3)。17 算法思想說(shuō)明算法思想說(shuō)明 搭橋找路徑搭橋找路徑 選取一個(gè)頂點(diǎn)作為橋梁，考察所有頂點(diǎn)，是否選取一個(gè)頂點(diǎn)作為橋梁，考察所有頂點(diǎn)，是否可以通過(guò)橋梁到達(dá)其它的頂點(diǎn)?？梢酝ㄟ^(guò)橋梁到達(dá)其它的頂點(diǎn)。 用用I控制依次選擇各頂點(diǎn)做橋梁。控制依次選擇各頂點(diǎn)做橋梁。 用用j控制當(dāng)選定某頂點(diǎn)做為橋梁時(shí)，依次考察所控制當(dāng)選定某頂點(diǎn)做為橋梁時(shí)，依次考察所有頂點(diǎn)。有頂點(diǎn)。 用用k控制當(dāng)橋梁選定時(shí)，考察某一頂點(diǎn)通過(guò)該橋控制當(dāng)橋梁選定時(shí)，考察某一頂點(diǎn)通過(guò)該橋梁是否可以到達(dá)其它頂點(diǎn)。梁是否可以到達(dá)其它頂點(diǎn)。18 外循環(huán)第一次，選擇外循環(huán)

12、第一次，選擇0作為橋梁作為橋梁 考察考察0是否可以通過(guò)是否可以通過(guò)0到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 1 0 1 0 0 1 考察考察1是否可以通過(guò)是否可以通過(guò)0到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 1 1 1 0 0 1 考察考察2是否可以通過(guò)是否可以通過(guò)0到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 0 1 1 0 0 0 考察考察3 0 0 1 1 1 0 考察考察4 0 0 0 0 1 1 考察考察5 0 0 0 0 1 11234050 1 2 3 4 50 1 0 1 0 0 11 1 1 0 0 0 02 0 1 1 0 0 03 0 0 1 1 1 04 0 0 0 0 1 15 0 0 0 0 1 1用用i控制控制

13、用用j控制控制用用k控制控制19 外循環(huán)第二次，增加外循環(huán)第二次，增加1為橋梁為橋梁 考察考察0是否可以通過(guò)是否可以通過(guò)1到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 1 0 1 0 0 1 考察考察1是否可以通過(guò)是否可以通過(guò)1到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 1 1 1 0 0 1 考察考察2是否可以通過(guò)是否可以通過(guò)1到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 1 1 1 0 0 1 考察考察3 0 0 1 1 1 0 考察考察4 0 0 0 0 1 1 考察考察5 0 0 0 0 1 10 1 2 3 4 50 1 0 1 0 0 11 1 1 1 0 0 12 0 1 1 0 0 03 0 0 1 1 1 04 0 0 0 0 1

14、15 0 0 0 0 1 1123405可看成是動(dòng)態(tài)可看成是動(dòng)態(tài)規(guī)劃的階段性，規(guī)劃的階段性，意味著可以通意味著可以通過(guò)過(guò)0，1。即當(dāng)。即當(dāng)前是否有路徑前是否有路徑可以建立在可以建立在前前一階段一階段的路徑的路徑基礎(chǔ)上?；A(chǔ)上。20 循環(huán)循環(huán)6次結(jié)束，次結(jié)束，M最終記錄了閉包矩最終記錄了閉包矩陣的信息。陣的信息。 實(shí)現(xiàn)細(xì)節(jié)說(shuō)明之一實(shí)現(xiàn)細(xì)節(jié)說(shuō)明之一 if(M j，iT) for (k=1; i n; i+ ) 當(dāng)當(dāng)M j，iF時(shí)說(shuō)明什么？時(shí)說(shuō)明什么？ 考察的頂點(diǎn)考察的頂點(diǎn)j到到橋梁橋梁i沒(méi)有路徑，沒(méi)有路徑， 也就意味著該頂點(diǎn)不可能通過(guò)選擇的橋梁建立到也就意味著該頂點(diǎn)不可能通過(guò)選擇的橋梁建立到其它頂

15、點(diǎn)的路徑，因此不必考察它通過(guò)該橋梁是其它頂點(diǎn)的路徑，因此不必考察它通過(guò)該橋梁是否可以到達(dá)其它頂點(diǎn)，即內(nèi)循環(huán)不用做。否可以到達(dá)其它頂點(diǎn)，即內(nèi)循環(huán)不用做。21 實(shí)現(xiàn)細(xì)節(jié)說(shuō)明之二實(shí)現(xiàn)細(xì)節(jié)說(shuō)明之二 if(M j，iT) for (k=1; i n; i+ ) m j，k + m i，k 紅色部分等同于紅色部分等同于 m j,k m i,k m j,i + m j,k 加號(hào)為邏輯加加號(hào)為邏輯加(OR)，乘號(hào)為邏輯乘，乘號(hào)為邏輯乘(and) 表達(dá)式含義表達(dá)式含義:考察頂點(diǎn)考察頂點(diǎn)j到到k是否經(jīng)過(guò)是否經(jīng)過(guò)i有路徑有路徑 觀察觀察m j,k的布爾值由什么決定的布爾值由什么決定 頂點(diǎn)頂點(diǎn)j到到k原來(lái)有路徑原來(lái)有

16、路徑 頂點(diǎn)頂點(diǎn)i到到k有路徑有路徑(j到到i有路徑隱含在有路徑隱含在if條件中條件中)22 定理定理 WARSHALL算法的輸出矩陣是輸入算法的輸出矩陣是輸入關(guān)系矩陣的傳遞閉包矩陣。關(guān)系矩陣的傳遞閉包矩陣。 證證 注意到算法的輸入、輸出矩陣都存儲(chǔ)注意到算法的輸入、輸出矩陣都存儲(chǔ)在在M中，與中，與M相應(yīng)的關(guān)系用相應(yīng)的關(guān)系用A表示。表示。 輸入關(guān)系用輸入關(guān)系用R表示，其傳遞閉包用表示，其傳遞閉包用R*表示。表示。則須證在算法運(yùn)行結(jié)束時(shí)則須證在算法運(yùn)行結(jié)束時(shí) 1. A R* 2. R* A 定理的證明分成相應(yīng)的兩部分。定理的證明分成相應(yīng)的兩部分。23 計(jì)算二項(xiàng)式系數(shù)與計(jì)算二項(xiàng)式系數(shù)與warshall

17、算法對(duì)動(dòng)態(tài)規(guī)劃法的算法對(duì)動(dòng)態(tài)規(guī)劃法的體現(xiàn)體現(xiàn) 1 并未體現(xiàn)出并未體現(xiàn)出最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)的特點(diǎn)的特點(diǎn) 2 計(jì)算二項(xiàng)式系數(shù)體現(xiàn)了計(jì)算二項(xiàng)式系數(shù)體現(xiàn)了重疊子問(wèn)題重疊子問(wèn)題，自底向上自底向上的計(jì)算方式以及利用的計(jì)算方式以及利用額外存儲(chǔ)空間額外存儲(chǔ)空間 3 warshall算法體現(xiàn)了算法體現(xiàn)了階段性和無(wú)后向性。階段性和無(wú)后向性。24 完全最短路徑問(wèn)題：找到從每個(gè)頂點(diǎn)到其他所有完全最短路徑問(wèn)題：找到從每個(gè)頂點(diǎn)到其他所有頂點(diǎn)之間的距離頂點(diǎn)之間的距離(最短路徑的長(zhǎng)度最短路徑的長(zhǎng)度) dcba23671 權(quán)重矩陣 0 3 2 0 7 0 1 6 0 距離矩陣 0 10 3 4 2 0 5 6 7 7 0 1

18、 6 16 9 025 Floyd算法中體現(xiàn)的動(dòng)態(tài)規(guī)劃思路：算法中體現(xiàn)的動(dòng)態(tài)規(guī)劃思路： 用一系列用一系列n階矩陣來(lái)計(jì)算一個(gè)階矩陣來(lái)計(jì)算一個(gè)n頂點(diǎn)加權(quán)圖的距離矩陣頂點(diǎn)加權(quán)圖的距離矩陣 矩陣矩陣D(k)的第的第i行第行第j列的元素列的元素dij (k)為從第為從第i個(gè)頂點(diǎn)到第個(gè)頂點(diǎn)到第j個(gè)個(gè)頂點(diǎn)之間最短路徑的長(zhǎng)度，并且路徑的每一個(gè)中間頂點(diǎn)頂點(diǎn)之間最短路徑的長(zhǎng)度，并且路徑的每一個(gè)中間頂點(diǎn)的編號(hào)不大于的編號(hào)不大于k D(0) 為權(quán)重矩陣為權(quán)重矩陣D(n)為距離矩陣為距離矩陣 （1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征 （2）遞歸地定義最優(yōu)值。）遞歸地定義最優(yōu)值。 （3

19、）以）以自底向上自底向上的方式計(jì)算出最優(yōu)值。的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。(0)(1)( )( ),., ,.,kknDDDD(0)( )(1)(1)(0)1,min,kkkijijijijikkjkdwdddd當(dāng)時(shí)26dcba23671 D(0) 0 3 2 0 7 0 1 6 0 D(1) 0 3 2 0 5 7 0 1 6 9 0 D(2) 0 3 2 0 5 9 7 0 1 6 9 0 D(3) 0 10 3 4 2 0 5 6 9 7 0 1 6 16 9 0 D(4) 0 10 3 4 2 0

20、5 6 7 7 0 1 6 16 9 027算法算法 Floyd(W1.n,1.n) / 實(shí)現(xiàn)計(jì)算完全最短路徑的實(shí)現(xiàn)計(jì)算完全最短路徑的Floyd算法算法 / 輸入：圖的權(quán)重矩陣輸入：圖的權(quán)重矩陣W / 輸出：包含最短路徑長(zhǎng)度的距離矩陣輸出：包含最短路徑長(zhǎng)度的距離矩陣 for 1 to do for 1 to do for j1 to do , min , , , + , return DWkninnD i jD i j D i kD k jD算法效率算法效率(n3)28 最優(yōu)二叉查找樹最優(yōu)二叉查找樹 前提：集合中元素的前提：集合中元素的查找概率已知查找概率已知。 它在查找中的它在查找中的平均鍵

21、值比較次數(shù)是最低平均鍵值比較次數(shù)是最低的的 例子：非最優(yōu)二叉查找樹例子：非最優(yōu)二叉查找樹 ABCDABCD29 如何定義最優(yōu)子結(jié)構(gòu)如何定義最優(yōu)子結(jié)構(gòu) 可能的最優(yōu)二叉查找樹形式可能的最優(yōu)二叉查找樹形式 其中其中Tik-1 , Tk+1j 是兩棵最優(yōu)二叉查找子樹是兩棵最優(yōu)二叉查找子樹 注意這只是注意這只是可能的最優(yōu)二叉查找樹形式，可能的最優(yōu)二叉查找樹形式， 寫出該形式下的平均比較次數(shù)寫出該形式下的平均比較次數(shù) 符合該形式的二叉樹有多少個(gè)？符合該形式的二叉樹有多少個(gè)？ K的不同取值，形成不同形式的二叉樹，共的不同取值，形成不同形式的二叉樹，共J-i+1個(gè)個(gè)注意樹的表注意樹的表示符號(hào)示符號(hào)30Ci,j

22、表示這棵樹表示這棵樹中成功查找的最小中成功查找的最小的平均查找次數(shù)的平均查找次數(shù)31 考慮用二維表記錄考慮用二維表記錄Ci,j 當(dāng)當(dāng)i在在1和和n+1之間時(shí)，之間時(shí)，Ci,i-1為多少？為多少？ 當(dāng)當(dāng)i在在1和和n之間時(shí)，之間時(shí)，Ci,i為多少？為多少？ 我們的目標(biāo)是求什么？我們的目標(biāo)是求什么？0 p1 目標(biāo) 0 p2 Ci,j pn 001jnn+11 i僅求出僅求出C1,n是否是否可以獲得最優(yōu)二叉可以獲得最優(yōu)二叉查找樹本身查找樹本身32 例：例： 鍵鍵 A B C D查找概率查找概率 0.1 0.2 0.4 0.3 初始表33 最終表 計(jì)算C1,234 為了獲得最優(yōu)二叉樹本身需要記錄什么？

23、為了獲得最優(yōu)二叉樹本身需要記錄什么？35得到最優(yōu)二叉查找樹36算法算法 OptimalBST(P1.n) / 用動(dòng)態(tài)規(guī)劃算法求最優(yōu)二叉查找樹用動(dòng)態(tài)規(guī)劃算法求最優(yōu)二叉查找樹 /輸入：一個(gè)輸入：一個(gè)n個(gè)鍵的有序列表的查找概率數(shù)組個(gè)鍵的有序列表的查找概率數(shù)組P1.n /輸出：在最優(yōu)輸出：在最優(yōu)BST中成功查找的平均比較次數(shù)，以及最優(yōu)中成功查找的平均比較次數(shù)，以及最優(yōu)BST中子樹的根中子樹的根表表R for i1 to n do Ci,i-10 Ci,iPi Ri,ii Cn+1,ni for d1 to n-1 do /對(duì)角線計(jì)數(shù)對(duì)角線計(jì)數(shù) for i1 to n-d do ji+d minval

24、for ki to j do if Ci,k-1+Ck+1,j minval minvalCi,k-1+Ck+1,j;kmink Ri,ik sumPi; for si+1 to j do sumsum+Ps Ci,iminval + sum Return C1,n,R算法效率算法效率(n2)37 背包問(wèn)題：給定背包問(wèn)題：給定n個(gè)重量為個(gè)重量為w1，.wn、價(jià)值為、價(jià)值為v1,vn的物品和一個(gè)承重量為的物品和一個(gè)承重量為W的背包，求的背包，求這些物品中這些物品中最有價(jià)值最有價(jià)值的一個(gè)子集，并且要能夠裝的一個(gè)子集，并且要能夠裝到背包中到背包中 38 思考其階段性和最優(yōu)子結(jié)構(gòu)思考其階段性和最優(yōu)子結(jié)

25、構(gòu) 考慮一個(gè)由考慮一個(gè)由前前i個(gè)物品個(gè)物品(1in)定義的實(shí)例，物品的重量分別為定義的實(shí)例，物品的重量分別為w1,wi、價(jià)值分別為、價(jià)值分別為v1，vi，背包的承重量為，背包的承重量為j (1jW)。設(shè)設(shè)Vi,j為該實(shí)例的最優(yōu)解的物品總價(jià)值為該實(shí)例的最優(yōu)解的物品總價(jià)值 分成兩類子集：分成兩類子集： 在不包括第在不包括第i個(gè)物品的子集個(gè)物品的子集中，最優(yōu)子集的價(jià)值是中，最優(yōu)子集的價(jià)值是Vi-1,j 在包括第在包括第i個(gè)物品的子集中個(gè)物品的子集中(因此，因此，jwi 0)，最優(yōu)子集是由該，最優(yōu)子集是由該物品和前物品和前i-1個(gè)物品中能夠放進(jìn)承重量為個(gè)物品中能夠放進(jìn)承重量為 j wi的背包的最優(yōu)的背

26、包的最優(yōu)子集組成。這種最優(yōu)子集的總價(jià)值等于子集組成。這種最優(yōu)子集的總價(jià)值等于vi+Vi-1,j-wi max 1, ,1,0 , 1, , 000, 0;0 ,00iiiiV ij vV ijwjwV i jV ijjwjVjiV i初始條件：當(dāng)時(shí)，當(dāng)時(shí)，39 考慮用二維數(shù)組記錄考慮用二維數(shù)組記錄Vi,j 則問(wèn)題求解的目標(biāo)是要求出什么值？則問(wèn)題求解的目標(biāo)是要求出什么值？40 n=3 w=30,20,10 v=120, 100,60 c=50 動(dòng)態(tài)規(guī)劃解動(dòng)態(tài)規(guī)劃解0-1背包：背包：V(i，j)是背包容量為是背包容量為j，可，可選擇物品為選擇物品為1, 2,i時(shí)的最優(yōu)值時(shí)的最優(yōu)值V(3,50)V(2,50)V(2,40)+60V(1,50)V(1,30)+100V(1,40)+60V(1,20)+60+10041 作業(yè)：作業(yè)： 用動(dòng)態(tài)規(guī)劃法解決用動(dòng)態(tài)規(guī)劃法解決n個(gè)矩陣的連乘的結(jié)合順序問(wèn)題。個(gè)矩陣的連乘的結(jié)合順序問(wèn)題。因?yàn)槠渲袃蓚€(gè)相鄰的矩陣，前者的列數(shù)與后者行因?yàn)槠渲袃蓚€(gè)相鄰的矩陣，