401-贪心算法

贪心算法：就是按照某种策略（方法）一步步的做选择，每一步总是做出在当前看来最好的选择（局部最优）, 不从整体考虑

活动安排问题

相容：两个活动进行的时间不重叠

贪心算法：找到一种贪心策略，也就是后动的选择方法，按照该方法经过一次次选择，找出相容最多的活动

1. 找活动占用时间最短的？ 如有三个活动：[8,13], [13,20],[11,14] [11,14]时间最短，但是就不能选择其他活动了；而其他两个活动可以相容；所以不能按照这个策略选择
2. 找开始时间最早的？ 如有三个活动：[9,12],[8,20],[12,13] 先选[8,20], 但是其他的就不能选了；因为 [8,20]跨越太长了；这个策略也不可以
3. 找活动结束时间最早的？✅

例子

对于上述的活动安排，按照结束时间排序得到

按照这个标准选择活动（上图中黄色显示的活动）

各个活动的时间轴，我们选择的是活动 2，4，5，7，9. 可以看到他们的活动时间不重叠

观察上上图，还有其他活动数量为 4 的最优活动安排；如活动 1，3，7，9 和活动 2，5，7，9, 这两个活动安排也是最优解 所以使用贪心算法只能找到一个最优解，不能找到全部最优解

算法描述

S 是活动开始时间，f 是活动结束时间 a 存放是否选择这个活动 for 循环中判断后续的活动开始时间是否晚于前一个选择的活动的结束时间

时间复杂度：$\Theta (n)$ 排序的时间复杂度：$O(n\log n)$

总的时间复杂度：$O(n\log (n))$

贪心算法的基本要素

对于一个问题是否可以使用贪心算法，需要问题满足两个性质：

1. 贪心选择性质
2. 最优子结构性质

贪心选择性质

贪心选择性质，是指所求问题的整体最优解，可以通过一系列局部最优的选择，即贪心选择来达到

贪心选择性质证明方法一步步的贪心选择（局部最优）最终导致问题的整体最优解

最优子结构性质

当一个问题的最优解包含其问题的最优解时，称此问题具有最优子结构

因为最优解对应最优值，所以通常证明：问题的最优值包含其子问题的最优解

贪心算法和动态规划算法的差异

• 性质相同点：贪心孙法和动态规划算法都要求问题具有最优子结构性质
• 性质不同点：贪心算法要求问题就有贪心选择性质，动态规划算法不要求
• 计算方式不同： 动态规划算法通常以自底向上的方式解各子问题 贪心算法以自顶向上的方式进行，每做一次贪心选择就将问题变成规模更小的问题

以 0-1背包问题为例，两个算法的区别

对每一种物品 i 只有两种选择，即装入背包或不装入背包

贪心算法解背包问题的基本步骤 背包问题：物品可分割成小块 贪心策略每次选择单位价值最高的物品装入背包

1. 计算每种物品单位重量的价值 $\frac{V_i}{W_i}$，按单位重量的价值从大到小将 n 种物品排序
2. 以排序厚的次序一次将物品装入背包。直至全部物品都装入或者因背包容量不足不能装入为止
3. 如果背包尚有容量，将最后不能完全装入物品切割一部分装满背包
4. 算法结束

时间复杂度有排序决定：$O(n\log n)$

贪心算法解 0-1 背包问题

贪心算法处理 0-1 背包问题，每次都选择价值/空间比最高的物品，不能保证最后背包完全塞满；选一个价值更小一点的物品有机会把背包塞满，并且获得更高的价值；所以贪心算法不能得到最优值，而动态规划可以考虑所有情况

---

最优装载

确定贪心策略

采用重量最轻这先装的贪心选择策略，可产生该问题的最优解

算法描述

贪心选择性质

这里是说有很多个最优解，类似前面活动安排，但是贪心算法实际上只能找到包含第一个集装箱的最优解，但是其他的最优解，我们可以证明，他可已使用第一个集装箱替换掉其中一个集装箱，这样集装箱数量不变，但是包含了第一个集装箱，这些都是最优解 普通最优解（0101）可以转换成贪心策略最优解（1100）

最优子结构性质

最优装载问题具有最优子结构性质，设 1 至 n 个集装箱装上船的最大数量为 $T(1,n,w)$

则 $T(1,n,w)=1+T(2,n,w-w_1)$;

因 $T(1,n,w)$ 是最优值，则 $T(2,n,w-w_1)$ 一定是最优值。反证法证明之

哈夫曼编码

定长编码，每个字母的编码长度小叙 8 个比特，这样总编码长度大大减小

这个编码字符编码长度不同。使用这个编码，总的编码长度进一步缩小 但是这个编码有歧义，如 101 可以解码成 b（1）d (01) 或者e（10）b（1）, 他的解释不唯一，没有办法准确的解码

前缀码不存在一个编码是另一个编码的前缀的问题，这样的在解码的时候是唯一的，不存在歧义

使用哈夫曼编码的编码长度

定长编码二叉树

所有的编码都在最后一层，从根节点搜到最后一层，得到编码

哈夫曼编码

平均编码长度

哈夫曼编码的贪心策略

伪代码

每次从队列中选出两个发生额度最小的字符，给他们加上一个根节点，使用 left，right 保存这个根节点的左右节点是这两个字符；然后把这个根基点放回到队列中 直到结束 Q 中只剩下一个根节点，整个哈夫曼树的根节点

贪心选择性质证明

这里的证明，也是因为，最优解的形式不唯一，但是我们的贪心策略得到的最优解：概率最低的节点肯定在最底层。那么其他的解可不可以转换成，我们的策略得到的解呢？上面的证明就解决了这个问题

最优子结构性质证明

若上图 T 树是一棵最优前缀编码树，那么他的子树 $T^{\prime }$ 也是最优前缀编码树（把 z 节点当作一个字符节点看）

单源最短路径

基本思想

设置顶点集合 S 并不断的做贪心选择来扩充这个结合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度一致（贪心策略）

初始时，S 为空，设 dist 中源到源的最短特殊路径长度为 0（非负） 从源只经过 S 中顶点到达u（s 外）称为从源到 u 的特殊路径，用数组 dist 记录当前每个顶点的最短特殊路径长度。最短特殊路径长度最小的顶点为最短路径长度已知

每次从 V-S 中去除最短路径长度已知的顶点 u，将 u 添加到 S 中，同时对数组 dist 做必要的修改。直到 S 包含了所有 V 中顶点

算法演示

Dijkstra 算法主要是维护上面的这个表格

算法正确性和计算复杂性

最小生成树

最小生成树性质

最小生成树早现实世界中应用十分广泛

• 交通
• 电信
• 网络通信
• 集成电路布线

最优子结构证明

使用剪切 +替换的方式可以使用反证法证明 T 为最优 MST 的时候他的子问题也一定是最优MST

贪心选择性质

同样可证明贪心选择性质，使用反证法

Prime 算法（选顶点加入集合S）

Kruskal 算法（选择连接属于不同连接分支的最小边）

时间复杂性对比

多机调度问题

多机调度问题要求给出一种作业调度方案，是所给的 n 个作业在尽可能断的时间内由 m 太及其加工处理完成

约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许终端处理。作业不能拆分成更小的子作业 这个问题是NP 完全问题，到目前为止没有有效的解法 对于这一类问题，用贪心策略有时可以设计出较好的近似算法

先分配时间最长的工作，把工作分配给工作时间最短的及其

例

贪心算法解题思路小结

1. 首先分析问题，确定贪心策略
2. 证明贪心策略对于该问题是否可以求出最优解（二要素），不满足贪心选择性质的问题，只能求出近似解
3. 为了方便选择操作，根据贪心策略的要求先做排序，更据排序结果顺序选择，如活动安排、最优装载、背包问题
4. 有些问题的贪心算法是边选择边排序（优先队列），例如：哈夫曼编码树问题，和多级调度问题等