《第3章_动态规划_作业-322 (1)》由会员分享，可在线阅读，更多相关《第3章_动态规划_作业-322 (1)（25页珍藏版）》请在文档大全上搜索。
1、课后练习课后练习练习练习1：已知一组连乘矩阵已知一组连乘矩阵A1A2A3A4A5的行列的行列数如下面数如下面p向量所示：向量所示：1. 如使用函数如使用函数直接递归调用直接递归调用（穷举法）的形式（穷举法）的形式求解，则是无效算法，请画出函数递归调用求解，则是无效算法，请画出函数递归调用的递归树树形，并说明有哪些子问题被重复的递归树树形，并说明有哪些子问题被重复计算。计算。2. 请用请用动态规划法动态规划法求解最优计算顺序，写出计求解最优计算顺序，写出计算过程以及加括号的计算顺序表达式。算过程以及加括号的计算顺序表达式。p = (5, 3, 9, 2, 2, 4)A1A2A3A4A5 p =
2、(5, 3, 9, 2, 2, 4) 函数递归调用的递归树树形函数递归调用的递归树树形1:51:12:51:23:51:34:51:45:52:23:52:45:51:12:23:34:53:45:5 用用动态规划法动态规划法求解最优计算顺序，写出计算过程求解最优计算顺序，写出计算过程以及加括号的计算顺序表达式。以及加括号的计算顺序表达式。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矩阵得出最矩阵得出最优完全加括优完全加括号方式为：号方式为：( ( 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，请使用动态规划算法求一颗最优二叉搜索树，请使用动态规划算法求一颗最优二叉搜索树，要求：要求：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、17543263210二维表二维表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最优值：最优值：2.19即最优二叉即最优二叉搜索树的平搜索树的平均查找长度均查找长度（ASL）为）为2.190.7130.8350.6851.3731.0940.9552.0121.5352.192 则由两个矩阵值得到则由两个矩阵值得到最优二叉搜索树最优二叉搜索树树形为：树形为：
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个节点值个节点值的二叉搜索树中的二叉搜索树中平均查找长度最短的，平均查找长度最短的，所以是最优所以是最优。k1k2k3k4k5k
18、6, 0.24, 0.18, 0.09, 0.13, 0.3, 0.06k2k1k5k4k3k6课后练习课后练习 练习练习3：假如你正在管理假如你正在管理SD纪念馆公路的广告牌纪念馆公路的广告牌的建设，这条路从西到东的建设，这条路从西到东M英里，是一段旅行量英里，是一段旅行量大的路程。广告牌的可能的地点用数字大的路程。广告牌的可能的地点用数字x1, x2, ., xn给出，每个均处在区间给出，每个均处在区间0, M中（沿这条公路中（沿这条公路规定它们的地点，从路地西端用英里量度）。如规定它们的地点，从路地西端用英里量度）。如果你放一块广告牌在地点果你放一块广告牌在地点xi，你就得到，你就得到r
19、i0的收的收益。益。课后练习课后练习 国家公路局得征税规定要求两块广告牌相对不国家公路局得征税规定要求两块广告牌相对不能位于小于或等于能位于小于或等于5英里之内。你需要找一组英里之内。你需要找一组地点来放置广告牌以使得你的总收益在这个限地点来放置广告牌以使得你的总收益在这个限制下达到最大。制下达到最大。 例如例如：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、题的问题的最优子结构性质最优子结构性质： x1, x2, , xn 的的最优解一定包含最优解一定包含 x1, x2, , xn-1 的最优解，的最优解，该结论可以用该结论可以用反证法反证法证明。证明。 最优解最优解为：为：n个地点放置两个广告牌的方案，个地点放置两个广告牌的方案，同时使总收益最大。同时使总收益最大。 最优值最优值设计为：总收益。设计为：总收益。 解题思路：解题思路：考虑对于给定输入实例的一个最优解，在考虑对于给定输入实例的一个最优解，在地点地点xn或者放广告牌，或者不放。或者放广告牌，或者不放。 如果不放，那么在地点如果不放，那么在地点x1, x2, , xn上的最优解实上的最
21、优解实际上与在地点际上与在地点x1, x2, , xn-1上的最优解一样。上的最优解一样。 如果放，那么应该去掉如果放，那么应该去掉xn以及与它在以及与它在5英里之内的所英里之内的所有其他地点，并且找在剩下地点上的最优解。有其他地点，并且找在剩下地点上的最优解。 当考察仅前当考察仅前j个地点个地点x1, x2, , xj所定义的问题时，所定义的问题时，同样的推理也适用：同样的推理也适用：在最优解中包含或不包含在最优解中包含或不包含xj ，具有同样的结果具有同样的结果。例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5,
22、 6, 5, 1 令令e(j)表示编号比表示编号比j小且距小且距xj大于大于5英里的最东边的英里的最东边的地点地点xi。 因为地点是因为地点是从西到东从西到东编号的，一旦选择在编号的，一旦选择在xj放放一块广告牌，地点一块广告牌，地点x1, x2, , xe(j)仍旧是有效仍旧是有效的选项，但地点的选项，但地点xe(j)+1, , xj-1不是。不是。例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5, 6, 5, 1 西西东东xjxe(j) 如此得出了如下的递推式，另如此得出了如下的递推式，另OPT(j)表示从表示从
23、x1, , xj中地点的中地点的最优子集得到的收益最优子集得到的收益。例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5, 6, 5, 1 OPT(j) = max( rj + OPT(e(j), OPT(j-1) )j = 2, , nj01234OPT(j)0OPT(0) = 0OPT(1) = max( r1 + OPT(e(1), OPT(0) ) e(1) = 05例如例如：M=20, n=4 x1, x2, x3, x4 = 6, 7, 12, 14 r1, r2, r3, r4 = 5, 6, 5, 1 OPT(j) = max( rj + OPT(e(j), OPT(j-1) )j = 0, 1, 2, , nj01234e(j)00OPT(j)05OPT(2) = max( r2 + OPT(e(2), OPT(1) ) e(2) = 0OPT(3) = max( r3 + OPT(e(3), OPT(2) ) e(3) = 1OPT(4) = max( r4 + OPT(e(4), OPT(3) ) e(4) = 206110210最优解最优解：将：将广告牌放在广告牌放在x1和和x3，总收，总收益为益为10。
