国家集训队2006论文集 黄劲松

《国家集训队2006论文集 黄劲松》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贪婪的动态规划——浅谈贪心思想在动态规划中的应用绍兴县柯桥中学黄劲松引言转移困难在动态规划的解题中我们面临着两大困难1、不知道是否可以用动态规划求解2、直观的动态规划算法过于低效在这个时候，巧妙的使用贪心思想，将其融入到动态规划中，动态规划便焕发出了新的光彩状态过于庞大目录贪心思想在动态规划中的应用确立状态[例一]青蛙的烦恼（详见论文）[例二]TheHorseRacing优化算法[例三]石子归并（详见论文）[例四]TheLostHouse贪心思想在动态规划中的应用一：确立状态动态规划当中，状态的确立是重点而在实际的解题过程中，状态信息往往是隐含的

2、这个时候，合理的运用贪心思想，可以迅速的从繁芜丛杂的问题背景中巧妙地抽象出状态[例二]TheHorseRacing齐王和田忌各派出N匹马（N≤2000）每匹马都有一个固定的速度值每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱请你扮演一下孙膑，帮助田忌赢最多的钱时间复杂度过大，无法满足要求[例二]TheHorseRacing这个问题很显然可以转化成一个二分图最佳匹配的问题把田忌的马放左边，把齐王的马放右边如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为-200的边。田忌齐王2

3、000-200[例二]TheHorseRacing运用贪心思想分析问题：田忌掌握有比赛的“主动权”，他总是根据齐王所出的马来分配自己的马去对抗齐王的马可以假设齐王按照马的强弱顺序由强到弱出马齐王最强的马田忌最强的马用田忌最差的马去输给齐王最强的马输给能赢用田忌最强的马去战胜齐王最强的马战平用田忌最强的马去打平齐王最强的马或者用田忌最差的马去输给齐王最强的马最强的马战平时，单一的贪心策略存在反例光是打平比赛田忌的马123齐王的马123[例二]TheHorseRacing收益为0收益为200最强的马战平时，单一的贪心策略存在反例光是输掉比赛田忌的马2

4、3齐王的马13[例二]TheHorseRacing收益为200收益为0“田忌出马不是出最强的，就是出最弱的”用f[i,j]表示齐王出了i匹较强的马和田忌的j匹较强的马，i-j匹较弱的马比赛之后，田忌所能够得到的最大盈利。其中g[i,j]表示齐王和田忌的马分别按由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为200，负为-200，平为0。[例二]TheHorseRacingO(n2)小结1抛弃了原本直观而低效的算法结合贪心思想分析问题用合理的假设得到了“田忌出马不是出最强，就是出最弱”的信息因此得知可以用动态规划求解且

5、确立出动规状态贪心思想在动态规划中的应用二：优化算法一些题目虽然容易确立出状态以及轻松的写出状态转移方程，但是直观上的算法往往效率不高而贪心历来是与高效一词密不可分的运用好贪心思想能够使原来效率低下的算法得到重生[例四]TheLostHouse蜗牛从根结点出发开始寻找它遗失在某个叶子结点的房子一些中间结点上住着的虫子会告诉蜗牛它的房子是否在以这个点为根的子树上房子遗失在每个叶子结点的概率都是相等的求蜗牛找到房子的最小数学期望步数（走过一条边算作一步）树上的结点个数n最多为1000，每个结点的分叉数k最多为8。[例四]TheLostHouse(1+

6、4+6)/3=11/3蜗牛从根结点1出发开始寻找它的房子它的房子可能遗失在叶结点2、4、5上在结点3上住着一只虫子，它会告诉蜗牛，房子是否在以3为根的子树上这种走法没有充分发挥虫子在这里的作用！[例四]TheLostHouse(3+2+4)/3=3WormSaid:No!WormSaid:Yes![例四]TheLostHouse不难分析出本题是用树型动态规划来求解。Fa[i]表示蜗牛的房子在i为根的子树上的期望步数和Fb[i]表示蜗牛的房子不在i为根的子树上的期望步数和（也就是遍历该子树需要的时间，如果i处有虫子，那么Fb[i]=0）用Leave

7、s[i]表示i为根的子树上叶子节点的数目。问题的解答就是Fa[根结点]/Leaves[根结点]。如果结点u有k个儿子,我们按照S[1]..S[k]进行访问，Fa[u]的计算方式是：Fa[u]=0;Fb[u]=0;fori=1tokdobeginFa[u]=Fa[u]+(Fb[u]+1)×Leaves[S[i]]+Fa[S[i]];Fb[u]=Fb[u]+Fb[S[i]]+2;end;Fb[u]的值与访问顺序无关[例四]TheLostHouse问题的关键是如何决定儿子的访问顺序一种直观的方法是枚举所有可能访问顺序，复杂度是O(nk!)，实在是很低效

8、上述算法存在冗余,我们再用一次动态规划的话，可以将复杂度降为O(n2kk)，勉强可以接受了另一个结论：如果A一定放在B前，B一定放在C前