[算法] 贪心算法证明思路

2018-11-04 本文已影响0人 jingy_ella

最优子结构

动态规划和贪心算法都需要问题具有最优子结构，但不同的是贪心自顶向下，先做选择再求解一个结果子问题，而动态规划自底向上求解子问题，需要先求出子问题的最优解再做选择。这是因为，动态规划最优解有两个子问题时，求解子问题 $S_{ij}$ 时有j-i-1种选择，但贪心选择特征能够使其中一个子问题必定为空，这种子问题和选择数目的减少使得子问题能够自顶向下被解决。

最优子结构的证明思路：

a) 定义子问题空间，做出一个选择从而产生一个或多个子问题。子问题空间的定义结合需要求解的目标和选择后子问题的描述刻画来考虑。
b) 利用“剪切-粘贴”证明作为最优解的组成部分的每个子问题的解也是它本身的最优解。如果子问题的解不是最优解，将其替换为对应的最优解从而一定能得到原问题一个更优的解，这与最初的解是原问题的最优解的前提假设矛盾，因此最优子结构得证。

以活动选择问题为例：
首先活动选择问题的子问题空间为 $S_{ij} = \{a_k \in S: f_i \le s_k < f_k \le s_j \}$ ，假设已知 $S_{ij}$ 的最优解包含活动 $a_k$ 和根据 $a_k$ 划分出的两个子问题 $S_{ik}$ 和 $S_{kj}$ 对应的最优解 $A_{ik}$ 和 $A_{kj}$ ，如果 $S_{ik}$ 有一个解 $A'_{ik}$ 包含比 $A_{ik}$ 更多的活动，那么将 $A_{ik}$ 从 $A_{ij}$ 中剪切并粘贴 $A'_{ik}$ 得到的新的解应该比 $A_{ij}$ 包含更多的活动，由此可以证明该问题具有最优子结构。

贪心选择性质

贪心的本质是局部最优解能产生全局最优解，即产生两个子问题 $S_1$ 和 $S_2$ 时，可以直接解决子问题 $S_1$ （在子问题 $S_1$ 中，使用贪心策略选择a作为局部最优解）然后对子问题 $S_2$ 进行分解，最终可以合并为全局最优解。
因此，要证明贪心选择性质只需要证明存在一个最优解是通过当前贪心选择策略得到的，反过来，即证明**通过非贪心策略得到的原问题的最优解中也一定包含局部最优解a。

Exchange Argument方法

定义通过非贪心策略的选择可以得到的一个最优解A，将最优解中的元素和当前贪心策略会选择的元素逐个交换后得到的解A'并不比
A差（假设贪心策略会选择的元素在当前最优解中未被选择，通过“剪切-粘贴”证明得到的仍是最优解），可以证明存在原问题的最优解可以通过贪心选择得到。

以活动选择问题为例：
取 $S_{ij}$ 的最优解 $A_{ij}$ ，将 $A_{ij}$ 中活动按结束时间单调递增排序，设 $a_k$ 为 $A_{ij}$ 中第一个活动即结束最早的活动， $a_m$ 为 $S_{ij}$ 中结束最早的活动。如果 $a_k = a_m$ 则 $a_m$ 在 $A_{ij}$ 中得证；否则如果问题空间中结束时间最早的活动 $a_m$ 没有在 $A_{ij}$ 中被选择，构造子集 $A'_{ij} = A_{ij} - {a_k} +{a_m}$ ，因为 ${a_m}$ 是最早结束的活动，因此 $f_m \le f_k$ 所以 $A'_{ij}$ 中的活动不相交，又因为 $A'_{ij}$ 中活动个数和 $A_{ij}$ 相同，因此 $A'_{ij}$ 也是问题的最优解。

以 CLRS 16-4 单位时间任务调度问题 为例：
假设存在一个并非通过贪心策略得到的最优解 $A$ ，其中第j个活动为 $a_j$ ，如果 $a_j$ 被安排在它的截止时间之前，那么 $a_j$ 可以和它截止时间之前安排的任何活动向后交换且不会使得惩罚增加，因此 $a_j$ 一定可以位于不晚于其截止时间的空时间槽的最晚位置；如果 $a_j$ 被安排在它的截止时间之后的位置 $p_j$ ，且存在被安排在 $a_j$ 活动之后的活动 $a_m$ ，假设 $a_m$ 位于 $p_m$ 位置且 $d_m \le p_j$ ，那么交换 $a_j$ 与 $a_m$ 的位置可以使总惩罚减少，这与 $A$ 是问题的最优解矛盾，因此活动 $a_j$ 后面的任一活动 $a_m$ 必定满足 $d_m \ge p_j$ ，将两者交换位置不会改变总惩罚值，因此 $a_j$ 一定可以交换至最晚的空时间槽处，通过逐个交换可以得到采用题目贪心方案所得的解，仍为最优解，贪心选择性质得证。

以 Huffman树为例：
设问题空间 $C$ 对应的最优前缀编码树为 $T$ ， $l, m, r$ 为 $C$ 中具有频度最低的三个字符，要证一定存在 $C$ 的一种最优前缀编码其中 $l, m, r$ 的编码长度相同但最后一位不同，即通过贪心选择能得到问题的最优解：
假设 $a, b, c$ 为任一种最优编码树中 $T$ 具有最大深度的兄弟叶子节点，因为 $l, m, r$ 具有最低的频度，因此 $l.freq \le a.freq, m.freq \le b.freq, r.freq\le c.freq$ 。交换节点l和a产生树 $T'$ ，交换节点m和b产生树 $T''$ ，交换节点r和c产生树 $T'''$ 。首先求解一次交换后树代价的变化：
$B(T') - B(T) = \sum_{c \in C} {c.freq*d_{T'}(c)} - \sum_{c \in C}{c.freq*d_{T}(c)}$
$= a.freq*d_{T'}(a) + l.freq*d_{T'}(l) - a.freq*d_{T}(a) - l.freq*d_{T}(l)$
$= a.freq*d_{T}(l) + l.freq*d_{T}(a) - a.freq*d_{T}(a) - l.freq*d_{T}(l)$
$= (a.freq - l.freq)(d_{T}(l) - d_{T}(a))$
因为 $l.freq \le a.freq, d_{T}(l) \le d_{T}(a)$ 所以 $B(T')\le B(T)$ 经过三次这样的交换可得 $B(T''') \le B(T)$ ，所以 $T^{'''}$ 是问题的最优解，即一定存在 $C$ 的一种最优解其中 $l, m, r$ 为具有最大深度的兄弟叶子节点，他们编码长度相同但最后一位不同，由此贪心选择性质得证。