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

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

2、(5, 3, 9, 2, 2, 4) 函數(shù)遞歸調(diào)用的遞歸樹(shù)樹(shù)形函數(shù)遞歸調(diào)用的遞歸樹(shù)樹(shù)形1:51:12:51:23:51:34:51:45:52:23:52:45:51:12:23:34:53:45:5 用用動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法求解最優(yōu)計(jì)算順序，寫(xiě)出計(jì)算過(guò)程求解最優(yōu)計(jì)算順序，寫(xiě)出計(jì)算過(guò)程以及加括號(hào)的計(jì)算順序表達(dá)式。以及加括號(hào)的計(jì)算順序表達(dá)式。A1A2A3A4A5 p = (5, 3, 9, 2, 2, 4)55M矩陣矩陣55S矩陣矩陣00000123451. 計(jì)算計(jì)算mi,i+1 (i=1, 2, 3, 4)： （矩陣鏈長(zhǎng)度為（矩陣鏈長(zhǎng)度為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. 計(jì)算計(jì)算mi,i+2 (i=1, 2, 3)： （矩陣鏈長(zhǎng)度為（矩陣鏈長(zhǎng)度為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. 計(jì)算計(jì)算mi,i+3 (i=1, 2)： （矩陣鏈長(zhǎng)度為（矩陣鏈長(zhǎng)度為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. 計(jì)算計(jì)算mi,i+3 (i=1, 2)： （矩陣鏈長(zhǎng)度為（矩陣鏈長(zhǎng)度為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. 計(jì)算計(jì)算mi,i+4 (i=1)： （矩陣鏈長(zhǎng)度為（矩陣鏈長(zhǎng)度為4）m15 = min 1k5 m11 + m25 + p0p1p5, m12 + m35 + p0p2p5, m13 + m45 + p0p3p5, m14 + m55 + p0p4p5 = 150, 403, 212, 136 = 136完成后通過(guò)完成后通過(guò)S矩陣得出最矩陣得出最優(yōu)完全加括優(yōu)完全加括號(hào)方式為：號(hào)方式為：( ( A1 ( A2 ( A3 A4 ) ) ) A5 )1364課后練習(xí)課后練習(xí)練習(xí)練習(xí)2：假定有假定有6個(gè)鍵值，個(gè)鍵值

7、，k1、k2、k3、k4、k5、k6，其中，其中k1k2k3k4k5k6。它們被搜索的概。它們被搜索的概率分別為率分別為 0.24，0.18，0.09，0.13，0.3，0.06，請(qǐng)使用動(dòng)態(tài)規(guī)劃算法求一顆最優(yōu)二叉搜索樹(shù)，請(qǐng)使用動(dòng)態(tài)規(guī)劃算法求一顆最優(yōu)二叉搜索樹(shù)，要求：要求：1. 給出該樹(shù)的平均查找長(zhǎng)度；給出該樹(shù)的平均查找長(zhǎng)度；2. 畫(huà)出樹(shù)形。畫(huà)出樹(shù)形。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)計(jì)算出來(lái)計(jì)算出來(lái)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)計(jì)算

14、出來(lái)計(jì)算出來(lái)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)計(jì)算出來(lái)計(jì)算出來(lái)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)二叉搜索樹(shù)的平搜索樹(shù)的平均查找長(zhǎng)度均查找長(zhǎng)度（ASL）為）為2.190.7130.8350.6851.3731.0940.9552.0121.5352.192 則由兩個(gè)矩陣值得到則由兩個(gè)矩陣值得到最優(yōu)二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)樹(shù)形為：樹(shù)形為：

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 左圖中的樹(shù)形符合二叉搜索樹(shù)的定義。左圖中的樹(shù)形符合二叉搜索樹(shù)的定義。 該樹(shù)的平均查找長(zhǎng)度為該樹(shù)的平均查找長(zhǎng)度為2.19 該樹(shù)樹(shù)形是所有具有下方該樹(shù)樹(shù)形是所有具有下方6個(gè)節(jié)點(diǎn)值個(gè)節(jié)點(diǎn)值的二叉搜索樹(shù)中的二叉搜索樹(shù)中平均查找長(zhǎng)度最短的，平均查找長(zhǎng)度最短的，所以是最優(yōu)所以是最優(yōu)。k1k2k3k4k5k

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

19、i0的收的收益。益。課后練習(xí)課后練習(xí) 國(guó)家公路局得征稅規(guī)定要求兩塊廣告牌相對(duì)不國(guó)家公路局得征稅規(guī)定要求兩塊廣告牌相對(duì)不能位于小于或等于能位于小于或等于5英里之內(nèi)。你需要找一組英里之內(nèi)。你需要找一組地點(diǎn)來(lái)放置廣告牌以使得你的總收益在這個(gè)限地點(diǎn)來(lái)放置廣告牌以使得你的總收益在這個(gè)限制下達(dá)到最大。制下達(dá)到最大。 例如例如：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 問(wèn)

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

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