贪心法与动态规划：问题简化与高效解法

需积分: 3 21 浏览量更新于2024-09-14 收藏 315KB DOC 举报

"贪婪的动态规划是一种在信息学竞赛中常用的策略，它巧妙地将贪心法与动态规划结合，用于解决复杂问题。在常规动态规划难以处理的状态过多或转移困难的情况下，贪心思想的引入显得尤为重要。动态规划的核心在于将问题分解成阶段决策，每个阶段都有多种状态，且最优决策独立于后续阶段。然而，动态规划面临两大挑战：判断问题是否适用动态规划和提高算法效率。在实际应用中，贪心方法首先体现在对问题本质的理解上，它能帮助识别出问题的关键部分，消除冗余，从而简化状态表示。例如，在青蛙过河问题中，贪心地选择离青蛙当前位置最近的荷叶作为下一步行动，这就是对动态规划状态的有效确立。这种情况下，原本复杂的环境被简化为一系列的决策，使得动态规划得以有效应用。贪心思想的另一个应用是在动态规划的初始状态选择上，即通过贪心策略来确定最有利的起始状态，而不是盲目搜索所有可能性。这种策略可以显著降低搜索空间，提高求解效率。总结来说，贪婪的动态规划通过合理利用贪心策略，降低了问题的复杂性，使得动态规划在面对难题时仍然能发挥其高效求解的优势。在信息学竞赛中，理解并熟练运用这一策略，能够帮助选手在有限的时间内找到解决问题的最优路径。"

2006 年全国信息学冬令营讲座

路线一定不会是最优的。

因此，原问题的模型变成了：寻找以 1 为起点，遍历凸多边形{1..N}中的顶

点一次且一次的最短路线。根据上述结论可以知道，如果离开 1 到达 2，接下

来的任务是寻找以 2 为起点，遍历凸多边形{2..N}中的顶点一次且一次的最短路

线；如果离开 1 到达 N，接下来的任务是寻找以 N 为起点，遍历凸多边形{2..N}

中的顶点一次且一次的最短路线。这是一个递归的过程！

因此，状态可以这样表示：f[i,L,0]表示从 i 出发，遍历{i..i+L-1}中的顶点一

次且一次的最短距离；f[i,L,1]表示从 i+L-1 出发，遍历{i..i+L-1}中的顶点一次且

一次的最短距离。状态转移方程是：

f[i,L,0] = min{dist(i,i+1)+f[i+1,L-1,0],dist(i,i+L-1)+f[i+1,L-1,1]}

f[i,L,1] = min{dist(i+L-1,i+L-2)+f[i,L-1,1],dist(i+L-1,i)+f[i,L-1,0]}

f[i,1,0] = 0, f[i,1,1] = 0

其中 dist(a,b)表示第 a 个结点和第 b 个结点之间的欧几里德距离。问题的答

案是 f[1,n,0]

时间复杂度 O(n

)。

本题小结：

本题中运用贪心思想合理的分析出了问题最优解的一些特点，从而能够根

据问题中的特殊条件确立出动态规划的状态，把看似 NP 的问题，用动态规划

巧妙的解决了。

例题二 The Horse Racing

题目大意：

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要

赛马了，他们各派出 N 匹马（N≤2000），每场比赛，输的一方将要给赢的一

方 200 两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是

固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自

己的马去对抗齐王的马，才能赢最多的钱？

上海赛区 2004 年 ACM 比赛试题

- 3 -

剩余13页未读，继续阅读

sfboi

粉丝: 3
资源: 51

贪心法与动态规划：问题简化与高效解法

动态规划与贪婪算法解决01背包问题

探索贪婪算法与动态规划：第3部分详解

立体停车楼智能优化：动态规划与贪婪算法的结合

算法图解 大O记法 递归 贪婪算法 动态规划 背包问题 散列表 SHA算法

贪婪算法，回溯，动态规划等一些算法

01背包-动态规划&贪婪算法.ipynb

0-1背包动态规划&部分背包贪婪算法

c语言版算法及程序（贪婪，回溯，动态规划）

算法：算法实践，例如分治法，贪婪算法，动态规划等

掌握核心算法：分治、贪婪、动态规划与回溯技术

最新资源

算法图解大O记法递归贪婪算法动态规划背包问题散列表 SHA算法