Mengzelev's Blog

算法导论学习笔记-贪心算法

Word count: 1,428 / Reading time: 5 min
2018/09/17 Share

前一篇dp写得又乱又烂简直不想看。但愿自己能坚持下去吧。可是这依然改变不了搬运和截图多于实际内容的事实

基础理论

贪心算法可以看做是动态规划的弱化版,处理某一类特殊的具有最优子结构的问题。

在每个贪心算法之下,几乎总有一个更繁琐的动态规划算法。

算法设计步骤

  1. 将最优化问题转化为这样的形式:对其作出一次选择后,只剩下一个子问题需要求解【子问题削减】
  2. 证明作出贪心选择后,原问题总是存在最优解,即贪心选择总是安全的【安全性证明:替换法
  3. 证明作出贪心选择后,剩余的子问题满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构【确认最优子结构】

贪心选择性质

贪心选择性质是指,当进行选择时,我们直接作出在当前问题中看来最优的选择,而不必考虑子问题的解【鼠目寸光】

贪心起来不太方便的时候,可以改进贪心选择,例如做一些预处理(活动选择问题中按照结束时间对活动进行排序)

最优子结构

证明:子问题最优解 + 贪心选择 = 原问题最优解
隐含地使用了数学归纳法

两种背包问题

  • 0-1背包问题
  • 分数背包问题

共同的条件是有一堆不同价值、重量的东西,用一个有一定承重量的背包去装,求装得的最大价值。
不同在于,0-1背包问题中每个东西要么拿要么不拿,而分数背包问题中可以拿分数个东西。

前者无法用贪心算法求解,但后者可以,主要区别在于考虑0-1背包问题中是否将一个商品装入背包时,必须比较包含此商品的子问题的解和不包含此商品的子问题的解。简单来说就是,空闲空间的存在非常讨厌。只能使用动态规划来求解

活动选择问题

问题描述



最优子结构

通俗地说,对于某一个活动$a_k$,在它开始之前结束的所有活动,和在它结束之后开始的所有活动,这两个集合都应该取到最优解,可以使用剪切-粘贴发得到证明。因为如果子问题存在更优解,只需替换即可得到原问题的最优解,与原问题已经是最优解矛盾。

严谨化表述可以描述为:




其中,$S{ij}$表示在$ai$结束后开始、在$aj$开始前结束的活动的集合;
c[i,j]表示集合$S{ij}$的最优解。

贪心选择
———————————
抛开各种分析直接来看这个问题,或者说和一个不知道动态规划的人谈起这个问题,很容易(大概)有这样一种想法:
对于每一次选择,都取不冲突的、最早结束的活动,感觉应该能够得到最优解。

事实上这个想法是对的,可以使用替换法进行证明。


这样每次做选择的时候就只剩下了一个子问题。

递归实现

贪心算法可以自顶向下实现。



迭代实现



其中Q是一个单调队列。如果用最小堆实现,则该算法的时间复杂度为O(nlgn)。

时间复杂度

如果直接使用dp,状态转移是O(n)的,子问题总数为O(n^2),因此总时间复杂度为O(n^3)。

而如果使用贪心策略,压缩了解空间,限制了解的范围,从伪代码可以看出每个$a_{i}$都被检查且只被检查了一次,因此时间复杂度是O(n)的。

如果输入数据是无序的那么还需要一个O(nlgn)的排序时间,总体的时间复杂度为O(nlgn)。

赫夫曼编码

问题描述

解释起来有点麻烦,提供STFW快捷入口

百度百科-哈夫曼编码

wikipedia-Huffman coding

简单概括一下:

  • 用变长编码压缩编码长度
  • Huffman树的叶结点与码字的编码一一对应
  • 字符的二进制码字用从根结点到该字符对应的叶结点的简单路径表示
  • 代价的定义:


伪代码



正确性证明

这一块设计很多数学推导,难度比较大,此处指概括大致思路,配合算法导论原书食用风味更佳

主要是需要证明两个引理。




引理2旨在说明在单步选择下,贪心能得到是最优解。用的是替换法。从假想出一个抽象的最优解T,经过某些变换得到根据贪心选择构造出的解T’’,运用数学手段证明这两个解具有相等的代价。
此处采用的是相减得到大于等于关系,与最优解天然具有的小于等于构造解相结合,证明等价。




引理3旨在证明该问题的最优子结构。采用了喜闻乐见的的剪切-粘贴法,也使用了一定的数学手段导出了矛盾。

引理2+引理3能证明上文的贪心算法可以生成一个最优前缀码。

课程要求暂时只需要看前三章

CATALOG
  1. 1. 基础理论
    1. 1.1. 算法设计步骤
    2. 1.2. 贪心选择性质
    3. 1.3. 最优子结构
    4. 1.4. 两种背包问题
  2. 2. 活动选择问题
    1. 2.1. 问题描述
    2. 2.2. 最优子结构
    3. 2.3. 递归实现
    4. 2.4. 迭代实现
    5. 2.5. 时间复杂度
  3. 3. 赫夫曼编码
    1. 3.1. 问题描述
    2. 3.2. 伪代码
    3. 3.3. 正确性证明