《算法设计与分析12动态规划1》由会员分享，可在线阅读，更多相关《算法设计与分析12动态规划1（45页珍藏版）》请在金锄头文库上搜索。
1、算法算法设计与分析与分析2007.91第十一章第十一章 动态规划（一）划（一）n动态规划概念划概念n矩矩阵链乘法（乘法（过程及分析）程及分析）n问题描述描述n最最优括号化分析括号化分析n计算最算最优代价代价n构造最构造最优解解n动态规划的基本内容划的基本内容n最最优结构构n重叠子重叠子问题n记忆化化n程序演示及程序演示及说明明2预备知知识1.分治法与分治法与动态规划的关系划的关系（1）分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题类型相同。递归地解这些子问题，然后将各子问题的解并到原问题的解。（2）动态规划基本思想：是将待求解问题分解成若干个子问
2、题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是：适合于动态规划求解的问题，经分解得到的子问题往往不是相互独立的。动态规划算法通常用于求解具有某种具有最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应一个值，我们希望找到具有最优值（最大值或最小值）的那个解。（3）20世纪50年代由贝尔曼等人提出多阶段决策特性，并提出“最优性原理”，从而创建了动态规划这种新的算法设计方法。动态规划的目标就是要在所有允许选择的决策序列中选择一个会获得问题最优解的决策序列。3预备知知识2.两矩两矩阵相乘的充分必要条件是第一个矩相乘的充分必要条件是第一个矩阵的列数与第二个矩的列数与
3、第二个矩阵的行数相等。的行数相等。4动态程序算法程序算法设计四步曲四步曲5矩矩阵链乘法乘法6矩矩阵链乘法乘法7矩矩阵链乘法乘法8矩矩阵链乘法乘法9计算括号化重数算括号化重数10计算括号化重数算括号化重数P(1) = 1 P(2) = 1P(3) = p(1)*p(2)+p(2)*p(1) = 1*1+1*1 =2P(4) = p(1) *p(3)+p(2)*p(2)+p(3)*p(1) = 1*2 +1*1 +2*1 = 5P(5) = p(1)*p(4)+p(2)*p(3)+p(3)*p(2)+ p(4)*p(1) = 1*5 +1*2+2*1 + 5*1 = 1411计算括号化重数算括号化
4、重数P(n) = 1n=1n=22*12计算括号化重数算括号化重数P(1) =p(2)= 1 P(3) = 2*(P(1)*P(2) =2P(4) = 2*(P(1)*P(3)+P(2)*P(2)/2) = 2*2.5 =5P(5) = 2*(P(1)*P(4)+P(2)*P(3) = 2*(5+2) =1413计算括号化重数算括号化重数14计算括号化重数算括号化重数15最最优括号化的括号化的结构构16一个一个递归解解17一个一个递归解解18计算最算最优代价代价19计算最算最优代价代价20计算最算最优代价代价21计算最算最优代价代价为下列矩下列矩阵序列求解最序列求解最优解解22计算最算最优代价
5、代价步步长为0，1m1,1=m2,2=m3,3=m4,4=m5,5=m6,6=0m1,2=minm1,1+m2,2+p0*p1*p2=30*35*15=15750S1,2=1m2,3=minm2,2+m3,3+p1*p2*p3=35*15*5=2625S2,3=2m3,4=minm3,3+m4,4+p2*p3*p4=15*5*10=750S3,4=3m4,5=minm4,4+m5,5+p3*p4*p5=5*10*20=1000S4,5=4m5,6=minm5,5+m6,6+p4*p5*p6=10*20*25=5000S5,6=523计算最算最优代价代价步步长为2m1,3=minm1,1+m2,
6、3+p0*p1*p3,m1,2+m2,3+p0*p2*p3 =min0+2625+30*35*5,15750+0+30*15*5 =min7875,18000 = 7875S1,3 = 1m2,4=minm2,2+m3,4+p1*p2*p4,m2,3+m4,4+p1*p3*p4 =min0+750+35*15*10,2625+0+35*5*10 =min6000,4375 =4375S2,4 = 324计算最算最优代价代价m3,5=minm3,3+m4,5+p2*p3*p5,m3,4+m5,5+p2*p4*p5 =min0+1000+15*5*20,750+0+15*10*20 =min250
7、0,3750 =2500 S3,5 =3m4,6=minm4,4+m5,6+p3*p4*p6,m4,5+m6,6+p3*p5*p6 =min0+5000+5*10*25,1000+0+5*20*25 =min6250,3500 =3500 S4,6 =525计算最算最优代价代价步步长为3m1,4=minm1,1+m2,4+p0*p1*p4,m1,2+m3,4+p0*p2*p4, m1,3+m4,4+p0*p3*p4 =min0+4375+30*35*10,15750+750+30*15*10,7875+0+35*5*10 =min14875,21000,9375 =9375s1,4=3m2,5
8、=minm2,2+m3,5+p1*p2*p5,m2,3+m4,5+p1*p3*p5, m2,4+ m5,5+p1*p4*p5 =min0+2500+35*15*20,2625+1000+35*5*20,4375+0+35*10*20 =min13000,7125,11375 =7025S2,5=326计算最算最优代价代价M3,6=minm3,3+m4,6+p2*p3*p6, m3,4+m5,6+p2*p4*p6, m3,5+m6,6+p2*p5*p6 =min0+3500+15*5*25,750+5000+15*10*25, 7500+0+15*20*25 =min5375,9500,1000
9、0 =5375S3,6=327计算最算最优代价代价步步长为4M1,5=minm1,1+m2,5+p0*p1*p5,m1,2+m3,5+p0*p2*p5, m1,3+m4,5+p0*p3*p5,m1,4+m5,5+p0*p4*p5 =min0+7125+30*35*20,15750+2500+36*15*20, 7875+1000+30*5*20,9375+0+30*10*20 =min28125,27250,11875,15375=11875S1,5=3M2,6=minm2,2+m3,6+p1*p2*p6,m2,3+m4,6+p1*p3*p6, m2,4+m5,6+p1*p4*p6,m2,5+
10、m6,6+p1*p5*p6 =min0+5357+35*15*25,2625+3500+35*5*25, 4375+5000+35*10*25,7125+0+35*20*25 =min18500,10500,18125,24625=10500S2,6=328计算最算最优代价代价步步长为5m1,6=minm1,1+m2,6+p0*p1*p6, m1,2+m3,6+p0*p2*p6, m1,3+m4,6+p0*p3*p6, m1,4+m5,6+p0*p4*p6, m1,5+m6,6+p0*p5*p6 =min0+10500+30*35*25,15750+5375+30*15*25, 7875+35
11、00+30*5*25,9375+5000+30*10*25, 11875+0 + 30*20*25 =min36750,32375,15125,21875,26875 =15125S1,6=329计算最算最优代价代价30构造最构造最优解解31构造最构造最优解解32动态程序程序设计基基础 从工程的角度看从工程的角度看,对一个具体一个具体问题,我我们在在什么什么样的情况下需要有一个的情况下需要有一个动态程序程序设计解解?在在这一一节里里,我我们要介要介绍适合采用适合采用动态程序程序设计方法的最方法的最优化化问题中的两中的两个要素个要素:最最优结构和重叠子构和重叠子问题.并并讨论另另一个称作一个称作
12、记忆化的方法化的方法,以充分利用重叠以充分利用重叠子子问题性性质.33最最优结构构1、一个、一个问题具有最具有最优子子结构，构，则该问题的最的最优解中包解中包含了子含了子问题的最的最优解。当一个解。当一个问题呈呈现出最出最优子子结构构时，动态程序程序设计可能就是一个合适的侯可能就是一个合适的侯选方法。方法。矩矩阵链乘法乘法问题具有最具有最优子子结构构. 可以用反可以用反证法法证明子明子问题具有最具有最优解解. 2、一个、一个问题的最的最优子子结构常常暗示了可构常常暗示了可应用用动态程序程序设计方法的一个子方法的一个子问题空空间。找出合适的找出合适的动态程序程序设计的子的子问题空空间的一个的一个
13、方法是通方法是通过对子子问题实例的叠代来考察一个例的叠代来考察一个问题的最的最优子子结构。构。34重叠子重叠子问题 1、适合于、适合于动态程序程序设计方法解决的最方法解决的最优化化问题必必须具有的第二个要素是子具有的第二个要素是子问题空空间要要“很很小小”，即用来解原来，即用来解原来问题的一个的一个递归算法可反算法可反复地解同复地解同样的子的子问题，而不，而不产生新的子生新的子问题。当一个当一个递归算法不断地遇到同一算法不断地遇到同一问题，则该最最优化化问题包含有重叠子包含有重叠子问题。动态程序程序设计方法方法总是充分利用重叠是充分利用重叠子子问题，对每个子每个子问题只解一次，把解放在一只解一
14、次，把解放在一个在需要个在需要时就可就可查看的表中，而每一次看的表中，而每一次查表的表的时间为常数。常数。35重叠子重叠子问题 2、确定、确定mi,j的低效的的低效的递归算法算法36重叠子重叠子问题 调用用RECURSIVE-MATRIX-CHAIN(p,1,4)所所产生的生的递归树如如图16.2所示所示37重叠子重叠子问题 3、由此、由此递归过程程计算算m1,n的运行的运行时间T（n）至少至少为n的指数的指数假假设执行第行第1-2行和第行和第6-7行都至少花行都至少花单位位时间。分析。分析该过程可得程可得递归式式T（1） 1 对i=1,2,n-1,每一每一项T（i)一次是作一次是作为T（k）
15、，），另一次作另一次作为T（n-k）出）出现，该递归式可重写式可重写为：38重叠子重叠子问题 替替换法法证明明T（n）=(2n),具体地，具体地，证明明对所有的所有的n 1,有有T(n) 2n-1 首先，首先，T(1) 1=20 对n 239重叠子重叠子问题 所以所以调用用RECURSIVE-MATRIX-CHAIN(p,1,n)的的总代价至少代价至少为n的指数。的指数。40记忆化化1、记忆的的递归算法算法其思想是其思想是记忆原原问题的自然但低效的自然但低效的的递归算法。它既然具有通常的算法。它既然具有通常的动态程程序序设计途径的效率，又采用了一种自途径的效率，又采用了一种自顶向下的策略。向下
16、的策略。一个一个记忆的的递归算法算法为每个子每个子问题的解在表中的解在表中记录一个表一个表项。以后每次遇。以后每次遇到到该子子问题，只要，只要查表中的先前填入的表中的先前填入的值即可。即可。41记忆化化2、RECURSIVE-MATRIX-CHAIN的的记忆化版本：化版本：42记忆化化 图16.2说明了明了MEMORIZE-MATRIX-CHAIN是如何是如何较RECURSIVE-MATRIX-CHAIN节省省时间。阴影部。阴影部分的子分的子树表示被表示被查看（而不是被看（而不是被计算）的算）的值43记忆化化3、运行、运行时间为O（n3）(n2)个表个表项中的每一个都由中的每一个都由MEMORIZE-MATRIX-CHAIN中的第中的第4行行进行行一次初始化，并由一次初始化，并由对LOOKUP-CHIAN的一次的一次调用填充。用填充。对LOOKUP-CHIAN的的(n2)次次调用用中的每一次的中的每一次的时间都都为O（n）,则总的的时间代代价价为O(n3)。因此，因此，记忆技技术将一个将一个(2n)算法算法变成成了一个了一个O(n3)算法。算法。44The EndnThank you!45
