极限优化：贪心法、动态规划、状态的时间复杂度揭秘

《算法宝典：浅谈贪心思想在动态规划中的应用》由会员分享，可以在线阅读。 更多相关《算法宝典：浅谈贪心思想在动态规划中的应用》（14页珍藏版）》请在在线教育资源下载分享平台大享图书馆搜索。

1. 2006全国信息学冬令营讲座 - 1 - 贪心动态规划 浅谈贪心思想在动态规划中的应用 黄劲松 浙江省绍兴县柯桥中学 【关键词】 贪心法、动态规划、状态、时间【摘要】 贪心法和动态规划是信息学竞赛中常用的两种算法。 本文重点介绍如何巧妙地将贪心思想运用到动态规划问题求解中。 全文分为三个部分。 首先讨论了贪心思想应用于动态规划问题求解的可行性和必要性，然后举例说明了贪心思想在动态规划中的两个基本应用，最后对全文进行了总结。 【正文】引言 贪心法和动态规划是信息学竞赛中常用的经典算法。 当某些问题的模型过于复杂时，常规动态规划会因状态太大、迁移困难等一系列问题而难以求解。

2.你甚至不知道从哪里开始。 这时贪心法与动态规划方法的异点，通过巧妙地运用贪心思想，并将其融入到动态规划问题的求解中，动态规划焕发出新的辉煌。 1、贪心思想应用于动态规划的必要性和可行性。 动态规划的原理是：在解决问题的过程中，通过处理当前位置与达到的目标之间的中间点来找到​​整个问题的解。 整个过程是递归的，每个新的中间点都是访问过的点的函数。 适合动态规划方法的标准问题必须具备以下特征： 1.整个问题的求解可以分为几个阶段的一系列决策过程。 2. 每个阶段都有几种可能的状态。 3、一个决定会让你从一个阶段的某种状态进入下一阶段的某种状态。 4. 在任何阶段，最优决策序列与后续阶段的决策无关。 5、各阶段状态之间

3. 转换有明确的成本。 在实际的动态规划问题求解中，我们面临两大困难：第一，我们不知道问题是否可以通过动态规划来解决；第二，我们不知道问题是否可以通过动态规划来解决。 第二，即使我们能够想到用动态规划来解决，由于各种因素的影响，算法的效率也不容乐观。 这时，用贪心思维来分析问题，可以帮助你在穷途末路时找到另一个亮点。 使用贪心思维时，主要是分析问题的一些本质，或者分析一些低效算法的冗余。 当然，我们必须根据题目的特殊信息，合理利用贪心思维，才能帮助动态规划发挥其强大的功效。 2006全国信息学冬令营讲座 - 2 - 下面举例说明贪心思维如何解决动态规划面临的两大难题。 2、贪心思想在动态规划中的应用1：建立状态动态

4.在国家规划中，国家的建立是重点，但在实际问题解决过程中，国家信息往往是隐性的。 这时，合理运用贪心思维可以快速识别复杂的问题背景。 巧妙地抽象陈述。 我们通过下面的例子来看看贪心思维是如何帮助动态规划建立状态的。 例1：青蛙的烦恼1 题目大意：池塘里有n片荷叶（），它们正好构成一个凸多边形。 将这n片荷叶按顺时针方向编号为1、2、n。 一号荷叶上站着一只小青蛙，它想在每片荷叶上跳过一次且仅一次（它可以从它所站的荷叶上跳到任何荷叶上）。 同时，它希望将跳过的总距离最小化。 请编程帮助小青蛙设计一条路线。算法分析：问题看起来是一个N点问题

5. TSP问题2，但它是一个特殊的TSP问题。 题目说N个点组成一个凸多边形！ 如何合理利用这一特殊条件成为解决问题的关键。 原来的问题模型很容易让人放弃动态规划，因为状态很难抽象，没有办法启动状态转换。 但如果从问题的特点出发，灵活运用贪心策略，就可以巧妙地设计出高效的动态规划算法！ 首先，我们介绍一下针对TSP问题的局部搜索算法2-最优算法。 它从随机替代路径（称为路径 T）开始并尝试改进它。 我们在 T 中找到 2 条不相交的边并移动这两条边。 如果新生成的路径比原始路径更好，则移动这两条边。 这个举动称为2-swap。如图：根据这个TSP问题

6.很容易想到局部最优算法。 原问题的最短路径显然不存在相交边。 否则的话，这条路线绝对可以“改进”成更好的路线。 1 经典问题 2 经典旅行商问题、NP问题 2006年全国信息学冬令营讲座 - 3 - 根据以上结论，我们可以知道：第一步从1开始只能走到2或n，否则生成的路线不会是最优的。 因此，原问题的模型就变成：从1开始，一次又一次地遍历凸多边形1N中的顶点，找到一条最短路径。根据上面的结论，我们可以知道，如果离开1，到达2，那么接下来任务是找到从2开始，一次又一次遍历凸多边形2N中顶点的最短路线； 如果离开1到达N，接下来的任务就是找到从2出发的最短路径，N为起点，遍历凸

7.一次又一次到多边形2N中顶点的最短路径。 这是一个递归过程！ 因此，状态可以表示为： fi,L,0 表示从 i 出发，一次又一次遍历 i i+L-1 中的顶点的最短距离； fi,L,1 表示从 i+L-1 出发，一次遍历 ii+L-1 内顶点之间的最短距离。 状态转移方程为：fi,L,0 = (i,i+1)+fi+1,L-1,0,dist(i,i+L-1)+fi+1,L-1,1 fi ,L,1 = (i+L-1,i+L-2)+fi,L-1,1,dist(i+L-1,i)+fi,L-1,0 fi,1, 0 = 0, fi,1,1 = 0 其中 dist(a,b) 表示 ath

8.该节点与第b个节点之间的欧氏距离。 问题的答案是f1,n,0，时间复杂度为O(n2)。 本题小结：本题利用贪心思维来合理分析问题最优解的一些特征，从而根据问题中的特殊条件建立动态规划的状态，而看似NP问题可以用动态规划巧妙地解决。 。 例2马3 题目大意：中国古代历史故事“田忌赛马”是大家耳熟能详的。 据说齐王和田忌又要去赛马了。 他们每人送N匹马（N2000）。 每场比赛，败方将赠送胜方200两黄金。 如果是平局，双方都无需付费。 现在每匹马的速度值都是固定已知的，齐王并不关心田忌的骑行顺序。

9、田忌如何安排自己的马匹去对抗齐王的马匹才能赢得最多的金钱？ 3 上海赛区2004年ACM竞赛试题2006年全国信息学冬令营讲座-4-算法分析：这个问题显然可以转化为二分图最优匹配问题。 将田忌的马放在左边，齐王的马放在右边。 田忌的马A和齐王的B之间，如果田忌的马获胜，则连接权重为200的一方；如果田忌的马获胜，则连接权重为200的一方； 如果是平局，则连接到权重为0的一边； 如果失败，它将连接到权重为 200 的一侧。 然而，我们知道二分图的最优匹配算法非常复杂，无法满足N2000的要求。 我们不妨用贪心思维来分析问题。因为田忌在竞争中拥有“主动权”，他总是按照齐王送来的马匹来分配自己的马匹，所以不存在

10、你不妨认为齐王的骑马顺序是根据马的速度从高到低。 基于这个假设，我们总结出如下的贪心策略： 1、如果田忌剩余的马匹中最强的马无法战胜齐王剩余的最强的马，那么就应该用最差的马来失去齐王最强的马。 2.如果田忌残马中最强的马能够击败齐王最强的残马，则用这匹马赢得齐王最强的残马。 3、如果田忌剩余的马匹中最强的马与齐王剩余的最强的马打成平手，则可以选择与最差的马平局或输掉比赛。贪心策略的第一个证明：此时，没有一个田忌的马可以打败齐王的马，所以无论我们用最慢的马输还是用最快的马输，我们都还是输。 在贪婪的心态下，我们应该保留更强的马，所以输掉最慢的马不会比输掉其他马更糟糕，所以

11. 这是最优策略。 认证完成。 贪心策略证明之二：假设齐王剩余最强马为A，田忌剩余最强马为B，如果有更好的博弈策略，使B的对手不是A，则田忌获胜钱更多，那么假设A的对手是b，B的对手是a： 1.如果是bA，则有Ba和bA。 这个结果与BA、ba相同。 2.如果aa，bA。 这个成绩不如BA，后者更优秀。 3. 如果是baA，则有Ba、bA。 这个结果与BA、ba相同。 由此可见，交换各自的对手后，结果不会更差，因此假设不成立。 认证完成。 贪心策略的第三个证明：因为田忌最快的马只和齐王的马打成平手，那么田忌只能选择打平或者输。 如果他选择平局，当然只能用最快的马来平局； 选择如果输了，用当时最慢的马输是值得的。 这和第一个贪心策略的思路是一样的。 认证完成。 我们发现第三种贪心策略有一个分支：tie or Lose。如果穷尽所有情况，算法的复杂度会比寻找二部图的最佳匹配更高； 如果做出一般选择

九软件 版权声明：以上发布的内容及图片均来源于网络，如有无意侵犯到您的权利，请联系我们及时删除！