第3章-动态规划-作业课件.ppt

《第3章-动态规划-作业课件.ppt》由会员分享，可在线阅读，更多相关《第3章-动态规划-作业课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课后练习课后练习练习1：已知一组连乘矩阵已知一组连乘矩阵A1A2A3A4A5的行列的行列数如下面数如下面p向量所示：向量所示：1.如使用函数如使用函数直接递归调用直接递归调用（穷举法）的形式求（穷举法）的形式求解，则是无效算法，请画出函数递归调用的递解，则是无效算法，请画出函数递归调用的递归树树形，并说明有哪些子问题被重复计算。归树树形，并说明有哪些子问题被重复计算。2.请用请用动态规划法动态规划法求解最优计算顺序，写出计算求解最优计算顺序，写出计算过程以及加括号的计算顺序表达式。过程以及加括号的计算顺序表达式。p=(5,3,9,2,2,4)A1A2A3A4A5 p=(5,3,9,2,2,4)

2、函数递归调用的递归树树形函数递归调用的递归树树形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+p0p1p2=135m23=min 2k3 m22+m33+p1p2p3=54m34=mi

3、n 3k4 m33+m44+p2p3p4=36m45=min 4k5 m44+m55+p3p4p5=161355436161234A1A2A3A4A5 p=(5,3,9,2,2,4)55M矩矩阵55S矩矩阵000000000013554361612348466881333.计算算mi,i+3(i=1,2)：（矩（矩阵链长度度为3）m14=min 1k4 m11+m24+p0p1p4,m12+m34+p0p2p4,m13+m44+p0p3p4 =96,261,104 =96961A1A2A3A4A5 p=(5,3,9,2,2,4)55M矩矩阵55S矩矩阵000000000013554361612

4、348466881333.计算算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矩矩阵000000000013554361612348466881339619044.计算算mi,i+4(i=1)：（矩（矩阵链长度度为4）m15=min 1k5 m11+m25+p0p1p5,m12+m35+p0p2p5,m13+m45+p0p3p5,m14+m55+p0p4p5 =150

5、,403,212,136 =136完成后通完成后通过S矩矩阵得出最得出最优完全加括完全加括号方式号方式为：(A1(A2 A3)A4)A5)1364课后练习课后练习练习2：假定有假定有6个键值，个键值，k1、k2、k3、k4、k5、k6，其中，其中k1k2k3k4k5k6。它们被搜索的概。它们被搜索的概率分别为率分别为 0.24，0.18，0.09，0.13，0.3，0.06，请使用动态规划算法求一颗最优二叉搜索树，请使用动态规划算法求一颗最优二叉搜索树，要求：要求：1.给出该树的平均查找长度；给出该树的平均查找长度；2.画出树形。画出树形。C(i,i-1)=0 (1in+1)式式1C(i,i)

6、=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)式式35641754326321056417543263210二二维表表C二二维表表R0000000.240.180.090.130.300.061234560.615641754326321056417543263210二二维表表C二二维表表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.42556417543263210564175432

7、63210二二维表表C二二维表表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.4250.842以此以此类推推可以把可以把C(2,5)、C(3,6)计算出来算出来0.7130.8350.6851.1921.3640.9555641754326321056417543263210二二维表表C二二维表表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.4250.842以此以此类推推可以可以把把C(2,6)计算出来算出来0.7130.8350.6851.1921.36

8、40.9552.0121.5355641754326321056417543263210二二维表表C二二维表表R0000000.240.180.090.130.300.061234560.610.3620.3140.5650.4250.842最最优值：2.19即最即最优二叉二叉搜索搜索树的平的平均均查找找长度度（ASL）为2.190.7130.8350.6851.1921.3640.9552.0121.5352.192则由两个矩阵值得到则由两个矩阵值得到最最优二叉搜索二叉搜索树树形为：树形为：5641754326321056417543263210二二维表表C二二维表表R0000000.240

9、.180.090.130.300.061234560.610.3620.3140.5650.4250.8420.7130.8350.6851.1921.3640.9552.0121.5352.192k2k1k5k4k3左图中的树形符合二叉搜索树的定义。左图中的树形符合二叉搜索树的定义。该树的平均查找长度为该树的平均查找长度为2.19该树树形是所有具有下方该树树形是所有具有下方6个节点值个节点值的二叉搜索树中的二叉搜索树中平均平均查找找长度最短的，度最短的，所以是最所以是最优。k1k2k3k4k5k6,0.24,0.18,0.09,0.13,0.3,0.06课后练习课后练习练习3：假如你正在管理

10、假如你正在管理SD纪念馆公路的广告牌纪念馆公路的广告牌的建设，这条路从西到东的建设，这条路从西到东M英里，是一段旅行量英里，是一段旅行量大的路程。广告牌的可能的地点用数字大的路程。广告牌的可能的地点用数字x1,x2,.,xn给出，每个均处在区间给出，每个均处在区间0,M中（沿这条公路中（沿这条公路规定它们的地点，从路地西端用英里量度）。如规定它们的地点，从路地西端用英里量度）。如果你放一块广告牌在地点果你放一块广告牌在地点xi，你就得到，你就得到ri0的收的收益。益。例如例如：M=20,n=4 x1,x2,x3,x4 =6,7,12,14 r1,r2,r3,r4 =5,6,5,1 问题的问题的

11、最最优子子结构性构性质：x1,x2,xn 的的最优解一定包含最优解一定包含 x1,x2,xn-1 的最优解，的最优解，该结论可以用该结论可以用反证法反证法证明。证明。最最优解解为：为：n个地点放置两个广告牌的方案，个地点放置两个广告牌的方案，同时使总收益最大。同时使总收益最大。最最优值设计为：总收益。设计为：总收益。解解题思路：思路：考虑对于给定输入实例的一个最优解，在考虑对于给定输入实例的一个最优解，在地点地点xn或者放广告牌，或者不放。或者放广告牌，或者不放。如果不放，那么在地点如果不放，那么在地点x1,x2,xn上的最优解实上的最优解实际上与在地点际上与在地点x1,x2,xn-1上的最优

12、解一样。上的最优解一样。如果放，那么应该去掉如果放，那么应该去掉xn以及与它在以及与它在5英里之内的所英里之内的所有其他地点，并且找在剩下地点上的最优解。有其他地点，并且找在剩下地点上的最优解。当考察仅前当考察仅前j个地点个地点x1,x2,xj所定义的问题时，所定义的问题时，同样的推理也适用：同样的推理也适用：在最在最优解中包含或不包含解中包含或不包含xj，具有同具有同样的的结果果。例如例如：M=20,n=4 x1,x2,x3,x4 =6,7,12,14 r1,r2,r3,r4 =5,6,5,1 如此得出了如下的递推式，另如此得出了如下的递推式，另OPT(j)表示从表示从x1,xj中地点的中地

13、点的最最优子集得到的收益子集得到的收益。例如例如：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。