内蒙古大学《算法与数据结构》讲义15动态规划
25页1、下载第1 5章动 态 规 划动态规划是本书介绍的五种算法设计方法中难度最大的一种, 它建立在最优原则的基础上。采用动态规划方法,可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后,本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。15.1 算法思想和贪婪算法一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。例15-1 最短路经 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点d= 5的最短路径,即选择此路径所经过的各个节点。第一步可选择节点 2,3或4。假设选择了节点3,则此时所要求解的问题变成:选择一条从 3到5的最短路径。如果3到5的路径不是最短的,则从1开始经过3和5的路径也不会是最短的。例如,若选择的子路径(非最短路径)是 3,2,5 (耗费为9 ),则1到5的路径为1,3,2,5 (耗费为11 ),这比选择最短子
2、路径3,4,5而得到的1到5的路径1,3,4,5 (耗费为9) 耗费更大。所以在最短路径问题中,假如在的第一次决策时到达了某个节点 v,那么不管v 是怎样确定的,此后选择从v 到d 的路径时,都必须采用最优策略。例15-2 0/1背包问题 考察1 3 . 4节的0 / 1背包问题。如前所述,在该问题中需要决定x1 xn的值。假设按i= 1,2,n 的次序来确定xi的值。如果置x1 = 0,则问题转变为相对于其余物品(即物品2,3,n) ,背包容量仍为c 的背包问题。若置x1 = 1,问题就变为关于最大背包容量为c-w1的问题。现设rc,c-w1 为剩余的背包容量。在第一次决策之后,剩下的问题便是考虑背包容量为 r 时的决策。不管x1 是0或是1,x2 ,xn 必须是第一次决策之后的一个最优方案,如果不是,则会有一个更好的方案 y2,yn ,因而x1,y2,yn 是一个更好的方案。假设n=3, w=100,14,10, p=20,18,15, c= 11 6。若设x1 = 1,则在本次决策之后,可用的背包容量为r= 116-100=16 。x2,x3 =0,1 符合容量限制的条件,所得值
3、为1 5,但因为x2,x3 = 1,0 同样符合容量条件且所得值为1 8,因此x2,x3 = 0,1 并非最优策略。即x= 1,0,1 可改进为x= 1,1,0 。若设x1 = 0,则对于剩下的两种物品而言,容量限制条件为 11 6。总之,如果子问题的结果x2,x3 不是剩余情况下的一个最优解,则x1,x2,x3 也不会是总体的最优解。例15-3 航费 某航线价格表为:从亚特兰大到纽约或芝加哥,或从洛杉矶到亚特兰大的费用为$ 1 0 0;从芝加哥到纽约票价$ 2 0;而对于路经亚特兰大的旅客,从亚特兰大到芝加哥的费用仅为$ 2 0。从洛杉矶到纽约的航线涉及到对中转机场的选择。如果问题状态的形式为(起点,终点) ,那么在选择从洛杉矶到亚特兰大后,问题的状态变为(亚特兰大,纽约) 。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约,票价 $ 1 0 0。而使用直飞方式时,从洛杉矶到纽约的花费为$ 2 0 0。不过,从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约,其总花费为$ 1 4 0(在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径:亚特兰大 -芝加哥-纽约) 。如
4、果用三维数组(t a g,起点,终点)表示问题状态,其中 t a g为0表示转飞,t a g为1表示其他情形,那么在到达亚特兰大后,状态的三维数组将变为( 0,亚特兰大,纽约) ,它对应的最优路径是经由芝加哥的那条路径。当最优决策序列中包含最优决策子序列时,可建立动态规划递归方程(d y n a m i c -programming recurrence equation) ,它可以帮助我们高效地解决问题。例15-4 0/1背包 在例1 5 - 2的0 / 1背包问题中,最优决策序列由最优决策子序列组成。假设f (i,y) 表示例1 5 - 2中剩余容量为y,剩余物品为i,i+ 1,n 时的最优解的值,即:和利用最优序列由最优子序列构成的结论,可得到 f 的递归式。f ( 1 ,c) 是初始时背包问题的最优解。可使用( 1 5 - 2)式通过递归或迭代来求解 f ( 1 ,c)。从f (n, * )开始迭式, f (n, * )由(1 5 - 1)式得出,然后由( 1 5 - 2)式递归计算f(i,*) (i=n- 1,n- 2,2 ),最后由(1 5 - 2)式得出f( 1 ,c)。
5、对于例1 5 - 2,若0y1 0,则f ( 3 ,y) = 0;若y1 0,f ( 3 ,y) = 1 5。利用递归式(1 5 - 2) ,可得f (2, y) = 0 ( 0y10 );f(2,y)= 1 5(1 0y1 4);f(2,y)= 1 8(1 4y2 4)和f(2,y)= 3 3(y2 4) 。因此最优解f ( 1 , 11 6 ) = m a x f(2,11 6) ,f(2,11 6 - w1)+ p1 = m a x f(2,11 6) ,f(2,1 6)+ 2 0 = m a x 3 3,3 8 = 3 8。现在计算xi值,步骤如下:若f ( 1 ,c) =f ( 2 ,c),则x1 = 0,否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解,用f (2, c-w1) 表示最优解。依此类推,可得到所有的xi(i= 1n) 值。在该例中,可得出f ( 2 , 11 6 ) = 3 3f ( 1 , 11 6 ),所以x1 = 1。接着利用返回值3 8 -p1=18 计算x2及x3,此时r= 11 6 -w1 = 1 6,又由f ( 2 , 1 6 ) = 1
《内蒙古大学《算法与数据结构》讲义15动态规划》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义15动态规划》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页