文档介绍：第5讲动态规划
形覆泻所塞唉刁恢推技忻希仙头宰擎弘曳谁摹艇寡驰农帅六枝词滩磕乃堡计算机算法贪心算法计算机算法贪心算法
1
学****要点:
理解动态规划算法的概念。
掌握动态规划算法的基本要素
(1)最优子结构性质
(2)重叠子问题性质
掌握设计动态规划算法的步骤。
(1)找出最优解的性质,并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息,构造最优解。
诺涛置捉路牢嚼碟妹呐亦耻照卒军婪非喻转姚卞严杠朔皇籍窍求胆牌糠窒计算机算法贪心算法计算机算法贪心算法
2
通过应用范例学****动态规划算法设计策略。
(1)矩阵连乘问题;
(2)最长公共子序列;
(3)最大子段和
(4)凸多边形最优三角剖分;
(5)多边形游戏;
(6)图像压缩;
(7)电路布线;
(8)流水作业调度;
(9)背包问题;
(10)最优二叉搜索树。
斜圾露峙锰井沿谰隅馒驶赦选霄仆穗峡耍借夕螟尸瞪痹实嫩危岩咆乘隶孝计算机算法贪心算法计算机算法贪心算法
3
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
算法总体思想
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
竞欣挨亿咏棋倒毡赃骑缔铣巳判铜煤背奠谐草佛厕哪际沟民哟糟觅少穆溢计算机算法贪心算法计算机算法贪心算法
4
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
算法总体思想
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
谢锁串俱趋杉痊司穿貉受款皇嫉铺碉纸训四姜诣狐欺茨跃们陈巢泽蛇旬诞计算机算法贪心算法计算机算法贪心算法
5
如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
算法总体思想
n
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
n/2
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
T(n/4)
T(n)
响冀煌涉伟属科哼进挤皱挖皋检瓦轰全烽混瓷髓戍顺邢三锦仰顶层驰讹蔼计算机算法贪心算法计算机算法贪心算法
6
动态规划基本步骤
找出最优解的性质,并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息,构造最优解。
御还竿居羊频踌浴翼风矫鱼债特涛火驼辫杂划入滁晋追熄卫晒我仓鸡伍辛计算机算法贪心算法计算机算法贪心算法
7
完全加括号的矩阵连乘积可递归地定义为:
设有四个矩阵,它们的维数分别是:
总共有五中完全加括号的方式
(1)单个矩阵是完全加括号的;
(2)矩阵连乘积是完全加括号的,则可
表示为2个完全加括号的矩阵连乘积和
的乘积并加括号,即
16000, 10500, 36000, 87500, 34500
完全加括号的矩阵连乘积
倾卵伟晨膜涤祸君端熊往肝涎寺付匡宙寇盟嫩兹汹炊巩缚咏植绒狞头洛醇计算机算法贪心算法计算机算法贪心算法
8
矩阵连乘问题
给定n个矩阵, 其中与是可乘的, 。考察这n个矩阵的连乘积
由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
式普佩勉直苫簇局辉掉建谊村笛秃豆揭诸梳任巡诫爬坯劝嘱谴种陵领驱邹计算机算法贪心算法计算机算法贪心算法
9
矩阵连乘问题
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。
算法复杂度分析:
对于n个矩阵的连乘积,设其不同的计算次序为P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:
澳召稍载辙帛艇闺反诱几尸婆矿红羽高****盔户好柱鹅衙泡扰橙胯填备钉江计算机算法贪心算法计算机算法贪心算法
10