第8章 動(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)題滿(mǎn)一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問(wèn)題滿(mǎn)足最優(yōu)化原理又稱(chēng)其具有最優(yōu)子結(jié)構(gòu)性質(zhì)足最優(yōu)化原理又稱(chēng)其具有

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ì)算 若路線(xiàn)若路線(xiàn)I I和和J J是是A A到到C C的最優(yōu)路徑，則的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線(xiàn)根據(jù)最優(yōu)化原理，路線(xiàn)J J必是從必是從B B到到C C的最優(yōu)路線(xiàn)。的最優(yōu)路線(xiàn)。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)。換句話(huà)說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。換句話(huà)說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱(chēng)為無(wú)后效性。這就是無(wú)后向性，又稱(chēng)為無(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ì)，并刻畫(huà)其結(jié)構(gòu)特征。）找出最優(yōu)解的

5、性質(zhì)，并刻畫(huà)其結(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)題 但是書(shū)中但是書(shū)中 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)二叉查找樹(shù)最優(yōu)二叉查找樹(shù) 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é)果記錄在表中。8910 二項(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

7、(n-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 b11 動(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列列12 算法算法 Binomial(n,k) /用動(dòng)態(tài)規(guī)劃算法計(jì)算用動(dòng)態(tài)規(guī)劃算法計(jì)算C(n,k) /輸入：輸

8、入：對(duì)非負(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 13 時(shí)間效率分析時(shí)間效率分析 基本操作：加法基本操作：加法14 Warshall 算法用于計(jì)算有向圖傳遞閉包算法用于計(jì)算有向圖傳遞閉包 Floyd算法用于計(jì)算全部最短路徑算法用于計(jì)算全部最短路徑15 傳遞閉包定義傳遞閉包定義: 一個(gè)一個(gè)n頂點(diǎn)有向圖的傳遞閉包可頂點(diǎn)有向圖的傳遞閉包可以定義為一個(gè)以定義為一個(gè)n階布爾矩陣階布爾矩陣T

9、=tij，如果從第如果從第i個(gè)個(gè)頂點(diǎn)到第頂點(diǎn)到第j個(gè)頂點(diǎn)之間存在一條有效的有向路徑個(gè)頂點(diǎn)之間存在一條有效的有向路徑，矩陣第矩陣第i行行(1in)第第j列列(1jn)的元素為的元素為1；否則，；否則，tij為為 0換言之：對(duì)給定的有向圖，換言之：對(duì)給定的有向圖， 求出每個(gè)點(diǎn)能到達(dá)的所有點(diǎn)求出每個(gè)點(diǎn)能到達(dá)的所有點(diǎn)16dcba鄰接矩陣鄰接矩陣 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 1對(duì)給定的有向圖，對(duì)給定的有向圖， 求出每個(gè)點(diǎn)能到達(dá)的所有點(diǎn)求出每個(gè)點(diǎn)能

10、到達(dá)的所有點(diǎn)17 求傳遞閉包是圖論中一個(gè)非常重要的問(wèn)題，例如求傳遞閉包是圖論中一個(gè)非常重要的問(wèn)題，例如給定了一個(gè)城市的交通地圖，可利用求傳遞閉包給定了一個(gè)城市的交通地圖，可利用求傳遞閉包的方法獲知任意兩個(gè)地點(diǎn)之間是否有路相連通。的方法獲知任意兩個(gè)地點(diǎn)之間是否有路相連通。 用深度優(yōu)先查找和廣度優(yōu)先查找如何生成傳遞閉用深度優(yōu)先查找和廣度優(yōu)先查找如何生成傳遞閉包？包？18 動(dòng)態(tài)規(guī)劃求解思路動(dòng)態(tài)規(guī)劃求解思路 動(dòng)態(tài)規(guī)劃將問(wèn)題分段，動(dòng)態(tài)規(guī)劃將問(wèn)題分段，Warshall算法是通過(guò)一算法是通過(guò)一系列系列n階矩陣階矩陣R（k）來(lái)構(gòu)造最終階段來(lái)構(gòu)造最終階段n階傳遞閉包階傳遞閉包矩陣矩陣R（n）, k =0, 1,

11、 ,n-1.19R（k）由它的前趨由它的前趨 R（k-1）計(jì)算得到（分級(jí)推進(jìn)計(jì)算）計(jì)算得到（分級(jí)推進(jìn)計(jì)算） 允許路徑中包含前允許路徑中包含前k個(gè)頂點(diǎn)作為中間頂點(diǎn)個(gè)頂點(diǎn)作為中間頂點(diǎn) R（0） 該矩陣不允許它的路徑中包含任何中間該矩陣不允許它的路徑中包含任何中間頂點(diǎn)，即從該矩陣的任意頂點(diǎn)出發(fā)的路徑不含有中頂點(diǎn)，即從該矩陣的任意頂點(diǎn)出發(fā)的路徑不含有中間頂點(diǎn)，此即間頂點(diǎn)，此即鄰接矩陣鄰接矩陣。 R（1） 允許路徑中包含第允許路徑中包含第1個(gè)頂點(diǎn)作為中間頂個(gè)頂點(diǎn)作為中間頂點(diǎn)。點(diǎn)。20 R（2） 允許路徑中包含前允許路徑中包含前2個(gè)頂點(diǎn)作為中間頂點(diǎn)個(gè)頂點(diǎn)作為中間頂點(diǎn)。 . R（k） 允許路徑中包含前允許路

12、徑中包含前k個(gè)頂點(diǎn)作為中間頂點(diǎn)個(gè)頂點(diǎn)作為中間頂點(diǎn)。 R（n） 允許路徑中包含全部允許路徑中包含全部 n 個(gè)頂點(diǎn)作為中間個(gè)頂點(diǎn)作為中間頂點(diǎn)。頂點(diǎn)。 每個(gè)后繼矩陣每個(gè)后繼矩陣 R（k）對(duì)其前趨對(duì)其前趨 R（k-1） 來(lái)說(shuō)，在路徑來(lái)說(shuō)，在路徑上允許增加一個(gè)頂點(diǎn)，上允許增加一個(gè)頂點(diǎn)， 因此有可能包含更多的因此有可能包含更多的1（增加前為增加前為1的在增加后依然為的在增加后依然為1）。）。21用與或式可以直接寫(xiě)成下式：用與或式可以直接寫(xiě)成下式：不包含第不包含第k個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn) 包含第包含第k個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)22 WARSHALL算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(n3)。23 算法思想說(shuō)明算法思想說(shuō)明 搭

13、橋找路徑搭橋找路徑 選取一個(gè)頂點(diǎn)作為橋梁，考察所有頂點(diǎn)，是否選取一個(gè)頂點(diǎn)作為橋梁，考察所有頂點(diǎn)，是否可以通過(guò)橋梁到達(dá)其它的頂點(diǎn)?？梢酝ㄟ^(guò)橋梁到達(dá)其它的頂點(diǎn)。 用用i控制依次選擇各頂點(diǎn)做橋梁?？刂埔来芜x擇各頂點(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)。24 外循環(huán)第一次，選擇外循環(huán)第一次，選擇0作為橋梁作為橋梁 考察考察0是否可以通過(guò)是否可以通過(guò)0到達(dá)其它頂點(diǎn)到達(dá)其它頂點(diǎn) 1 0 1 0 0 1 考察

14、考察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控制控制用用j控制控制用用k控制控制25 外循環(huán)第二次，增加外循環(huán)第二次，增加1為橋梁為橋梁 考察考察0是否可以通過(guò)是否可以通過(guò)1

15、到達(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 15 0 0 0 0 1 1123405可看成是動(dòng)態(tài)可看成是動(dòng)態(tài)規(guī)劃的階段性，規(guī)劃的階段性，意味著可以通意味著可以通過(guò)過(guò)0

16、，1。即當(dāng)。即當(dāng)前是否有路徑前是否有路徑可以建立在可以建立在前前一階段一階段的路徑的路徑基礎(chǔ)上?；A(chǔ)上。26 循環(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ò)選擇的橋梁建立到其它頂點(diǎn)的路徑，因此不必考察它通過(guò)該橋梁是其它頂點(diǎn)的路徑，因此不必考察它通過(guò)該橋梁是否可以到達(dá)其它頂點(diǎn)，即內(nèi)循環(huán)不用做。否可以到

17、達(dá)其它頂點(diǎn)，即內(nèi)循環(huán)不用做。27 完全最短路徑問(wèn)題：完全最短路徑問(wèn)題： 找到從每個(gè)頂點(diǎn)到其他所有頂點(diǎn)之間的距離找到從每個(gè)頂點(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 6 16 9 028 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è)頂點(diǎn)之間

18、最短路徑的長(zhǎng)度，個(gè)頂點(diǎn)之間最短路徑的長(zhǎng)度，并且路徑的每一并且路徑的每一個(gè)中間頂點(diǎn)的編號(hào)不大于個(gè)中間頂點(diǎn)的編號(hào)不大于k (0)(1)( )( ),., ,.,kknDDDD29 D(0) 為權(quán)重矩陣為權(quán)重矩陣D(n)為距離矩陣為距離矩陣 （1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征 （2）并遞歸地定義最優(yōu)值。）并遞歸地定義最優(yōu)值。(0)( )(1)(1)(0)1,min,kkkijijijijikkjkdwdddd當(dāng)時(shí)不包含第不包含第k個(gè)節(jié)點(diǎn)：個(gè)節(jié)點(diǎn)： dij (k-1) 包含第包含第k個(gè)節(jié)點(diǎn)：個(gè)節(jié)點(diǎn)： dik (k-1) + dkj (k-1)k-130注：注：

19、從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能， Case 1. 直接從i到j(luò)， Case 2. 從i 經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)k 到j(luò)。 我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis(i,k) + Dis(k,j) Dis(i,j)是否成立， 如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)， 這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。31 （3）以）以自底向上自底向上的方式計(jì)算出最優(yōu)值。的方式計(jì)算出最優(yōu)值。 （4）根據(jù)計(jì)算最優(yōu)值時(shí)得

20、到的信息，構(gòu)造一個(gè)最優(yōu)解。）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。32dcba23671 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 5 6 7 7 0 1 6 16 9 033算法算法 Floyd(W1.n,1.n) / 實(shí)現(xiàn)計(jì)算完全最短路徑的實(shí)現(xiàn)計(jì)算完全最短路徑的Floyd算法算法 / 輸入：圖的權(quán)重矩陣輸入：圖的權(quán)重矩陣W / 輸出：包含最短路徑長(zhǎng)度的距離矩

21、陣輸出：包含最短路徑長(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)34問(wèn)題描述問(wèn)題描述 給定給定n個(gè)鍵個(gè)鍵a1, a2, a3, ., an,其相應(yīng)的查其相應(yīng)的查找概率為找概率為p1, p2, p3, ., pn。構(gòu)成最優(yōu)。構(gòu)成最優(yōu)BST,表示為表示為T(mén)1n ，求這棵樹(shù)的，求這棵樹(shù)的平均查找次數(shù)平均查找次數(shù)C1, n（耗費(fèi)最低（耗費(fèi)最低)。 換言之，如何構(gòu)造這棵最優(yōu)換言之，如何構(gòu)造這棵最優(yōu)BST，使得，使得C1, n 最小。

22、最小。35 它在查找中的它在查找中的平均比較次數(shù)是最低平均比較次數(shù)是最低的的 平均比較次數(shù)的計(jì)算：所有節(jié)點(diǎn)上平均比較次數(shù)的計(jì)算：所有節(jié)點(diǎn)上 概率與比較次數(shù)的乘積之和概率與比較次數(shù)的乘積之和 例子：非最優(yōu)二叉查找樹(shù)例子：非最優(yōu)二叉查找樹(shù) ABCDABCD36 動(dòng)態(tài)規(guī)劃法策略是將問(wèn)題分成多個(gè)階段，逐段推動(dòng)態(tài)規(guī)劃法策略是將問(wèn)題分成多個(gè)階段，逐段推進(jìn)計(jì)算，后繼實(shí)例解由其直接前趨實(shí)例解計(jì)算得進(jìn)計(jì)算，后繼實(shí)例解由其直接前趨實(shí)例解計(jì)算得到。到。 對(duì)于最優(yōu)對(duì)于最優(yōu)BST問(wèn)題，利用減一技術(shù)和最優(yōu)性原則，問(wèn)題，利用減一技術(shù)和最優(yōu)性原則，如果前如果前n-1個(gè)節(jié)點(diǎn)構(gòu)成最優(yōu)個(gè)節(jié)點(diǎn)構(gòu)成最優(yōu)BST，加入一個(gè)節(jié)點(diǎn)，加入一個(gè)節(jié)

23、點(diǎn)an 后要求構(gòu)成規(guī)模后要求構(gòu)成規(guī)模n的最優(yōu)的最優(yōu)BST。 按按 n-1, n-2 , . , 2, 1 遞歸，問(wèn)題可解。自底向上遞歸，問(wèn)題可解。自底向上計(jì)算：計(jì)算：C1, 2C1, 3 . C1, n。37 用用Ci, j 表示由表示由a1, a2, ., an構(gòu)成的構(gòu)成的BST的耗費(fèi)的耗費(fèi)。其中。其中1i j n。這棵樹(shù)表示為。這棵樹(shù)表示為T(mén)ij。 從中選擇一個(gè)鍵從中選擇一個(gè)鍵ak作根節(jié)點(diǎn)，它的左子樹(shù)為作根節(jié)點(diǎn)，它的左子樹(shù)為T(mén)i, k-1，右子樹(shù)為，右子樹(shù)為T(mén)k+1,j。要求選擇的。要求選擇的k 使得整棵樹(shù)的平均使得整棵樹(shù)的平均查找次數(shù)查找次數(shù)Ci, j最小。最小。 左右子樹(shù)遞歸執(zhí)行此過(guò)程

24、。（根的生成過(guò)程）左右子樹(shù)遞歸執(zhí)行此過(guò)程。（根的生成過(guò)程）3839 可能的最優(yōu)二叉查找樹(shù)形式可能的最優(yōu)二叉查找樹(shù)形式 其中其中Ti, k-1 , Tk+1, j 是兩棵最優(yōu)二叉查找子樹(shù)是兩棵最優(yōu)二叉查找子樹(shù) 注意這只是注意這只是可能的最優(yōu)二叉查找樹(shù)形式，可能的最優(yōu)二叉查找樹(shù)形式，注意樹(shù)的表注意樹(shù)的表示符號(hào)示符號(hào)40Ci,j表示這棵樹(shù)表示這棵樹(shù)中成功查找的最小中成功查找的最小的平均查找次數(shù)的平均查找次數(shù)41 考慮用二維表記錄考慮用二維表記錄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)是求什么？

25、我們的目標(biāo)是求什么？0 p1 目標(biāo) 0 p2 Ci,j pn 001jnn+11 i僅求出僅求出C1,n是否是否可以獲得最優(yōu)二叉可以獲得最優(yōu)二叉查找樹(shù)本身查找樹(shù)本身42 例：例： 鍵鍵 A B C D查找概率查找概率 0.1 0.2 0.4 0.3 初始表43 最終表 計(jì)算C1,244 為了獲得最優(yōu)二叉樹(shù)本身需要記錄什么？為了獲得最優(yōu)二叉樹(shù)本身需要記錄什么？45得到最優(yōu)二叉查找樹(shù)46算法算法 OptimalBST(P1.n) / 用動(dòng)態(tài)規(guī)劃算法求最優(yōu)二叉查找樹(shù)用動(dòng)態(tài)規(guī)劃算法求最優(yōu)二叉查找樹(shù) /輸入：一個(gè)輸入：一個(gè)n個(gè)鍵的有序列表的查找概率數(shù)組個(gè)鍵的有序列表的查找概率數(shù)組P1.n /輸出：在最優(yōu)

26、輸出：在最優(yōu)BST中成功查找的平均比較次數(shù)，以及最優(yōu)中成功查找的平均比較次數(shù)，以及最優(yōu)BST中子樹(shù)的根中子樹(shù)的根表表R for i1 to n do Ci,i-10 Ci,iPi Ri,ii Cn+1,ni for d1 to n-1 do /對(duì)角線(xiàn)計(jì)數(shù)對(duì)角線(xiàn)計(jì)數(shù) for i1 to n-d do ji+d minval for ki to j do if Ci,k-1+Ck+1,j w. Item k cant be part of the solution, since if it was, the total weight would be w, which is unacceptabl

27、e Second case: wk =w. Then the item k can be in the solution, and we choose the case with greater valueelse , 1, 1max if , 1,kkkbwwkBwkBwwwkBwkB3/1/2022for w = 0 to WB0,w = 0for i = 0 to nBi,0 = 0for w = 0 to Wif wi Bi-1,wBi,w = bi + Bi-1,w- wielseBi,w = Bi-1,welse Bi,w = Bi-1,w / wi w 3/1/2022for w

28、 = 0 to WB0,w = 0for i = 0 to nBi,0 = 0for w = 0 to W算法運(yùn)行時(shí)間O(W)O(W)Repeat n timesO(n*W)蠻力法：蠻力法：O(2n)3/1/2022583/1/202259for w = 0 to WB0,w = 0000000W012345i01234n = 4 ( 4個(gè)物品)W = 5 (最大容量)物品 (重量， 收益):(2,3), (3,4), (4,5), (5,6)3/1/202260for i = 0 to nBi,0 = 0000000W012345i0123000043/1/202261 if wi Bi-1

29、,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=1w-wi =-1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)403/1/202262 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=2w-wi =0Items:1:

30、(2,3)2: (3,4)3: (4,5) 4: (5,6)4033/1/202263 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=3w-wi=1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)40333/1/202264 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi

31、w 000000W012345i01230000i=1bi=3wi=2w=4w-wi=2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)403333/1/202265 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=1bi=3wi=2w=5w-wi=2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)4033333/1/202266 if wi Bi-1,w Bi,w = bi

32、 + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=1w-wi=-2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)40333303/1/202267 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=2w-wi=-1Items:1: (2,3)2:

33、(3,4)3: (4,5) 4: (5,6)403333033/1/202268 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=3w-wi=0Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)4033330343/1/202269 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / w

34、i w 000000W012345i01230000i=2bi=4wi=3w=4w-wi=1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)40333303443/1/202270 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=2bi=4wi=3w=5w-wi=2Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)403333034473/1/202271 if wi Bi-1

35、,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=1.3Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)4033330 034470343/1/202272 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=4w- wi=0I

36、tems:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)400 03447034533333/1/202273 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=5w- wi=1Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)400 034470345733333/1/202274 if wi Bi-1,w Bi,w = bi + Bi-1,w- wi else Bi,w = Bi-1,w else Bi,w = Bi-1,w / wi w 000000W012345i01230000i=3bi=5wi=4w=1.4Items:1: (2,3)2: (3,4)3: (4,5) 4: (5,6)400 0344703457034533333/1/202275 if wi Bi-