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

《国家集训队2006论文集 黄劲松》由会员分享，可在线阅读，更多相关《国家集训队2006论文集 黄劲松（22页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、rse Racing收益为200收益为0“田忌出马不是出最强的，就是出最弱的” 用fi,j表示齐王出了i匹较强的马和田忌的j匹较强的马，i -j匹较弱的马比赛之后，田忌所能够得到的最大盈利。 其中gi,j表示齐王和田忌的马分别按由强到弱的顺序排 序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得 的盈利，胜为200，负为-200，平为0。例二 The Horse RacingO(n2)小结1抛弃了原本直观而低效的算法结合贪心思想分析问题用合理的假设得到了“田忌出马不是出最强，就 是出最弱”的信息因此得知可以用动态规划求解且确立出动规状态贪心思想在动态规划中的应用二： 优化算法一些题目虽然容易确

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

6、叶结点2、4、5上 在结点3上住着一只虫子，它会告诉蜗 牛，房子是否在以3为根的子树上这种走法没有充分发挥虫子在这里的作用！例四The Lost House(3+2+4)/3 = 3Worm Said : No!Worm Said : Yes!例四The Lost House不难分析出本题是用树型动态规划来求解。 Fai表示蜗牛的房子在i为根的子树上的期望步数和 Fbi表示蜗牛的房子不在i为根的子树上的期望步数 和（也就是遍历该子树需要的时间，如果i处有虫子 ，那么Fbi=0） 用Leavesi 表示i为根的子树上叶子节点的数目。 问题的解答就是Fa根结点/Leaves根结点。如果结点u有k个

7、儿子,我们按照S1Sk进行访 问，Fau的计算方式是： Fau = 0; Fbu = 0; for i = 1 to k do beginFau = Fau + (Fbu + 1) LeavesSi + FaSi;Fbu = Fbu + FbSi + 2; end;Fbu的值与访问顺序无关例四 The Lost House 问题的关键是如何决定儿子的访问顺序 一种直观的方法是枚举所有可能访问顺序 ，复杂度是O(nk!)，实在是很低效 上述算法存在冗余, 我们再用一次动态规划 的话，可以将复杂度降为O(n2kk)，勉强可 以接受了另一个结论：如果A一定放在B前，B一定放在C 前，可以推导出A一定

8、放在C前。例四 The Lost House对交换前后的Fau值做差 这只跟元素v和v+1本身的信息有关！ 因此如果交换后的值优秀的话，那么v+1一定放 在v的前面O(nklog2k )12kvv+1。运用贪心思想分析问题u元素之间存在可比性，且可比 性存在着传递性，因此可以确 定出一个全序关系此时FaS1k和FbS1k的值都已知，Fau的值待定我们考虑一种访问顺序中的两个相邻元素v和v+1小结2从原始的动态规划入手运用贪心思想除去算法中的冗余最终达到优化算法的目的回顾与总结贪心思想在动态规划中的两种简单应用确立状态优化算法合理的运用题目中隐含的 特殊信息回顾与总结勇于探索大胆创新举一反三Thank you for listening!