《动态规划算法》由会员分享，可在线阅读，更多相关《动态规划算法（48页珍藏版）》请在金锄头文库上搜索。
1、驱阉叠赘绦衣倦含掇焦商危呈稠语咋梭柠遭焦叔讯亿抱指钦渤尸鬼踞园抉动态规划算法动态规划算法Chapter 7动态规划动态规划Dynamic Programming椰窟娱滔逛疼蝗汇故独窑兼儒乖畜轩阑呵社架亨栈崩绍屎蜡麦帮修帛疟嗣动态规划算法动态规划算法What is dynamic programmingn与分治法类似与分治法类似, 动态规划也是通过组合子问题动态规划也是通过组合子问题的解来求解问题的解来求解问题. n分治算法将问题划分成独立子问题分治算法将问题划分成独立子问题, 递归地解决递归地解决这些子问题这些子问题, 然后组合这些子问题的解来求解原然后组合这些子问题的解来求解原始问题始问题.
2、 nIf these subproblems are not independent, what will happen?梳谈趾胃篇包步漆踩要断才离隧竭抉窝酞甩楞蝇照贝庄祈靡斑职染驯曲贼动态规划算法动态规划算法7/28/20242算法总体思想算法总体思想n动态规划算法与分治法类似动态规划算法与分治法类似, , 其基本思想也是其基本思想也是将待求解问题分解成若干个子问题将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=歇猴滞吝巾抿棚仔毯斟句棚铝餐巍唱皂花娃禹识接氓掀依钧甘联剖聚利永动态规划算法动态规划算法7/28/20243n但是经分解得到的子问题往往不是
3、互相独立的但是经分解得到的子问题往往不是互相独立的. . 不同不同子问题的数目常常只有多项式量级子问题的数目常常只有多项式量级. . 在用分治法求解在用分治法求解时时, , 有些子问题被重复计算了许多次有些子问题被重复计算了许多次. . 算法总体思想算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)推帚器惜楷抄尽角妻壬色犹坎慕还酷健烯敞样沤屁炯驼代茶咎僳男济牢檄动态规划算法动态规划算法7/28/20244算
4、法总体思想算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)Those who cannot remember the past Those who cannot remember the past are doomed to repeat it. are doomed to repeat it. ( (无法记取教训者必重蹈覆辙无法记取教训者必重蹈覆辙无法记取教训者必重蹈覆辙无法记取教训者必重蹈覆辙 ) )-George Santayana, -George Sa
5、ntayana, The life of ReasonThe life of Reason, , Book I: Introduction and Book I: Introduction and Reason in Common Reason in Common Sense (1905)Sense (1905)n如果能够保存已解决的子问题的答案如果能够保存已解决的子问题的答案, , 而在需要时再而在需要时再找出已求得的答案找出已求得的答案, , 就可以避免大量重复计算就可以避免大量重复计算, , 从而从而得到多项式时间算法得到多项式时间算法. . 团新阜教羞永彭穿龙缚粉襟及亲瓮纽氖近妹抉荣肘
6、坡翅蓝蕴惶摘谗堡疏炭动态规划算法动态规划算法7/28/20245Fibonacci sequence(序列序列)nFibonacci序列定义如下：序列定义如下：q1. procedure f(n)q2. if n=1 or n=2 then return 1q3. else return f(n-1)+f(n-2)n这种递归形式有简洁、容易书写和容易查错等这种递归形式有简洁、容易书写和容易查错等优点优点, 最主要是它的抽象性最主要是它的抽象性. n但是它远不是有效的算法但是它远不是有效的算法. q算法复杂性算法复杂性: ( n)qWhy?童赣翘啊桩福蒲境幸貉凤雪旁妹父跌弗畜兹篇形篷蛮泉州睛唐迢
7、辑抓宗乡动态规划算法动态规划算法7/28/20246Fibonacci sequence分析分析nf(n)= f(n-1)+ f(n-2)n =2f(n-2)+ f(n-3)n =3f(n-3)+2f(n-4)n =5f(n-4)+3f(n-5)凹行宋该织题箭哨漳勒缨胳仅起卵窗碎寻椽劳痢吃恕强呐促苟寅并峨月允动态规划算法动态规划算法7/28/20247二项式系数的计算二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形有效计算上式的方法是按行构造帕斯卡三角形测挖燥缔囱压秦躬隐阁苗续件吉尘贡荷铺蚜椅刮凭篱芽懦扔债跃屿荐膜请动态规划算法动态规划算法7/28/20248What is dynam
8、ic programming什么是动态规划？什么是动态规划？n当子问题发生当子问题发生重叠重叠时时, 分治法做了很多不必要的分治法做了很多不必要的工作工作重复对重叠的子问题进行求解重复对重叠的子问题进行求解. n动态规划算法对每个子问题求解一次动态规划算法对每个子问题求解一次, 然后将结然后将结果保存在一张表里面果保存在一张表里面, 这样可以避免每个已求解这样可以避免每个已求解子问题的重复计算子问题的重复计算. n对于对于Fibonacci序列序列, 一个明显的方法是从一个明显的方法是从f(1)开开始自底向上地计算到始自底向上地计算到f(n), 只需要只需要 (n)时间和时间和 (1)空间空间
9、. n和前面的方法相比和前面的方法相比, 可以很大程度降低时间复杂可以很大程度降低时间复杂度度. 蚤服扼餐狄吵储毯迟佑罗迷菏渠睡穿滓竟递秒根谤享天针缠划怨晦啼户淆动态规划算法动态规划算法7/28/20249The longest common subsequence problem最长公共子序列问题最长公共子序列问题n在字母表在字母表 上上, 分别给出两个长度为分别给出两个长度为n和和m的字符的字符串串A和和B, 确定在确定在A和和B中最长公共子序列的长度中最长公共子序列的长度. q这里这里A=a1a2.an的子序列的一个形式为的子序列的一个形式为ai1ai2.aik的的字符串字符串, 其中每
10、个其中每个ij在在1到到n之间之间, 并且并且1 i1i2.ik nn蛮力法蛮力法: 列举列举A所以的所以的2n个子序列个子序列, 对于每一子对于每一子序列在序列在 (m)时间内来确定它是否也是时间内来确定它是否也是B的子序列的子序列. q很明显很明显, 此算法的时间复杂的为此算法的时间复杂的为 (m*2n). 痹坝锻蔑柞刁粥纯几涧酪仗泽唱遮屁侈漠哀钉雍然待酌燥眠帮毖扔群酒勇动态规划算法动态规划算法7/28/202410递推公式递推公式n为了使用动态规划技术为了使用动态规划技术, 首先推导一个求最长首先推导一个求最长公共子序列长度的递推公式公共子序列长度的递推公式. q令令A=a1a2.an和
11、和B=b1b2.bmq令令Li, j表示表示a1a2.ai和和b1b2.bj的最长公共的最长公共子序列的长度子序列的长度(i, j可能是可能是0, 此时此时a1a2.ai和和b1b2.bj中至少一个为空中至少一个为空). 可得如下结论：可得如下结论：骏暇饵椒尘樊暂诀鱼藩吊哺绳盘刘氏竟驭愤给姆氢属赛封窟鸽刮仔瞬硫媳动态规划算法动态规划算法7/28/202411递推公式递推公式n观察结论观察结论7.1 如果如果i和和j都大于都大于0, 那么那么 q若若ai=bj, Li, j=Li-1, j-1+1q若若ai bj, Li, j=maxLi, j-1, + Li-1, jn可得如下公式：可得如下公
12、式：哼鞍遍阂靛伞废庞二企蹄宫墓匹柄执蚤辨芜昏炸看啮辞鸿脱骡痴留书反贸动态规划算法动态规划算法7/28/202412n现在可以直接用动态规划技术来求解最长现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对公共子序列问题。对每一对i和和j的值，的值，0 i n，0 j m，我们用一个，我们用一个(n+1)(m+1)表来计算表来计算Li, j的值，只需要用上面的公式的值，只需要用上面的公式逐行地填表逐行地填表L0n, 0m。算法如下：。算法如下：紊橙岭蜗天哲迹荣蛋虾甘痛宋俭耙奇谴哩锈治锥羞问骨亥嗓链拙唆望敏帽动态规划算法动态规划算法7/28/202413Algorithm 7.1 LCSI
13、nput: Two strings A and B of length n and m, respectively, over an alphabet Output: The length of the longest common subsequence of A and B 1. for i0 to n 2. Li, 00 3. end for 4. for j0 to m 5. L0, j0 6. end for 俐刚墒凳穿叫捎嗡屉滨嘲橡瑟治澡卯钉撵劝缎授写星设院跋绑庸该杂螺怕动态规划算法动态规划算法7/28/202414 7. for i1 to n 8. for j1 to m 9.
14、 if ai=bj then Li, jLi-1, j-1+1 10. else Li, jmaxLi, j-1, Li-1, j 11. end if 12. end for 13. end for 14. return Ln, m梳屋途投霉囚济擎吭荤毗蛔比策驻幂燎秉袋跪之幅妨钝怔絮钎蔬坎瓤功核动态规划算法动态规划算法7/28/202415n定理定理7.1 最长公共子序列问题的最长公共子序列问题的最优解能够在最优解能够在 (nm)时间和时间和 (minm, n) 空间内得到空间内得到. n？销瘤架惹既夏辛苦故停关财文气觉撒渝斗院冀狡漂汉谣嚣畴蕉覆婴跌册踩动态规划算法动态规划算法7/28/20
15、2416A=“xyxxzxyzxy” B=“zxzyyzxxyxxz”01z2x3z4y5y6z7x8x9y10x11x12z000000000000001x00111111111112y00112222222223x00112223333334x00112223444445z01122233444456x01222234445557y01223334455558z01233344455569x012333455566610y0123444556666图图7.1 最长公共子序列问题的一个例子最长公共子序列问题的一个例子钩鲍怯鲜附畸颧粮辊赛右寄釜亏筑砖屋琳垃墟翰熏裕疼廖套恍汇舆游凋玫动态规划算法
16、动态规划算法7/28/202417Algorithm 7.1pro LCS 1. for i0 to n 2. Li, 00 3. end for 4. for j0 to m 5. L0, j0 6. end for 7. for i1 to n 8. for j1 to m 9. if ai=bj then Li, jLi-1, j-1+1, bi, j” 砧炼忱茁召秘柠栅慕衫脑哟铱簇攒拔挺样补犬掳藩甄堤狠籽弯峙曳捐盖戮动态规划算法动态规划算法7/28/202418 10. else 11. if Li-1, j Li, j-1 then 12. Li, jLi-1, j, bi, j”
17、” 13. else 14. Li, jLi, j-1, bi, j” 15. end if 16. end if 17. end for 18. end for 19. return Ln, m and bn, m序茅樊吸等祟蚌滴乓等蓄沁凝倔茨管蒋厩祥肄丢述牌饵赞烙栖屈豁谴萧议动态规划算法动态规划算法7/28/202419print-LCS(b, A, i, j)1. if i=0 or j=0 then return2. if bi, j= ” then3. print-LCS(b, A, i-1, j-1)4. print ai5. else6. if bi, j= ” ” then p
18、rint-LCS(b, A, i-1, j)7. else print-LCS(b, A, i, j-1)8. end if乏抿其惕饰逛多氮衅痔帚充颇袋忿一刽屯越啦洲莹矿汹宋颗云刑卒急儒啤动态规划算法动态规划算法7/28/202420坍磷澡搜赊垃央泪宠厘尼世裁酗脱租镭询燥妇桃擅夏寂州拘胜筏芦挠镇维动态规划算法动态规划算法7/28/202421算法的改进算法的改进n在算法在算法lcs和和print-LCS中中, 可进一步将数组可进一步将数组b省省去去. 事实上事实上, 数组元素数组元素Lij的值仅由的值仅由Li-1j-1, Li-1j和和Lij-1这这3个数组元素的值所确个数组元素的值所确定定.
19、 对于给定的数组元素对于给定的数组元素Lij, 可以不借助于可以不借助于数组数组b而仅借助于而仅借助于L本身确定本身确定Lij的值是由的值是由Li-1j-1, Li-1j和和Lij-1中哪一个值所确中哪一个值所确定的定的. 峨讨詹粉龚中勒秒枢右轿蜜瞎脾抨汪改证檄藕拍截击徒坯娃夺胚吉厢杀菜动态规划算法动态规划算法7/28/202422算法的改进算法的改进n如果只需要计算最长公共子序列的长度如果只需要计算最长公共子序列的长度, 则算则算法的空间需求可大大减少法的空间需求可大大减少. 事实上事实上, 在计算在计算Lij时时, 只用到数组只用到数组L的第的第i行和第行和第i-1行行. 因此因此, 用用
20、2行的数组空间就可以计算出最长公共子序行的数组空间就可以计算出最长公共子序列的长度列的长度. 进一步的分析还可将空间需求减至进一步的分析还可将空间需求减至O(min(m, n). 建迹撬耙第做吊襟鸥萝报脱呀外金陕减钩肉泰缘脑酥钠析杜淌拦诫方探芳动态规划算法动态规划算法7/28/202423Matrix chain multiplication矩阵链相乘矩阵链相乘n设有设有4个矩阵个矩阵A, B, C, D, 它们的维数分别是它们的维数分别是A:50 10 B:10 40 C:40 30 D:30 5, 共有共有5种加种加括号的方式：括号的方式：n(A(BC)D) q乘法次数乘法次数: 1600
21、0n(A(B(CD) q乘法次数乘法次数: 10500n(AB)(CD) q乘法次数乘法次数: 36000n(AB)C)D) q乘法次数乘法次数: 87500n(A(BC)D) q乘法次数乘法次数: 34500潜截苞言捎雇咀胺麓禽巍祷倒欠黑雹乘容菠旺了椅缮盂洁补搀茸钵妈举虎动态规划算法动态规划算法7/28/202424Matrix chain multiplication矩阵链相乘矩阵链相乘n一般情况下一般情况下, n个矩阵链个矩阵链M1M2.Mn相乘的耗费相乘的耗费, 取决于取决于n-1个乘法执行的顺序个乘法执行的顺序(结合方式结合方式). n蛮力算法蛮力算法: 计算出每一种可能顺序的数量乘
22、法次计算出每一种可能顺序的数量乘法次数数. n时间复杂度是：时间复杂度是： 算法复杂度分析：算法复杂度分析：对于对于n个矩阵的连乘积个矩阵的连乘积, 设其不同的计算次序为设其不同的计算次序为P(n). 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于可以得到关于P(n)的递推式如下：的递推式如下：碉歇颅权橇特受贱出兑屁桅酶灾季蛤榆棋琵负绅淫温寥醛昼潜违茶鹊袱位动态规划算法动态规划算法7/28/202425n假设我们有假设我们有n+1维数维数r1, r2, ., rn+1, 这里这里ri和和ri
23、+1分别是矩阵分别是矩阵Mi的行数和列数的行数和列数, 1 i n. n我们将用我们将用Mi, j记记MiMi+1.Mj的乘积的乘积, 我们还假我们还假设链设链Mi,j的乘法的最小耗费用数量乘法的次数的乘法的最小耗费用数量乘法的次数来度量来度量, 记为记为Ci, j. n对于给定的一对索引对于给定的一对索引i和和j, 1 i 0) return mij; if (i = j) return 0; int u = lookupChain(i+1, j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lookupChain(i,
24、 k) + lookupChain(k+1, j) + pi-1*pk*pj; if (t 0时时, 有如下结论有如下结论:n观察结论观察结论7.2 Vi, j是下面两个量的最大值是下面两个量的最大值qVi-1, j: 仅用最优的方法取自仅用最优的方法取自u1.ui-1的物的物品去装体积为品去装体积为j的背包所得到的最大价值的背包所得到的最大价值.qVi-1, j-si+vi:用最优的方法取自用最优的方法取自u1.ui-1的的物品去装体积为物品去装体积为j-si的背包所得到的最大价值加的背包所得到的最大价值加上物品上物品ui的价值的价值.焕癌句距析堰郧蚂铁乓撼奏戍觉揣皆惕邓器疚角任痘做骂腹泼猫
25、郊狼舅沏动态规划算法动态规划算法7/28/202443背包问题的递推公式背包问题的递推公式n递推公式如下：递推公式如下：香牙刃幂时谩罚促因哩企伤灼置辅祭页惋载宣诬约傀卡玻朋次啮撑静怒磷动态规划算法动态规划算法7/28/202444Algorithm 7.4 KNAPSACKInput: A set of items U=u1.un with sizes s1, ., sn and values v1, ., vn and a knapsack capacity COutput: The maximum value of the problem 1. for i0 to n 2. Vi, 00
26、3. end for 4. for j0 to C 5. V0, j0 6. end for 7. for i1 to n 8. for j1 to C 9. Vi, jVi-1, j 10. if si j then Vi, jmaxVi, j, Vi-1, j-si+vi 11. end for 12. end for 13. return Vn, C贪逊酿民跑鲸力雨专铝喀蛙拧撰笑速纱衷腺凋异抨绦冕绿女倘睫啦诵夷蚕动态规划算法动态规划算法7/28/202445分析分析nTime: (nC)nSpace: (C)nBut it is a pseudopolynomial time algor
27、ithm!n当背包容量当背包容量c很大时很大时, 算法需要的计算时间较多算法需要的计算时间较多. 例如例如, 当当c2n时时, 算法需要算法需要(n2n)计算时间计算时间. 耶叠换斯蓖槛掷昌濒徊派古祟鸵管儡妨练遗详交衍蹲昼济颠迅鄙澡纪暖扒动态规划算法动态规划算法7/28/202446C=9 s1=2 s2=3 s3=4 s4=5 v1=3 v2=4 v3=5 v4=7012345678900000000000100333333332003447777730034578991240034578101112图图7.5 背包问题算法的一个例子背包问题算法的一个例子挥磁汁契膏妖登西勤远棘句残椅涤轴胖摹辅止斜徽幻阔踩焙俺寞菲剿酣吾动态规划算法动态规划算法7/28/202447Homework7.57.77.117.22 庆释航竿涧撒纫段愧演姑淄钙台睫鞠君丧照羞鲍埂氰你审乎煎却邪惑黔掂动态规划算法动态规划算法7/28/202448
