第七章 贪心策略
7.1 贪心策略的定义
7.2 贪心策略特点
7.3 典型例题与习题
在众多的计算机解题策略中,贪心策略可以算得上是最接近人们日常思维的一种解题策略,
正基于此,贪心策略在各级各类信息学竞赛、尤其在对 NPC 类问题的求解中发挥着越来越重要
的作用。
7.1 贪心策略的定义
贪心策略是:指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一
种解题方法。
其实,从“贪心策略”一词我们便可以看出,贪心策略总是做出在当前看来是最优的选择,也就
是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而
许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
例 1:在 n 行 m 列的正整数矩阵中,要求从每一行中选一个数,使得选出的 n 个数的和最大。
本题可用贪心策略:选 n 次,每一次选相应行中的最大值即可。
例 2:在一个 N×M 的方格阵中,每一格子赋予一个数(即为权)。规定每次移动时只能向上或
向右。现试找出一条路径,使其从左下角至右上角所经过的权之和最大。
本题用贪心策略不能得到最优解,我们以 2×4 的矩阵为例。
3 4 6
1 2 10
若按贪心策略求解,所得路径为:1,3,4,6;
若按动态规划法求解,所得路径为:1,2,10,6。
例 3:设定有 n 台处理机 p1,p2,......pn,和 m 个作业 j1,j2,...jm,处理机可并行工作,作业未完
成不能中断,作业 ji 在处理机上的处理时间为 ti,求解最佳方案,使得完成 m 项工作的时间最短?
本题不能用贪心算法求解:理由是若 n=3,m=6 各作业的时间分别是 11 7 5 5 4 7
用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是 14,但
是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过 15,给搜索提供了方便。
总之:
1. 不能保证求得的最后解是最佳的;
2. 只能用来求某些最大或最小解问题;
3. 能确定某些问题的可行解的范围,特别是给搜索算法提供了依据。
7. 2 贪心策略的特点
贪心算法有什么样的特点呢?我认为,适用于贪心算法解决的问题应具有以下 2 个特点:
1、贪心选择性质:
所谓贪心选择性质是指应用同一规则 f,将原问题变为一个相似的、但规模更小的子问题、
而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出的
选择。从全局来看,运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择
性质,读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
2、局部最优解: