计算机算法贪心算法.ppt

第5讲动态规划
学****要点
理解动态规划算法的概念。
掌握动态规划算法的基本要素
(1)最优子结构性质
(2)重叠子问题性质
掌握设计动态规划算法的步骤
(1)找出最优解的性质,并刻划其结构特征
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息,构造最优解。
通过应用范例学****动态规划算法设计策略
(1)矩阵连乘问题
(2)最长公共子序列
(3)最大子段和
(4)凸多边形最优三角剖分
(5)多边形游戏;
(6)图像压缩
(7)电路布线
(8)流水作业调度
(9)背包问题;
(10)最优二叉搜索树
算法总体思想
动态规划算法与分治法类似,其基本思想也是将待求
解问题分解成若干个子问题
T(n/2)
T(n/2)
T(n/2)
T(n/2
算法总体思想
但是经分解得到的子问题往往不是互相独立的。不同子问题的
数目常常只有多项式量级。在用分治法求解时,有些子问题被
重复计算了许多次。
Tin) tin a)tn 4)tn 4)t(n 4)T n 4)T (n 4)T(n 4) T n 4)T(n 4)T(n 4)(n 4)Tn n 4))tn
算法总体思想
■如果能够保存已解决的子问题的答案,而在需要时再找出已求
得的答案,就可以避免大量重复计算,从而得到多项式时间算
法
nl4) Tn/4)TnM)Tn/4)Tn
4)Ta4)T24)
动态规划基本步骤
找出最优解的性质,并刻划其结构特征
递归地定义最优值
以自底向上的方式计算出最优值。
■根据计算最优值时得到的信息,构造最优解
完全加括号的矩阵连乘积
完全加括号的矩阵连乘积可递归地定义为:
(1)单个矩阵是完全加括号的
(2)矩阵连乘积A是完全加括号的,则A可
表示为2个完全加括号的矩阵连乘积B和C
的乘积并加括号,即A=(BC
◆
A=50×10B=10×40C=40×30D=30×5
总共有五中完全加括号的方式
(A((BC)D))(AB(CD))((AB)CD))
(((AB)C)D) ((ABCD)
16000,10500,36000,87500,34500
矩阵连乘问题
给定n个矩阵{A,A2,…A4n}其中A与A1是可乘
的,i=1,2,n-1。考察这n个矩阵的连乘积
A1A2…A,
由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不
同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已
完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算
法计算出矩阵连乘积
矩阵连乘问题
给定n个矩阵{A1A2灬,An},其中A与A+1是可乘的,i=1,
2…,η-1。如何确定计算矩阵连乘积的计算次序,使得依此次
序计算矩阵连乘积需要的数乘次数最少。
◆穷举法:列举出所有可能的计算次序,并计算出每一种计
算次序相应需要的数乘次数,从中找出一种数乘次数最少的
计算次序。
算法复杂度分析
对于n个矩阵的连乘积,设其不同的计算次序为P(n
由于每种加括号方式都可以分解为两个子矩阵的加括号问题:
(A1…Ak)(Ak+)可以得到关于P(n)的递推式如下
n=1
P(n)=
P(h)P(n-k)n>I
→P(n)=92(4"/n32)