信息学竞赛常用算法思想
中华IT学习网doc.guandang.net 官方总站:圣才学习网doc.guandang.net
动态规划
动态规划是本书介绍的五种算法设计方法中难度最大的一种,它建立在最优原则的基础上。采用动态规划方法,可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后,本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。
3.1 算法思想
和贪婪算法一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。
例3-1 [最短路经] 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点最短路径,即选择此路径所经过的各个节点。第一步可选择节点2,3或4。假设选择了节点要求解的问题变成:选择一条从3到5的最短路径。如果3到513和5的路径也不会是最短的。例如,若选择的子路径(非最短路径)是3,2,5 (1到5的路径为1,3,2,5 (耗费为11 ),这比选择最短子路径3,4,5而得到的1到53,4,5 (耗费为9) 耗费更大。
所以在最短路径问题中,假如在的第一次决策时到达了某个节点v 是怎样确定的,此后选择从v 到d 的路径时,都必须采用最优策略。
例3-2 [0/1背包问题] 考察1 3 . 4节的0 / 1x1 .. xn的值。假设按i = 1,2,.,n 的次序来确定xi 的值。如果置x1 物品2,3,.,n),背包容量仍为c 的背包问题。若置1c-w1 的问题。现设r {c,c-w1 } 为剩余的背包容量。
在第一次决策之后,r 时的决策。不管x1 是0或是1,[x2 ,.,xn ] [y2,.,yn ],因而[x1,y2,.,yn ]是一个更好的方案。
假设n=3, w=[100,14,10], c= 11 6。若设x1 = 1,则在本次决策之后,可用的背包容量为r= 116-100=16 。[x2符合容量限制的条件,所得值为1 5,但因为[x2,x3 ]= [1,0] ,因此[x2,x3 ] = [ 0,1] 并非最优策略。即x= [ 1,0,1] 可改进为x= [ 1,1,0 ]1 = 0,则对于剩下的两种物品而言,容量限制条件为11 6。总之,如果子问题的结果[x2,[x1,x2,x3 ]也不会是总体的最优解。
例3-3 [ $ 1 0 0$ 2 0;而对于路经亚特兰大的旅客,从亚特兰大到芝加哥的费用仅为$ 2 0。从洛$ 1 0 0。而使用直飞方式时,从洛杉矶到纽约的花费为$ 2 0 0。不过,从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约,其总花费为$ 1 4 0(在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径:亚特兰大-芝加哥-纽约)。
如果用三维数组(t a g,起点,终点)表示问题状态,其中t a g为0表示转飞, t a g为1表示其他情形,那么在到达亚特兰大后,状态的三维数组将变为( 0,亚特兰大,纽约),它对应的最优路径是经由芝加哥的那条路径。
当最优决策序列中包含最优决策子序列时,可建立动态规划递归方程( d y n a m i c -programming recurrence equation),它可以帮助我们高效地解决问题。
例3-4 [0/1背包] 在例3 - 2的0 / 1背包问题中,最优决策序列由最优决策子序列组成。假设f (i,y) 表示例1 5 - 2中剩余容量为y,剩余物品为i,i + 1,.,n 时的最优解的值,即:和利用最优序列由最
第6讲 动态规划专题讲座 35页 1财富值 acm系列讲座-动态规划 39页 免费 信息学竞赛常用的算法思想... 19页 10财富值 石少俭算法讲座1动态规划 49页 1财富...
动态规划是信息学竞赛中的两种常用算法,本文着重讨论了贪心的思想是如何巧妙的...-1- 2006 年全国信息学冬令营讲座 下文就贪心思想如何解决动态规划面临着的这...
信息学竞赛常用的算法思想... 19页 10财富值 常用算法(八)——动态规划......动态规划是本书介绍的五种算法设计方法中难度最大的一种,它建立在最优原则的...
第6讲 动态规划专题讲座 35页 1财富值 acm系列讲座-动态规划 39页 免费 信息学竞赛常用的算法思想... 19页 10财富值喜欢此文档的还喜欢 第二节 动态规划 4...
信息学竞赛常用算法!!! 算法大全 一、数论算法 1....(1,n); } 思路三:可使用动态规划求解 USACO1.2...G.基数排序 思想:对每个元素按从低位到高位对每一...
算法合集之《浅谈数形结合思想在信息学竞赛中的...动态规划解题...9 小结......赛中的项链,使用 Raney 引理都是最简单的方法之一。2 用几何图形辅助思考...
【关键字】 贪心法,动态规划,状态,时间复杂度【摘要】贪心法和动态规划是信息学竞赛中的两种常用算法,本文着重讨论了贪心的思想是如何巧妙的运用到动态规划的解题...
部分贪心 【正文】 正文】 引言 贪心在信息学竞赛中,是一种非常重要的思想。 ...状态的决策中采用搜索或者动态规划这类可以保证正确性的算法来处理, 而对于第 2...
是信息学竞赛中选手必须熟练掌握的一种算法,他以其...编辑本段 基本思想动态规划算法通常用于求解具有某种...编辑本段 作用在编程中常用解决最长公共子序列问题...
各类信息学竞赛的重要考察内容。 ? 不同于其他算法...? 初学者不易掌握其思想,需要做大量的题。 ? ...动态规划的常见模型及例题 4 引例1:数字三角形【...
热门文档