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

需积分: 3 57 浏览量更新于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

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

动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法

利用动态规划解决01背包问题

贪婪算法与动态规划的思路区别

动态规划算法是贪婪算法吗

hdp 启发式动态规划代码

自适应动态规划控制matlab

分而治之 归并排序 二分搜索 动态规划 正统的斐波那契数 流水线调度问题 背包问题 最长公共子序列问题 贪婪算法 活动选择问题 霍夫曼编码问题

qleaning greedy贪婪策略

简述找零问题背包问题与贪婪算法

tsp问题适合用贪婪算法吗

最新资源

分而治之归并排序二分搜索动态规划正统的斐波那契数流水线调度问题背包问题最长公共子序列问题贪婪算法活动选择问题霍夫曼编码问题