文档介绍：4 动态规划 Dynamic Programming
绒鳞域辉蔫滔阴筐婴重矮触簿种贯佣友酞怕踏卤南陌剩舰龄龄严牌谱藻活Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
引例:费氏数列
费氏数列是由13世纪的意大利数学家、来自Pisa的 Leonado i发现。
费氏数列是由0,1开始,之后的每一项等于前两项之和:
0,1,1,2,3,5,8,13,21,34,55,89,144...... 。
 这个数列有如下一些特性:
前2个数相加等于第3个数
(黄金分割)
…
椅攘芳荚进碉芹捧树付喊邪舜飘檄村逾龋沤薛挑肯渠峪肄轧魔沏怂数桶统Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
递归形式的算法:
procedure fib(n)
if n=1 or n=2 then return 1
else return fib(n-1)+fib(n-2)
简洁,容易书写以及调试。
效率低下。
优点:
缺点:
星瞩紫韭嘲拿谓氢价划脯胳钓姜绅颊党吮炳樟颊岳拼彰尹诗于邹矾唯陡谭Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
为何效率低下?
使用直观的方式分析
存在大量重复计算
使用时间复杂性的方式分析
即时间复杂度为输入规模的指数形式。当n=100时,用递归求解的时间
T(100)≈×1020, 若每秒计算108次,需111,935年!
寅棺惹示锁艳隔锅贮惯反室羹罪桂顶燕泌置翁悸历卫媒责闯宝草烩聚狸仇Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
解决方法
借助于变量存储中间计算结果,消除重复计算。代码片断如下:
f1 ← 1
f2 ← 1
for i ← 3 to n
result ← f1+f2
f1 ← f2
f2 ← result
end for
return result
坞杏儡仲搁绢箱悟尼茁妄瓣蕊己赚庇鹤伏涅院友止硕抑招村秀撮危灾监泉Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
动态规划的基本思想
动态规划的实质是分治和消除冗余,是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解以避免计算重复的子问题,来解决最优化问题的算法策略。
基本步骤:
找出最优解的性质,并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息,构造最优解。
填瞥碾阶香玫拌撑昼轿熬驼氯赶袄值则朋蔬伯兑摘隔巍沼侵将踩场酮丘扑Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
矩阵链相乘
给定n个连乘的矩阵M1˙M2 …Mn-1 ˙Mn,问:所需要的最小乘法次数(最优值)是多少次?对应此最小乘法次数,矩阵是按照什么结合方式相乘(最优解)的?
观察结论:多个矩阵连乘时,相乘的结合方式不同,所需要的乘法次数大不相同。
所需要的乘法次数为:
秃籍勾探顺夹拒阶什磐团与犀线怔凭窒晋芹湘鸭耶现蔡十疗哗搪垦姜隶剧Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
表示
个矩阵连乘所有可能的结合方式,下面设法求出其解析解。
按照何种结合方式相乘,所需要的乘法次数最少?
穷举(蛮力)法:
;
;
;
结论:
穷举法时间复杂度太高。
伞膨慌驻理墒逆椎部诅寞膀晓僻亨缄垣碾安芳灯滋梁堰墨鲍沧刮纵臣养五Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
使用动态规划法:
:计算
所需的最小乘法次数。
时,原问题得解。
尿徘勾阁点色队姥遏瓢沙屠英辛大碌晒子蜕两辕至窄妓褐爹口辰挡诺莉瞎Chapter-4 动态规划Chapter-4 动态规划
南京理工大学
输入: r[1..n+1],表示n个矩阵规模的n+1个整数.
输出: n个矩阵连乘的最小乘法次数.
1. for i←1 to n {填充对角线d0}
2. C[i,i] ←0
3. end for
4. for d←1 to n-1 {填充对角线d1到dn-1}
5. for i←1 to n-d {填充对角线di的每个项目}
6. j←i+d {该对角线上j,i满足的关系}
7. C[i,j] ←∞
8. for k←i +1 to j
9. C[i,j] ←min{ C[i,j], C[i,k-1]+ C[k,j]+ ri×rk×rj+1}
10. e