第3章_動態(tài)規(guī)劃_作業(yè)-322 (1)

1、課后練習課后練習練習練習1：已知一組連乘矩陣已知一組連乘矩陣A1A2A3A4A5的行列的行列數(shù)如下面數(shù)如下面p向量所示：向量所示：1. 如使用函數(shù)如使用函數(shù)直接遞歸調(diào)用直接遞歸調(diào)用（窮舉法）的形式（窮舉法）的形式求解，則是無效算法，請畫出函數(shù)遞歸調(diào)用求解，則是無效算法，請畫出函數(shù)遞歸調(diào)用的遞歸樹樹形，并說明有哪些子問題被重復的遞歸樹樹形，并說明有哪些子問題被重復計算。計算。2. 請用請用動態(tài)規(guī)劃法動態(tài)規(guī)劃法求解最優(yōu)計算順序，寫出計求解最優(yōu)計算順序，寫出計算過程以及加括號的計算順序表達式。算過程以及加括號的計算順序表達式。p = (5, 3, 9, 2, 2, 4)A1A2A3A4A5 p =

2、(5, 3, 9, 2, 2, 4) 函數(shù)遞歸調(diào)用的遞歸樹樹形函數(shù)遞歸調(diào)用的遞歸樹樹形1:51:12:51:23:51:34:51:45:52:23:52:45:51:12:23:34:53:45:5 用用動態(tài)規(guī)劃法動態(tài)規(guī)劃法求解最優(yōu)計算順序，寫出計算過程求解最優(yōu)計算順序，寫出計算過程以及加括號的計算順序表達式。以及加括號的計算順序表達式。A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4)55M矩陣矩陣55S矩陣矩陣00000123451. 計算計算mi,i+1 (i=1, 2, 3, 4)： （矩陣鏈長度為（矩陣鏈長度為2）m12 = min 1k2 m11+m22+p0p1

3、p2 = 135m23 = min 2k3 m22+m33+p1p2p3 = 54m34 = min 3k4 m33+m44+p2p3p4 = 36m45 = min 4k5 m44+m55+p3p4p5 = 161355436161234A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4)55M矩陣矩陣55S矩陣矩陣000001234513554361612342. 計算計算mi,i+2 (i=1, 2, 3)： （矩陣鏈長度為（矩陣鏈長度為3）m13 = min 1k2 m11+m23+p0p1p3, m12+m33+p0p2p3 = min84, 225 = 84m24 =

4、 min 2k4 m22+m34+p1p2p4, m23+m44+p1p3p4 = min90, 66 = 66m35 = min 3k5 m33+m45+p2p3p5, m34+m55+p2p4p5 = min88, 90 = 88846688133A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4)55M矩陣矩陣55S矩陣矩陣000001234513554361612348466881333. 計算計算mi,i+3 (i=1, 2)： （矩陣鏈長度為（矩陣鏈長度為3）m14 = min 1k4 m11 + m24 + p0p1p4, m12 + m34 + p0p2p4, m

5、13 + m44 + p0p3p4 = 96, 261, 104 = 96961A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4)55M矩陣矩陣55S矩陣矩陣000001234513554361612348466881333. 計算計算mi,i+3 (i=1, 2)： （矩陣鏈長度為（矩陣鏈長度為3）m25 = min 2k5 m22 + m35 + p1p2p5, m23 + m45 + p1p3p5, m24 + m55 + p1p4p5 = 196, 94, 90 = 90961904A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4)55M矩陣矩陣55S矩

6、陣矩陣000001234513554361612348466881339619044. 計算計算mi,i+4 (i=1)： （矩陣鏈長度為（矩陣鏈長度為4）m15 = min 1k5 m11 + m25 + p0p1p5, m12 + m35 + p0p2p5, m13 + m45 + p0p3p5, m14 + m55 + p0p4p5 = 150, 403, 212, 136 = 136完成后通過完成后通過S矩陣得出最矩陣得出最優(yōu)完全加括優(yōu)完全加括號方式為：號方式為：( ( A1 ( A2 ( A3 A4 ) ) ) A5 )1364課后練習課后練習練習練習2：假定有假定有6個鍵值，個鍵值

7、，k1、k2、k3、k4、k5、k6，其中，其中k1k2k3k4k5k6。它們被搜索的概。它們被搜索的概率分別為率分別為 0.24，0.18，0.09，0.13，0.3，0.06，請使用動態(tài)規(guī)劃算法求一顆最優(yōu)二叉搜索樹，請使用動態(tài)規(guī)劃算法求一顆最優(yōu)二叉搜索樹，要求：要求：1. 給出該樹的平均查找長度；給出該樹的平均查找長度；2. 畫出樹形。畫出樹形。k1k2k3k4k5k6, 0.24, 0.18, 0.09, 0.13, 0.3, 0.06C(i, i-1)=0 (1in+1) 式式1C(i, i)=pi (1in) 式式2C(i, j)=minC(i, k-1)+C(k+1, j)+w(i

8、,j) (1ijn, ikj) =minC(i, k-1)+C(k+1, j)+w(i,j) (1ijn, ikj) 式式30123456123456701234561234567二維表二維表C二維表二維表R0000000.240.180.090.130.300.06123456C(i, i-1)=0 (1in+1) 式式1C(i, i)=pi (1in) 式式2C(i, j)=minC(i, k-1)+C(k+1, j)+w(i,j) (1ijn, ikj) =minC(i, k-1)+C(k+1, j)+w(i,j) (1ijn, ikj) 式式3564175432632105641754

9、3263210二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234566 . 066. 042. 0024. 0)2 , 3()1 , 1(:26 . 042. 018. 00)2 , 2()0 , 1(:1min)2 , 1(2121 sssspCCkpCCkC0.61C(i, i-1)=0 (1in+1) 式式1C(i, i)=pi (1in) 式式2C(i, j)=minC(i, k-1)+C(k+1, j)+w(i,j) (1ijn, ikj) =minC(i, k-1)+C(k+1, j)+w(i,j) (1ijn, ikj) 式式3564

10、1754326321056417543263210二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.6136. 045. 027. 0018. 0)3 , 4()2 , 2(:336. 027. 009. 00)3 , 3()1 , 2(:2min)3 , 2(3232 sssspCCkpCCkC0.3625641754326321056417543263210二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.610.36231. 031. 022. 0009. 0)4 , 5()3 ,

11、 3(:435. 022. 013. 00)4 , 4()2 , 3(:3min)4 , 3(4343 sssspCCkpCCkC56. 056. 043. 0013. 0)5 , 6()4 , 4(:573. 043. 03 . 00)5 , 5()3 , 4(:4min)5 , 4(5454 sssspCCkpCCkC42. 066. 036. 003 . 0)6 , 7()5 , 5(:642. 036. 006. 00)6 , 6()4 , 5(:5min)6 , 5(6565 sssspCCkpCCkC0.3140.5650.42556417543263210564175432632

12、10二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.42584. 011. 151. 006 . 0)3 , 4()2 , 1(384. 051. 009. 024. 0)3 , 3()1 , 1(287. 051. 036. 00)3 , 2()0 , 1(1min)3 , 1(313131 sssssspCCkpCCkpCCkC0.842以此類推以此類推可以把可以把C(2,4)、C(3,5)、C(4,6)、C(5,7)計算出來計算出來0.7130.8350.68556417543263210564

13維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.42537. 148. 164. 0084. 0)4 , 5()3 , 1(437. 164. 013. 06 . 0)4 , 4()2 , 1(319. 164. 031. 024. 0)4 , 3()1 , 1(235. 164. 071. 00)4 , 2()0 , 1(1min)4 , 1(41414141 sssssssspCCkpCCkpCCkpCCkC0.842以此類推以此類推可以把可以把C(2,5)、C(3,6)計算

14、出來計算出來0.7130.8350.6851.3731.0940.9555641754326321056417543263210二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.42501. 231. 294. 0037. 1)5 , 6()4 , 1(508. 294. 03 . 084. 0)5 , 5()3 , 1(41 . 294. 056. 06 . 0)5 , 4()2 , 1(301. 294. 083. 024. 0)5 , 3()1 , 1(203. 294. 009. 10)5 ,

15、2()0 , 1(1min)5 , 1(5151515151 sssssssssspCCkpCCkpCCkpCCkpCCkC0.842以此類以此類推推可可以把以把C(2,6)計算出來計算出來0.7130.8350.6851.3731.0940.9552.0121.5355641754326321056417543263210二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.42519.201.31001.2)6 ,7()5 , 1(643.2106.037.1)6 ,6()4 , 1(526.2142.

16、084.0)6 ,5()3, 1(428.2168.06 .0)6 ,4()2, 1(319.2195.024.0)6 ,3()1 , 1(253.2153.10)6 ,2()0 , 1(1min)6 , 1(616161616161 sssssssssssspCCkpCCkpCCkpCCkpCCkpCCkC0.842最優(yōu)值：最優(yōu)值：2.19即最優(yōu)二叉即最優(yōu)二叉搜索樹的平搜索樹的平均查找長度均查找長度（ASL）為）為2.190.7130.8350.6851.3731.0940.9552.0121.5352.192 則由兩個矩陣值得到則由兩個矩陣值得到最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹樹形為：樹形為：

17、5641754326321056417543263210二維表二維表C二維表二維表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.4250.8420.7130.8350.6851.3731.0940.9552.0121.5352.192 左圖中的樹形符合二叉搜索樹的定義。左圖中的樹形符合二叉搜索樹的定義。 該樹的平均查找長度為該樹的平均查找長度為2.19 該樹樹形是所有具有下方該樹樹形是所有具有下方6個節(jié)點值個節(jié)點值的二叉搜索樹中的二叉搜索樹中平均查找長度最短的，平均查找長度最短的，所以是最優(yōu)所以是最優(yōu)。k1k2k3k4k5k

18、6, 0.24, 0.18, 0.09, 0.13, 0.3, 0.06k2k1k5k4k3k6課后練習課后練習 練習練習3：假如你正在管理假如你正在管理SD紀念館公路的廣告牌紀念館公路的廣告牌的建設，這條路從西到東的建設，這條路從西到東M英里，是一段旅行量英里，是一段旅行量大的路程。廣告牌的可能的地點用數(shù)字大的路程。廣告牌的可能的地點用數(shù)字x1, x2, ., xn給出，每個均處在區(qū)間給出，每個均處在區(qū)間0, M中（沿這條公路中（沿這條公路規(guī)定它們的地點，從路地西端用英里量度）。如規(guī)定它們的地點，從路地西端用英里量度）。如果你放一塊廣告牌在地點果你放一塊廣告牌在地點xi，你就得到，你就得到r

19、i0的收的收益。益。課后練習課后練習 國家公路局得征稅規(guī)定要求兩塊廣告牌相對不國家公路局得征稅規(guī)定要求兩塊廣告牌相對不能位于小于或等于能位于小于或等于5英里之內(nèi)。你需要找一組英里之內(nèi)。你需要找一組地點來放置廣告牌以使得你的總收益在這個限地點來放置廣告牌以使得你的總收益在這個限制下達到最大。制下達到最大。 例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5, 6, 5, 1 例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5, 6, 5, 1 問

20、題的問題的最優(yōu)子結構性質(zhì)最優(yōu)子結構性質(zhì)： x1, x2, , xn 的的最優(yōu)解一定包含最優(yōu)解一定包含 x1, x2, , xn-1 的最優(yōu)解，的最優(yōu)解，該結論可以用該結論可以用反證法反證法證明。證明。 最優(yōu)解最優(yōu)解為：為：n個地點放置兩個廣告牌的方案，個地點放置兩個廣告牌的方案，同時使總收益最大。同時使總收益最大。 最優(yōu)值最優(yōu)值設計為：總收益。設計為：總收益。 解題思路：解題思路：考慮對于給定輸入實例的一個最優(yōu)解，在考慮對于給定輸入實例的一個最優(yōu)解，在地點地點xn或者放廣告牌，或者不放?；蛘叻艔V告牌，或者不放。 如果不放，那么在地點如果不放，那么在地點x1, x2, , xn上的最優(yōu)解實上的最

21、優(yōu)解實際上與在地點際上與在地點x1, x2, , xn-1上的最優(yōu)解一樣。上的最優(yōu)解一樣。 如果放，那么應該去掉如果放，那么應該去掉xn以及與它在以及與它在5英里之內(nèi)的所英里之內(nèi)的所有其他地點，并且找在剩下地點上的最優(yōu)解。有其他地點，并且找在剩下地點上的最優(yōu)解。 當考察僅前當考察僅前j個地點個地點x1, x2, , xj所定義的問題時，所定義的問題時，同樣的推理也適用：同樣的推理也適用：在最優(yōu)解中包含或不包含在最優(yōu)解中包含或不包含xj ，具有同樣的結果具有同樣的結果。例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5, 6, 5, 1 令令e(j)表示編號比表示編號比j小且距小且距xj大于大于5英里的最東邊的英里的最東邊的地點地點xi。 因為地點是因為地點是從西到東從西到東編號的，一旦選擇在編號的，一旦選擇在xj放放一塊廣告牌，地點一塊廣告牌，地點x1, x2, , xe(j)仍舊是有效仍舊是有效的選