贪心算法

概述

贪心算法(Greedy Algorithm)，意思是每次只选择当下的最佳解，来得到最后的最佳解答案。

相较于其它算法，这个更常概念性的出现，只要算法的一部分满足这样的操作就具有贪心算法的性质，但贪心算法并非所有情况都适用。

充要条件

贪心选择性质

引用自 https://en.wikipedia.org/wiki/Greedy_algorithm#Specifics

Whichever choice seems best at a given moment can be made and then (recursively) solve the remaining sub-problems. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the best (that is, the ‘optimal’) solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage’s algorithmic path to the solution.

这段话的意思是当下做出的局部最佳选择必定包含在最佳解之中，做出最佳选择后不再需要回溯只需要往下解决子问题就能得出最佳解的情况。

若要确实的证明满足贪心选择性质的话常用交换论证以及拟阵

最优子结构

该问题的最佳解是由各个子问题的最佳解所构成的

示例说明

1. 排程问题

说明：尽可能选择最多的任务，并且时间不能重叠

     start, end
任务 A: [5, 9]
任务 B: [1, 2]
任务 C: [3, 4]
任务 D: [0, 6]
任务 E: [5, 7]
任务 F: [8, 9]

Schedule initial image

如图所示，要选择最多的区块但不能重叠，使用贪心算法将最早完成的当作当前最佳解

选择当前最早完成的 B [1, 2]
接着从2开始，下一个起始时间>=2并且不重叠的是 C [3, 4]
接着从4开始，下一个起始时间>=4并且不重叠的是 E [5, 7]
接着从7开始，下一个起始时间>=7并且不重叠的是 F [8, 9]
完成，一共选择了 $O = [B, C, E, F]$

使用交换论证说明其符合贪心选择性质

所有任务 $S = \{A, B, C, D, E, F\}$
选择最早完成的 $g_1$ ( B [1, 2] )
假设存在一个最佳解 $O = \{o_1, o_2, ..., o_k\}$
假设最佳解 $O$ 不包含 $g_1$
那么 $O$ 也有自己的第一个 $o_1$ ， $o_1 \neq g_1$
根据策略选择最早结束的， $g_1$ 的完成时间必然小于等于 $o_1$ ， $Finish(g_1) \le Finish(o_1)$
新的集合 $O' = (O - \{o_1\}) \cup \{g_1\}$
$O'$ 与 $O$ 同样有 $k$ 个任务
$O'$ 与 $O$ 里面的其它任务 $\{o_2, ..., o_k\}$ 是相容的，因为 $Finish(g_1) \le Finish(o_1)$
这表示 $g_1$ 也可以和 $O$ 里的任务相容并且数量相同， $O'$ 是一个有效的解

说明其符合最优子结构
当选择了 B [1, 2] 现在可以视为是一个起始点是2的新题目
当选择了 C [3, 4] 现在可以视为是一个起始点是4的新题目
当选择了 E [5, 7] 现在可以视为是一个起始点是7的新题目
当选择了 F [8, 9] 现在可以视为是一个起始点是9的新题目
每次选择都是一个新的子问题，将这些子问题合并起来就是最终的结果 $O = [B, C, E, F]$

我们再来看看别的例子

2. 凑币问题_1

说明：在硬币 $S = \{1, 3, 4\}$ 中使用最少的硬币凑成刚好的币值 $N$
就是平时付钱的行为，使用贪心算法每次选择最大的面额

使用交换论证说明其符合贪心选择性质

硬币币值 $S = \{1, 3, 4\}$
寻找一个大于 $4$ 的临界点检验，假设目标金额 $N = 6$
最佳解 $O = \{3, 3\}$ ，使用硬币数量 $k = 2$
若贪心选择性质成立，存在一个最佳解 $O' \supseteq \{4\}$
$N = 6$ ，所以 $O'$ 还需要补足 $2$ ，凑出 $2$ 需要 $\{1, 1\}$
$O' = \{4, 1, 1\}$ 的硬币数量 $k' = 3$ ， $k' > k$ ，贪心选择性质不成立

说明其符合最优子结构
假设初始 $N = 6$
当选择了最大币值 $4$ 现在可以视为新题目 $N = 2$
当选择了最大币值 $1$ 现在可以视为新题目 $N = 1$
当选择了最大币值 $1$ 现在可以视为新题目 $N = 0$

这个币值不符合 贪心选择性质 但符合 最优子结构，所以能用动态规划(Dynamic programming)解决，该章节正在撰写中

3. 凑币问题_2

说明：在硬币 $S = \{1, 5, 10, 50\}$ 中使用最少的硬币凑成刚好的币值 $N$
使用贪心算法每次选择最大的面额

使用交换论证说明其符合贪心选择性质

硬币币值 $S = \{1, 5, 10, 50\}$
寻找一个大于 $50$ 的临界点检验，假设目标金额 $N = 60$
假设最佳解 $O$ 不包含 $50$ ， $O = \{10, 10, 10, 10, 10, 10\}$ ，使用硬币数量 $k = 6$
若贪心选择性质成立，存在一个最佳解 $O' \supseteq \{50\}$
$N = 60$ ，所以 $O'$ 还需要补足 $10$ ，凑出 $10$ 需要 $\{10\}$
$O' = \{50, 10\}$ 的硬币数量 $k' = 2$ ， $k'(2) < k(6)$ ，符合结果

实际需要从最小测试到 $\max(S) + \text{second\_max}(S)$ 都符合最佳解
如果 $N$ 远大于 $\max(S)$ ，则最佳解必定包含 $\max(S)$ ，如同缩减成子问题的概念
而 $\max(S) + \text{second\_max}(S)$ 之内可能产生复杂的交互作用。

说明其符合最优子结构
假设初始 $N = 60$
当选择了最大币值 $50$ 现在可以视为新题目 $N = 10$
当选择了最大币值 $10$ 现在可以视为新题目 $N = 0$

补充

货币币值是经过安排的符合标准，所以我们平时凑钱的方式总是符合预期，这篇文章提到了新增币值时确保符合贪心解法的定理。

实际解题通常不搞麻烦的证明贪心算法有效，可以判断规模 $O$ 与 $10^8$ 的关系、想个测资反例、实际尝试等方式来猜测有效性。