算法设计与分析动态规划

算法设计与分析动态规划第1页，课件共42页，创作于2023年2月第十一章动态规划（一）动态规划概念矩阵链乘法（过程及分析）问题描述最优括号化分析计算最优代价构造最优解动态规划的基本内容最优结构重叠子问题记忆化程序演示及说明第2页，课件共42页，创作于2023年2月预备知识1.分治法与动态规划的关系

（1）分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题类型相同。递归地解这些子问题，然后将各子问题的解并到原问题的解。（2）动态规划基本思想：是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是：适合于动态规划求解的问题，经分解得到的子问题往往不是相互独立的。

动态规划算法通常用于求解具有某种具有最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应一个值，我们希望找到具有最优值（最大值或最小值）的那个解。（3）20世纪50年代由贝尔曼等人提出多阶段决策特性，并提出“最优性原理”，从而创建了动态规划这种新的算法设计方法。动态规划的目标就是要在所有允许选择的决策序列中选择一个会获得问题最优解的决策序列。第3页，课件共42页，创作于2023年2月预备知识2.两矩阵相乘的充分必要条件是第一个矩阵的列数与第二个矩阵的行数相等。第4页，课件共42页，创作于2023年2月动态程序算法设计四步曲第5页，课件共42页，创作于2023年2月矩阵链乘法第6页，课件共42页，创作于2023年2月矩阵链乘法第7页，课件共42页，创作于2023年2月矩阵链乘法第8页，课件共42页，创作于2023年2月矩阵链乘法第9页，课件共42页，创作于2023年2月计算括号化重数第10页，课件共42页，创作于2023年2月计算括号化重数P(1)=1P(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=14第11页，课件共42页，创作于2023年2月计算括号化重数P(n)=1n=1n>=22*第12页，课件共42页，创作于2023年2月计算括号化重数P(1)=p(2)=1P(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)=14第13页，课件共42页，创作于2023年2月计算括号化重数第14页，课件共42页，创作于2023年2月计算括号化重数第15页，课件共42页，创作于2023年2月最优括号化的结构第16页，课件共42页，创作于2023年2月一个递归解第17页，课件共42页，创作于2023年2月一个递归解第18页，课件共42页，创作于2023年2月计算最优代价第19页，课件共42页，创作于2023年2月计算最优代价第20页，课件共42页，创作于2023年2月计算最优代价第21页，课件共42页，创作于2023年2月计算最优代价为下列矩阵序列求解最优解第22页，课件共42页，创作于2023年2月计算最优代价步长为0，1m[1,1]=m[2,2]=m[3,3]=m[4,4]=m[5,5]=m[6,6]=0m[1,2]=min{m[1,1]+m[2,2]+p0*p1*p2}=30*35*15=15750S[1,2]=1m[2,3]=min{m[2,2]+m[3,3]+p1*p2*p3}=35*15*5=2625S[2,3]=2m[3,4]=min{m[3,3]+m[4,4]+p2*p3*p4}=15*5*10=750S[3,4]=3m[4,5]=min{m[4,4]+m[5,5]+p3*p4*p5}=5*10*20=1000S[4,5]=4m[5,6]=min{m[5,5]+m[6,6]+p4*p5*p6}=10*20*25=5000S[5,6]=5第23页，课件共42页，创作于2023年2月计算最优代价步长为2m[1,3]=min{m[1,1]+m[2,3]+p0*p1*p3,m[1,2]+m[2,3]+p0*p2*p3} =min{0+2625+30*35*5,15750+0+30*15*5}=min{7875,18000}=7875S[1,3]=1 m[2,4]=min{m[2,2]+m[3,4]+p1*p2*p4,m[2,3]+m[4,4]+p1*p3*p4} =min{0+750+35*15*10,2625+0+35*5*10} =min{6000,4375}=4375S[2,4]=3第24页，课件共42页，创作于2023年2月计算最优代价m[3,5]=min{m[3,3]+m[4,5]+p2*p3*p5,m[3,4]+m[5,5]+p2*p4*p5}=min{0+1000+15*5*20,750+0+15*10*20}=min{2500,3750}=2500S[3,5]=3m[4,6]=min{m[4,4]+m[5,6]+p3*p4*p6,m[4,5]+m[6,6]+p3*p5*p6}=min{0+5000+5*10*25,1000+0+5*20*25}=min{6250,3500}=3500S[4,6]=5第25页，课件共42页，创作于2023年2月计算最优代价步长为3m[1,4]=min{m[1,1]+m[2,4]+p0*p1*p4,m[1,2]+m[3,4]+p0*p2*p4,m[1,3]+m[4,4]+p0*p3*p4}=min{0+4375+30*35*10,15750+750+30*15*10,7875+0+35*5*10}=min{14875,21000,9375}=9375s[1,4]=3m[2,5]=min{m[2,2]+m[3,5]+p1*p2*p5,m[2,3]+m[4,5]+p1*p3*p5,m[2,4]+m[5,5]+p1*p4*p5}=min{0+2500+35*15*20,2625+1000+35*5*20,4375+0+35*10*20}=min{13000,7125,11375}=7025S[2,5]=3第26页，课件共42页，创作于2023年2月计算最优代价M[3,6]=min{m[3,3]+m[4,6]+p2*p3*p6,m[3,4]+m[5,6]+p2*p4*p6,m[3,5]+m[6,6]+p2*p5*p6}=min{0+3500+15*5*25,750+5000+15*10*25,7500+0+15*20*25}=min{5375,9500,10000}=5375S[3,6]=3第27页，课件共42页，创作于2023年2月计算最优代价步长为4M[1,5]=min{m[1,1]+m[2,5]+p0*p1*p5,m[1,2]+m[3,5]+p0*p2*p5,m[1,3]+m[4,5]+p0*p3*p5,m[1,4]+m[5,5]+p0*p4*p5}=min{0+7125+30*35*20,15750+2500+36*15*20,7875+1000+30*5*20,9375+0+30*10*20}=min{28125,27250,11875,15375}=11875S[1,5]=3M[2,6]=min{m[2,2]+m[3,6]+p1*p2*p6,m[2,3]+m[4,6]+p1*p3*p6,m[2,4]+m[5,6]+p1*p4*p6,m[2,5]+m[6,6]+p1*p5*p6}=min{0+5357+35*15*25,2625+3500+35*5*25,4375+5000+35*10*25,7125+0+35*20*25}=min{18500,10500,18125,24625}=10500S[2,6]=3第28页，课件共42页，创作于2023年2月计算最优代价步长为5m[1,6]=min{m[1,1]+m[2,6]+p0*p1*p6,m[1,2]+m[3,6]+p0*p2*p6,m[1,3]+m[4,6]+p0*p3*p6,m[1,4]+m[5,6]+p0*p4*p6, m[1,5]+m[6,6]+p0*p5*p6}=min{0+10500+30*35*25,15750+5375+30*15*25,7875+3500+30*5*25,9375+5000+30*10*25, 11875+0+30*20*25}=min{36750,32375,15125,21875,26875}=15125S[1,6]=3第29页，课件共42页，创作于2023年2月计算最优代价第30页，课件共42页，创作于2023年2月构造最优解第31页，课件共42页，创作于2023年2月构造最优解第32页，课件共42页，创作于2023年2月动态程序设计基础

从工程的角度看,对一个具体问题,我们在什么样的情况下需要有一个动态程序设计解?在这一节里,我们要介绍适合采用动态程序设计方法的最优化问题中的两个要素:最优结构和重叠子问题.并讨论另一个称作记忆化的方法,以充分利用重叠子问题性质.第33页，课件共42页，创作于2023年2月最优结构1、一个问题具有最优子结构，则该问题的最优解中包含了子问题的最优解。当一个问题呈现出最优子结构时，动态程序设计可能就是一个合适的侯选方法。矩阵链乘法问题具有最优子结构.可以用反证法证明子问题具有最优解.

2、一个问题的最优子结构常常暗示了可应用动态程序设计方法的一个子问题空间。找出合适的动态程序设计的子问题空间的一个方法是通过对子问题实例的叠代来考察一个问题的最优子结构。第34页，课件共42页，创作于2023年2月重叠子问题1、适合于动态程序设计方法解决的最优化问题必须具有的第二个要素是子问题空间要“很小”，即用来解原来问题的一个递归算法可反复地解同样的子问题，而不产生新的子问题。当一个递归算法不断地遇到同一问题，则该最优化问题包含有重叠子问题。动态程序设计方法总是充分利用重叠子问题，对每个子问题只解一次，把解放在一个在需要时就可查看的表中，而每一次查表的时间为常数。第35页，课件共42页，创作于2023年2月重叠子问题2、确定m[i,j]的低效的递归算法第36页，课件共42页，创作于2023年2月重叠子问题

调用RECURSIVE-MATRIX-CHAIN(p,1,4)所产生的递归树如图16.2所示第37页，课件共42页，创作于2023年2月重叠子问题3、由此递归过程计算m[1,n]的运行时间T（n）至少为n的指数