算法分析与设计之贪心算法

文章目录

前言
一、Greedy Algorithms
- 1.1 贪心选择性质
- 1.2 最优子结构性质
- 1.3 正确性证明
二、典型例题
- 2.1 Interval Scheduling间隔调度
- 2.2 Interval Partitioning最少间教室排课
- 2.3 Selecting Breakpoints选择加油站停靠点
- 2.4 硬币找零
- 2.5 Scheduling to Minimizing Lateness
- 2.6最优离线缓存
- 2.7 其它
结束语

???? 个人主页:风间琉璃

???? 版权: 本文由【风间琉璃】原创、在****首发、需要转载请联系博主

???? 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

前言

提示：这里可以添加本文要记录的大概内容：

预览：

一、Greedy Algorithms

贪心算法是一种基于贪心策略的优化算法，通过一系列的选择得到问题的解，它所做出的每一个选择都是当前状态下局部最好的选择，即贪心选择，这种启发式的策略并不能总能获得最优解，通常这种算法对于解决一些最优化问题非常有效，尤其是那些可以通过局部最优解来达到全局最优解的问题。

对于一个具体的问题，怎么知道是否可用贪心算法解决此问题，以及能否得到问题的最优解呢？

这类问题一般具有两个重要的性质：贪心选择性质和最优子结构性质。

1.1 贪心选择性质

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别：

在动态规划中，每步所做出的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择。
在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。

贪心算法所做出的贪心选择可以依赖于以往所做过的选择，但绝不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做出一次贪心选择就将所求同题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做出的贪心选择最终导致问题的整体最优解。首先考查问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做出贪心选择后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

1.2 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。在活动安排问题中，其最优子结构性质表现为：若A是关于E的活动安排问题的包含活动1的一个最优解，则相容活动集合A’=A- {1}是关于E’={ $\in E$ ; $s_i \geq f_1$ }的活动安排问题的一个最优解。

小结：

基本思想：在每次迭代中，选择当时的最佳解决方案，不从整体最优考虑，因此贪心算法不是对所有问题都能得到整体最优解。
局部最优 v.s.全局最优：贪婪算法是在每个时刻做出局部最优选择。在某些问题中，这种策略可以导致全局最优解。
算法一般分为如下三步：
- 分解：将问题分解为若干子问题
- 解决：找出合适的贪心策略，求解每一个子问题的最优解
- 合并：将局部最优解堆叠成全局最优解
优点：简单、高效
缺点：可能不正确/可能不是最佳

1.3 正确性证明

贪心算法最难的部分不在于问题的求解，而在于正确性的证明，常用的证明方法有归纳法和反证法。

归纳法证明分下面两步：

证明当n= 1时命题成立。
假设n=m时命题成立，可以推导出在n=m+1时命题也成立。（m代表任意自然数）

贪心证明一般思路：

①假设贪心算法不是最优的。

②设 $S_1 = (i_1, i_2, \dots, i_k)$ 表示由贪心算法得到解， $ S_2 = (j_1, j_2, \dots, j_m) $表示的是最优解。并且设 $i_1 = j_1, i_2 = j_2, \dots, i_r = j_r$ ，即 $S_1,S_2$ 有最多r个相同元素的解，前 r 个解在贪心解和最优解中是相同的，直到某个点 r + 1，贪心算法选择 $i_{r+1}$ ，而最优解选择 $j_{r+1}$ 。

③由于贪心策略是按照xxx进行选择，然后比较 $i_{r+1}$ 和 $j_{r+1}$ ，观察解的不同，可以将贪心算法选择的解 $i_{r+1}$ 替换最优解 $j_{r+1}$ ，并解释说明这样更能满足问题要求。但这与有最多r个相同元素的解冲突，这与假设贪心算法不是最优的相矛盾。因此，贪心算法必须是最优的。

二、典型例题

参考：

2.1 Interval Scheduling间隔调度

如下图所示，每个长条方块代表一个活动，总有若干个活动a、b… h，横坐标是时间，方块的起点和终点分别代表这个活动的起始时间和结束时间。当两个活动的活动时间没有交叉，即两个方块不重叠时，表示这两个活动是兼容的(compatible)。问题最终是要找到一个活动子集，查找相互兼容的活动的最大子集。

本问题为尽可能多的选择活动，约束条件是下一个活动的开始时间大于等于上一个活动的结束时间s[i] >= f[j]。使用贪心算法解决该问题，可能的贪心策略如下：

每次选择开始时间最早的活动(不是最优解)

证明(反证法)：为了方便使用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示已经选择的活动;红色的线条表示没有选择的活动。

如图按照该贪心策略每次选择开始时间最早的活动，则应该选择蓝色的活动。很明显这不是最优解，因为选择红色的活动，可以选择2个活动，因此此策略不可靠。
**每次选择持续时间最短的活动(**不是最优解)

证明(反证法)：按照该贪心策略每次选择持续时间最短的活动，如下图所示，在最短时间的活动，位置刚好和其他活动冲突，只能选择蓝色的活动，很明显持续时间最短不是最优解。
**每次选择最少的冲突活动(**不是最优解)

证明(反证法)：按照该贪心策略每次选择最少的冲突活动，如下图所示，很明显每次选择最少的冲突活动不是最优解。
每次选择结束时间最早的活动(最优解)

贪婪算法：按完成时间的递增顺序考虑活动。如果该活动与已经选择的活动不冲突，则选择该活动。伪代码如下：

将活动按照结束时间进行排序(归并、==快速排序： $O (n l o g n)$ )。==集合A存放已经选择的活动j，并且初始化为空。然后遍历已经排好序的活动，如果该活动与集合A中的活动不冲突，则将该活动加入到集合A中。

证明：该贪婪算法是最优的(重点！)

贪心算法求interval scheduling最优证明：首先在最优解中找出最接近贪心解的（最接近指r的取值最大），前r个一样。最后推出r不是最大（largest），即推出矛盾。

证明（反证法）：

假设贪心算法不是最优的。

设 $S_1 = (i_1, i_2, \dots, i_k)$ 表示由贪心算法选择的活动集合， $ S_2 = (j_1, j_2, \dots, j_m) $表示最优解中的活动集合。并且设 $i_1 = j_1, i_2 = j_2, \dots, i_r = j_r$ ，即 $S_1,S_2$ 有最多r个相同元素的解，前 r 个活动在贪心解和最优解中是相同的，直到某个点 r + 1，贪心算法选择了活动 $i_{r+1}$ ，而最优解选择了活动 $j_{r+1}$ 。

由于贪心策略是按照最早结束时间进行选择，所以 $i_{r+1}$ 的结束时间比 $j_{r+1}$ 的结束时间早。因此，贪心算法选择 $i_{r+1}$ 后，仍然为后续活动留下了最大的可能空间，这就意味着可以安排更多的活动。

如果 $j_{r+1}$ 是最优解中的活动，而 $i_{r+1}$ 的结束时间比 $j_{r+1}$ 更早，则可以将 $j_{r+1}$ 替换为 $i_{r+1}$ ，并保持后续活动不受影响。但这与有最多r个相同元素的解冲突，这与假设贪心算法不是最优的相矛盾。因此，贪心算法必须是最优的。

对于区间调度问题（Interval Scheduling），常用的解题思路是贪心算法。该问题通常涉及选择尽可能多的互不重叠的区间，并且在一些应用场景下，区间代表任务的开始和结束时间。贪心算法的核心思想是通过局部最优选择来构建全局最优解。

2.2 Interval Partitioning最少间教室排课

课程i从 $s_i$ 开始到 $f_i$ 结束。目标：找到最少的教室数量来安排所有讲座，确保没有两堂课在同一时间在同一间教室上课。
这个安排使用了 4 间教室来安排 10 堂讲座：

这个安排仅使用了3间教室来安排 10 堂讲座：

要解决这个问题，可以使用一种贪心策略，通过按时间顺序安排讲座来最小化所需的教室数量。关键是按讲座的开始时间进行排序，并根据教室的占用情况安排新的讲座。伪代码如下：

首先按讲座的开始时间 $s_i$ 对所有讲座进行排序。d初始化为 0，表示当前教室的数量。对于每一个讲座j，按顺序考虑其是否可以安排到现有的某个教室中。

如果当前讲座j可以与某个教室 k兼容（即在该教室的最后一个讲座结束后开始），则将讲座安排到该教室，并更新该教室的结束时间。如果当前讲座与所有现有的教室都不兼容（即所有教室都在当前讲座的开始时间之前被占用），则分配一个新教室。将 d 加 1，表示新增了一间教室，并将该讲座安排到新教室中。

证明: 贪心算法在讲座安排问题中使用的教室数量是最小的，即贪心算法是最优的，即其他任何调度方案无法减少这个教室数量。

假设贪心算法使用了d个教室来安排所有讲座，需要证明任何其他调度方案也至少需要d个教室。

假设d号教室是因为安排了讲座 j而被使用的，因为讲座 j 的安排与其他 d-1个教室中的讲座都不兼容。讲座j与之前安排在其他d−1 个教室中的所有讲座都不兼容，因此需要一个新的教室。

这些安排在d个教室中的讲座的结束时间都在 $s_j$ （讲座 j的开始时间）之后结束。因为贪心算法按照开始时间对讲座进行了排序，所有与讲座j不兼容的讲座（即与 j重叠的讲座）都是在时间 $s_j$ 或之前开始的。这意味着在时间$ s_j + ϵ$（即 $s_j$

秒客网