对贪心算法的思考，贪心算法究竟是什么？
发表于: 2020-02-29 17:07:00 | 已被阅读: 429 | 分类于: 算法
通过上一节讨论的“充分利用会议室”问题，我们发现贪心算法几乎基于“直觉本能”解决问题：每次只选择结束时间最早的会议，就可达成“充分利用会议室”的目的。从本质上来看，这其实是通过做出一系列选择来求解问题的，而在每个决策点，则只需做出当前看来最佳的选择（例如每次都选择结束时间最早的会议），不再考虑其他情况。但是这样“随性”的启发式求解方法并不能保证总是找到最优解，例如上一节文章的“找钱”问题。
至此，虽说我们使用贪心策略解决过具体的问题，并且也得到了最优解，但是似乎对某些概念还有些模糊：例如，既然贪心算法不能保证总是找到问题的最优解，那究竟什么时候才应使用贪心算法呢？遗憾的是，并没有通用的数学公式可以判断所有的问题，但是本文将尝试探讨贪心算法的原理，贪心算法到底是什么呢？相信对此问题有所指引。
贪心算法的设计步骤
问了不讨论枯燥的理论，让文章太劝退，我们先回顾下上一节解决的问题，在求解“充分利用会议室”问题时，先是使用（本专栏第一节介绍过的）动态规划方法对问题做了分析，然后基于贪心策略解决了问题，当时主要经过了如下几个步骤：
- 确定问题的最优子结构
- 设计递归算法（动态规划）
- 证明贪心选择是安全有效的
- 设计递归算法（贪心算法）
- 写程序实现算法
稍后讨论“最优子结构”的概念，在此之前，我们能够看出，在上一节中，贪心算法的设计比想象的（仅凭借直觉本能）复杂了一些，它是以动态规划为基础的，例如，在会议选择问题中，我们首先定义了子问题 S(ij)，然后发现如果总是做出贪心选择（选择结束时间最早的会议），问题可以简化为 S(K) 的形式。
由此可以看出，有着“世界上最简单算法”之称的贪心算法，其实并不简单，所谓“大简至繁”，若希望简单的算法有效，背后必定要做充分的分析和论证工作。
解决“重复利用会议室”问题时，我们可以使用贪心选择来改进最优子结构，使得选择后只留下一个子问题。例如，贪心策略每次只需挑出结束时间最早的会议，从所有的会议中挑选出结束时间最早的后，余下的会议集合中，我们需要做的仍然只有相同的一件事——就是继续找出结束时间最早的会议。然后把每次选择的会议组合在一起，就形成了问题的最优解。更一般的，稍稍总结一下，贪心算法的设计步骤可以如下进行：
- 将求解问题转换为：做出一次求解后，总是只余下一个子问题需要求解
- 证明贪心选择是安全有效的
- 证明做出贪心选择后，余下的子问题满足：其最优解与贪心选择组合即可得到原始问题的最优解
这样就得到了最优子结构。
最优子结构
如果一个问题的最优解包含其子问题的最优解，我们就称该问题具有最优子结构。问题具备最优子结构是使用贪心算法和动态规划应该具备的条件，这其实很好理解，贪心算法和动态规划在求解问题时，通常会先求解子问题的最优解，再将子问题的最优解组合，得到原始问题的最优解。不难看出，此时原始问题的最优解其实就是其子问题最优解的组合。
理论层面的讨论非常枯燥，来看下面这个问题：
根据上图提出两个问题：
- 找到一条从 q 到 t 的最短路径
- 找到一条从 q 到 t 的最长简单路径
上图几个端点构成了环，因此问题 2 必须是“简单路径”，否则无限绕环，就构成了无限长的路径，“简单”一词限制着不能有重复路径。
对于问题 1，q->r->t 是从 q 到 t 的一条最短路径，其子问题“一条从 q 到 r 的最短路径”的一个解为 q->r，显然被包含在原始问题的解中，也即问题 1 的最优解包含其子问题的最优解，所以问题 1 具有“最优子结构”。
对于问题 2，q->r->t 是从 q 到 t 的一条最长简单路径，但是其子问题“一条从 q 到 r 的最长简单路径”的一个解为 q->s->t->r，也即问题 2 的最优解不包含其子问题的最优解，所以问题 2 不具有“最优子结构”。
从直觉上来看，问题 1 和问题 2 似乎是“对称”的，那为什么前者有最优子结构，而后者没有呢？仔细考虑一下，应该能够发现问题 1 的子问题是无关的，这里子问题无关的含义是：原问题的一个子问题的解不影响另一个子问题的解，例如问题 1 的子问题“从 q 到 r 的最短路径”和子问题“从 r 到 t 的最短路径”互不影响，因此是无关的。
再看问题 2，它可以拆分为子问题1“从 q 到 r 的最长简单路径”和子问题2“从 r 到 t 的最长简单路径”。子问题 1 的最优解可以是 q->s->t->r，这没有问题，但是应该注意，求解子问题 2 时，就不能再使用顶点 s 和 t 了（“简单路径”限制不能有重复路径）。可是，顶点 t 是原问题的路径终点，是必须用到的。这么看来，由于求解问题 2 的两个子问题必须用到共同的顶点，因此我们说这两个子问题是相关的。
可见，在寻找最优子结构时，应该尽量保证子问题的“无关性”。事实上，问题 2 是 NP 完全的，我们不太可能找到多项式时间的求解方法，以后有机会再谈。
贪心 vs 动态规划
如何证明贪心算法能否得到最优解呢？遗憾的是，并没有一套适合所有情况的通用方法，但是有两个关键要素可以参考，其中一个是问题要具备最优子结构，这一点我们已经讨论过。另外一个关键要素是贪心选择性质：我们可以通过做出局部最优（贪心）选择来构造全局最优解。换句话说，当需要选择时，只需做出当前看来最佳的选择，而不必考虑子问题的解。
这其实也是贪心算法和动态规划的不同之处。我们回顾下第一节讨论的“动态规划方法”，不难发现，每个步骤都要进行一次选择，并且选择还依赖子问题的解，通过第一节最后介绍的两种方式的动态规划算法实现可以看出，如果想要从顶到下的求解问题，就需要申请一块额外的空间用于存放已经求得的子子问题的解，这样在下次求解依赖该子子问题的子问题时，直接查询即可，避免重复计算。或者，干脆使用第二种方式，也即从底向上的方式求解问题。
在贪心算法中，我们要做的就简单许多了，无非就是做出当前看来最佳的选择，无需再考虑子问题的解。当然，我们必须证明每个步骤做出贪心选择后能够生成全局最优解，例如上一节我们在求解“充分利用会议室”问题时，证明了结束时间最早的会议必定在最优解中。
另外需要说明的是，如果进行贪心选择时，我们不得不考虑不止一个选择，通常意味着可以改进贪心选择，使其更为高效。由于贪心算法和动态规划都利用了问题的最优子结构性质，所以我们可能会为一个可用贪心算法求解的问题设计一个动态规划算法，或者反过来。因此，我们再看一个经典的问题，探讨二者之间的轻微差别：
着火了，小明的保险箱里有 n 件贵重物品，第 i 个物品价值 vi 元，重 wi 斤，假设小明的背包只能装 W 斤的物品，vi 、wi 和 W 都是整数，小明怎样才能带走价值尽量高的物品呢？
这个问题很多人习惯称之为“0-1背包问题”，因为对每一个物品，小明要么把它留下，要么把它拿走，他不能把同一个物品拿走多次，也不能只拿走一个物品的一部分。如果 n 种物品可以被拿走一部分，而不是只能做 0-1 二元选择，问题就演化为“分数背包问题”。
可以想象 0-1 背包问题对应的物品是金砖，而分数背包问题对应的物品是金砂。
两种背包问题都具有最优子结构性质。对于 0-1 背包问题，我们要解决的是重量不超过 W 斤而又价值最高的装包方案，假定已经选择了物品 k，那么余下的问题就是重量不超过 W-wk 斤而又价值最高的装包方案，与此同时，小明只能从没有物品 k 的余下物品里挑选。
不过，虽然两种背包问题很相似，但贪心算法仅能求解分数背包问题，而不能求解 0-1 背包问题。可以先计算每个物品的单位价值 vi/wi，按照贪心策略，小明只需要选择单位价值最高的物品，该物品拿完后，如果背包还没装满，就继续拿余下的单位价值最高的物品，直至背包装满，达到重量上限 W 斤。将物品的单位价值排序，贪心算法的运行时间可以为 O(nlgn)。
但是这一贪心策略求解 0-1 背包问题就不能得到最优解了。我们考虑问题实例：假如小明的背包能容纳 50 斤的物品，保险箱内一共有 3 种物品：
物品编号|重量/斤|价值/元|单位价值/(斤/元) ---|--- 1|10|60|6 2|20|100|5 3|30|120|4
上述贪心策略首先会选择物品 1，然后选择物品 2，此时虽然背包还没有满，但是已经不能容纳物品 3 了，所以小明最多带走价值 160 元的物品。这显然不是最优解，因为带走物品 2 和物品 3 的价值更高（220元）。求解分数背包适用的贪心策略不能应用于 0-1 背包主要是因为无法装满背包，物品单位有效价值降低了。对于 0-1 背包问题，当我们考虑是否将一个物品装入背包时，必须比较包含此物品的子问题与不包含它的子问题，然后才能做出选择，这会导致大量的重叠子问题——而“大量重叠子问题”恰好就是应用动态规划的标识，所以动态规划特别适合求解 0-1 背包问题。
小结
本节主要探讨了贪心算法可以解决哪些问题——显然，问题具备最优子结构和满足贪心选择性质是不错的参照条件。可以看出，有着“世界上最简单的算法”之称的贪心算法在应用上并不简单，这主要是因为贪心算法不能保证求得全局最优解，确保能够得到最优解的工作就交给我们使用者了。其实，从本质上来看，贪心算法更多的是一种思想，指导我们探寻问题的“简单”解决方案，这里的“简单”加上了引号，是因为找到贪心算法的可行路径并不简单，但是一旦确保所选路径能够应用贪心算法，剩下的工作就简单了。
用一句话来说，应用贪心算法，过程是复杂的，结果是简单的。一个简单的例子就是上一节求解“充分利用会议室”问题时，在探寻方案和证明贪心策略可以求得全局最优解时是复杂的，但是一旦确定，接下来编写代码实现算法是非常简单的。