算法设计与分析动态规划.pptVIP

计算最优代价第30页，共42页，星期日，2025年，2月5日第1页，共42页，星期日，2025年，2月5日第十一章动态规划（一）动态规划概念矩阵链乘法（过程及分析）问题描述最优括号化分析计算最优代价构造最优解动态规划的基本内容最优结构重叠子问题记忆化程序演示及说明第2页，共42页，星期日，2025年，2月5日预备知识1.分治法与动态规划的关系（1）分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题类型相同。递归地解这些子问题，然后将各子问题的解并到原问题的解。（2）动态规划基本思想：是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是：适合于动态规划求解的问题，经分解得到的子问题往往不是相互独立的。

动态规划算法通常用于求解具有某种具有最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应一个值，我们希望找到具有最优值（最大值或最小值）的那个解。（3）20世纪50年代由贝尔曼等人提出多阶段决策特性，并提出“最优性原理”，从而创建了动态规划这种新的算法设计方法。动态规划的目标就是要在所有允许选择的决策序列中选择一个会获得问题最优解的决策序列。第3页，共42页，星期日，2025年，2月5日预备知识2.两矩阵相乘的充分必要条件是第一个矩阵的列数与第二个矩阵的行数相等。第4页，共42页，星期日，2025年，2月5日动态程序算法设计四步曲第5页，共42页，星期日，2025年，2月5日矩阵链乘法第6页，共42页，星期日，2025年，2月5日矩阵链乘法第7页，共42页，星期日，2025年，2月5日矩阵链乘法第8页，共42页，星期日，2025年，2月5日矩阵链乘法第9页，共42页，星期日，2025年，2月5日计算括号化重数第10页，共42页，星期日，2025年，2月5日计算括号化重数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页，星期日，2025年，2月5日计算括号化重数P(n)=1n=1n=22*第12页，共42页，星期日，2025年，2月5日计算括号化重数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页，星期日，2025年，2月5日计算括号化重数第14页，共42页，星期日，2025年，2月5日计算括号化重数第15页，共42页，星期日，2025年，2月5日最优括号化的结构第16页，共42页，星期日，2025年，2月5日一个递归解第17页，共42页，星期日，2025年，2月5日一个递归解第18页，共42页，星期日，2025年，2月5日计算最优代价第19页，共42页，星期日，2025年，2月5日计算最优代价第20页，共42页，星期日，2025年，2月5日计算最优代价第21页，共42页，星期日，2025年，2月5日计算最优代价为下列矩阵序列求解最优解第22页，共42页，星期日，2025年，2月5日计算最优代价步长为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页，星期日，2025年，2月5日计算最优代价步长为2