《算法合集之《浅谈贪心思想在动态规划中的应用》.doc》由会员分享，可在线阅读，更多相关《算法合集之《浅谈贪心思想在动态规划中的应用》.doc（14页珍藏版）》请在金锄头文库上搜索。
1、2006年全国信息学冬令营讲座贪婪的动态规划浅谈贪心思想在动态规划中的应用浙江省绍兴县柯桥中学 黄劲松【关键字】贪心法，动态规划，状态，时间复杂度【摘要】贪心法和动态规划是信息学竞赛中的两种常用算法，本文着重讨论了贪心的思想是如何巧妙的运用到动态规划的解题中的。全文分三个部分，首先讨论了贪心思想运用到动态规划解题中的可行性和必要性，然后就贪心思想在动态规划中的两种基本应用分别做了举例说明，最后总结全文。【正文】引言贪心法和动态规划是信息学竞赛中的常用经典算法，而当某些问题的模型过于复杂的时候，由于状态过于庞大、转移困难等一系列的问题，常规的动态规划难于甚至无从下手。而在这个时候，巧妙的使用贪心
2、思想，将其融入到动态规划的解题中，动态规划便焕发出了新的光彩。1、贪心思想运用到动态规划中的必要性和可行性动态规划的原理是：在求解问题的过程中，通过处理位于当前位置和所达目标之间的中间点来找到整个问题的解。整个过程是递归的，每到一个新的中间点都是已访问过的点的一个函数。适合于动态规划法的标准问题必须具有下列特点：l 1、整个问题的求解可以划分为若干个阶段的一系列决策过程。l 2、每个阶段有若干可能状态。l 3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。l 4、在任一个阶段，最佳的决策序列和该阶段以后的决策无关。l 5、各阶段状态之间的转换有明确定义的费用在实际的动态规划的解题中
3、，面临着两大困难：一是不知道题目是否可以用动态规划求解；二是即使能够想到用动态规划来求解，但是因为种种因素，算法的效率并不乐观。这个时候，使用贪心思想分析问题，可以让你在山穷水尽疑无路的时候，柳暗花明又一村。在运用贪心思想的时候，主要是分析出问题的一些本质，或者分析出低效算法的一些冗余。当然，我们要根据题目的特殊信息，合理的运用好贪心思想，才能帮助动态规划发挥其强大的功效。下文就贪心思想如何解决动态规划面临着的这两大困难分别做了举例说明。2、贪心思想在动态规划中的应用一： 确立状态动态规划当中，状态的确立是重点，而在实际的解题过程中，状态的信息往往是隐含的，这个时候，合理的运用贪心思想，可以迅
4、速的从繁芜丛杂的问题背景中巧妙地抽象出状态。我们通过下面的例子来看一看，贪心思想是如何帮助动态规划确立状态的。例题一 青蛙的烦恼 经典问题题目大意：池塘里有n片荷叶（1n1000），它们正好形成一个凸多边形。按照顺时针方向将这n片荷叶顺次编号为1，2，n。有一只小青蛙站在1号荷叶上，它想跳过每片荷叶一次且仅一次（它可以从所站的荷叶跳到任意一片荷叶上）。同时，它又希望跳过的总距离最短。请你编程帮小青蛙设计一条路线。算法分析：问题似乎是一个N个点的TSP问题 经典的旅行商问题，NP问题，但却又是一个特殊的TSP问题题目中说明，N个点围成了一个凸多边形！如何合理的运用这个特殊的条件成为了解题的关键。
5、原始的问题模型很容易使人放弃动态规划，因为状态难以抽象，状态转移也无从着手。但如果从问题特征出发，灵活运用贪心策略，却能巧妙的设计出一种高效的动态规划算法！先介绍一下TSP问题的一种局部搜索算法2-最优算法。它从随机的一种可选路径出发（称为路径T），试图去改善它。我们在T中寻找出2条不相交的边，移动这两条边，如果新产生的路径比原来的路径优秀，那么就移动这两条边。这种移动称为2-交换。如图所示：可以根据这个TSP问题的局部最优算法容易想到，原问题的最短路线中显然不存在相交的边，否则一定可以将这条路线“改进”成一条更优秀的路线。根据上述结论可以知道：从1出发的第一步只能到2或者n，否则产生的路线一
6、定不会是最优的。因此，原问题的模型变成了：寻找以1为起点，遍历凸多边形1.N中的顶点一次且一次的最短路线。根据上述结论可以知道，如果离开1到达2，接下来的任务是寻找以2为起点，遍历凸多边形2.N中的顶点一次且一次的最短路线；如果离开1到达N，接下来的任务是寻找以N为起点，遍历凸多边形2.N中的顶点一次且一次的最短路线。这是一个递归的过程！因此，状态可以这样表示：fi,L,0表示从i出发，遍历i.i+L-1中的顶点一次且一次的最短距离；fi,L,1表示从i+L-1出发，遍历i.i+L-1中的顶点一次且一次的最短距离。状态转移方程是：fi,L,0 = mindist(i,i+1)+fi+1,L-1
7、,0,dist(i,i+L-1)+fi+1,L-1,1fi,L,1 = mindist(i+L-1,i+L-2)+fi,L-1,1,dist(i+L-1,i)+fi,L-1,0fi,1,0 = 0, fi,1,1 = 0其中dist(a,b)表示第a个结点和第b个结点之间的欧几里德距离。问题的答案是f1,n,0时间复杂度O(n2)。本题小结：本题中运用贪心思想合理的分析出了问题最优解的一些特点，从而能够根据问题中的特殊条件确立出动态规划的状态，把看似NP的问题，用动态规划巧妙的解决了。例题二 The Horse Racing 上海赛区2004年ACM比赛试题题目大意：中国古代的历史故事“田忌赛
8、马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马（N2000），每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？算法分析：这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马A和齐王的B之间，如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为200的边。然而我们知道，二分图的最佳匹配算法的复杂度很高，无法满足N2000的要求。我们不妨用贪心思
9、想来分析一下问题。因为田忌掌握有比赛的“主动权”，他总是根据齐王所出的马来分配自己的马，所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设，我们归纳出如下贪心策略： 1、如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。 2、如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。 3、如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话，可以选择打平或者用最差的马输掉比赛。第一个贪心策略的证明：此时田忌的所有马都赢不了齐王的马，所以无论用最慢马去输还是用最快的马去输都同样是输，而处于贪心的思想，
10、我们应该保留相比之下更强的马，因此用最慢的马去输一定不会比用别的马去输来得劣，所以这是最优策略。证毕。第二个贪心策略的证明：假设现在齐王剩下的最强的马是A，田忌剩下的最强的马是B，如果存在一种更优的比赛策略，让B的对手不是A，而使得田忌赢更多的钱的话，那么设此时A的对手是b，B的对手是a：1、 若bA，则有Ba，bA。这个结果和BA，ba是相同的。2、 若aa，bA。这个结果不如BA，ba来得优秀。3、 若baA，则有Ba，bA。这个结果和BA，ba是相同的。由此可知，交换各自对手后，一定不会使得结果变劣，那么假设是不成立的。证毕。第三个贪心策略的证明：因为田忌最快的马也只是和齐王的马打平，那
11、么田忌只能选择平或输，选择平的话，当然只能用最快的马去平了；选择输的话当时是用最慢的马去输来得值得，这和第一个贪心策略的思路是一样的。证毕。我们发现，第三个贪心策略出现了一个分支：打平或输掉。如果穷举所有的情况，算法的复杂度将比求二分图最佳匹配还要高；如果一概而论的选择让最强的马去打平比赛或者是让最差的马去输掉比赛，则存在反例： 光是打平的话，如果齐王马的速度分别是1 2 3，田忌马的速度也是1 2 3，每次选择打平的话，田忌一分钱也得不到，而如果选择先用速度为1的马输给速度为3的马的话，可以赢得200两黄金。 光是输掉的话，如果齐王马的速度分别是1 3，田忌马的速度分别是2 3，田忌一胜一负
12、，仍然一分钱也拿不到。而如果先用速度为3的马去打平的话，可以赢得200两黄金。虽然因为第三个贪心出现了分支，我们不能直接的按照这种方法来设计出一个完全贪心的方法，但是通过上述的三种贪心策略，我们可以发现，如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。有了这个信息之后，动态规划的模型也就出来了！设fi,j表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。状态转移方程如下：其中gi,j表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和
13、齐王的第j匹马赛跑所能取得的盈利，胜为200，输为200，平为0。本题小结：虽然本题存在直接贪心的方法，不过它可以作为一个例子告诉大家，合理的运用贪心策略，分析出问题的一些本质之后，一些看似不能用动态规划做的题目便可以巧妙的确立出状态，继而可以用动态规划来求解。3、贪心思想在动态规划中的应用二： 优化算法一些动态规划的题目虽然容易确立出正确的状态以及轻松的写出状态转移方程。但是直序的算法往往效率不高。而贪心历来都是与“高效”一词分不开的。所以，合理的在动态规划中运用贪心思想，能够让原本效率低下的算法获得“重生”！例题三 石子归并 经典问题题目大意：在一个操场上摆放着一排n（n1000）堆石子。
14、现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的花费。试编程求出将n堆石子合并成一堆的最小花费。算法分析：这是一道经典的动态规划问题，用mi,j表示第i堆石子合并到第j堆石子所需的最小花费，wi,j表示第i堆石子到第j堆石子的石子总数。状态转移方程如下：上述算法的状态总数为O(n2)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n3)。显然，这个简单易懂的算法的过于低效了，我们需要进行优化。我们尝试寻找动态规划中的冗余。不难发现，在枚举决策k的时候，上述算法实在是太盲目了，因为当有一些k如果作为
15、决策点，肯定得不到最优解，我们可以不去枚举他们。这是一种贪心的思想！令si,j表示使得mi,j取到最小时的k。可以用四边形不等式 当函数wi,j满足时，称w满足四边形不等式。证明出si,jsi,j+1si+1,j+1, ij这说明mi,j的决策单调。于是状态转移方程可以变成如下的形式：整体的时间复杂度则变为了： 本题的相关证明详见参考文献3本题小结：决策单调的动态规划是一类很常见的问题，例如NOI2004的hut就是一道不错的根据决策单调的性质来优化动态规划的题目。根据决策单调的性质，我们避免了一些无用的决策枚举，从而使得算法的复杂度降了级，这是贪心思想的经典体现。例题四 The Lost House 北京赛区2004年ACM比赛试题题目大意：蜗牛的房子遗失在了一棵树的某个叶子结点上，它要从根结点出发开始寻找它的房子。有一些中间结点可能会住着一些虫子，这些虫子会告诉蜗牛它的房子是否在以这个中间结点为根的子树上，
