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

• 💂 个人主页:风间琉璃
• 🤟 版权: 本文由【风间琉璃】原创、在CSDN首发、需要转载请联系博主
• 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

前言

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

预览：

一、Greedy Algorithms

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

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

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

1.1 贪心选择性质

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

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

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

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

1.2 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。在活动安排问题中，其最优子结构性质表现为：若A是关于E的活动安排问题的包含活动1的一个最优解，则相容活动集合A’=A- {1}​是关于E’={$i\in E$; $s_i\ge 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(nlogn)$)。==集合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$ 稍后）时，这些 d个讲座都是同时进行的。

在时间 $ s_j + ϵ$处，有 d 个讲座重叠，表明在这个时刻必须使用至少 d个教室来安排这些讲座。如果少于 d 个教室，这些重叠的讲座就会导致冲突，因为两个或多个不兼容的讲座将被分配到同一个教室。

因此，任何调度方案都至少需要d 个教室来避免讲座的冲突。由于贪心算法使用了d 个教室，且其他任何安排方案不可能使用少于 d 个教室，所以贪心算法是最优的。

2.3 Selecting Breakpoints选择加油站停靠点

从普林斯顿到帕洛阿尔托沿着固定路线进行公路旅行，沿途在某些点有加油站，油箱容量为 C，每次加油后可以行驶的最大距离为 C。目标：尽量少停靠加油站进行加油。

这是一个典型的贪心算法问题，目的是在公路旅行中通过选择合适的加油站停靠点，使加油次数最少。贪心算法的核心思想是每次加油时都选择可以到达的最远加油站，从而最大化每次加油后的行驶距离，确保尽可能减少加油次数。伪代码如下：

将加油站停靠点按照距离大小从小到大进行排序，集合 S 存储了已经选择的停靠点，初始时只包含起点$b_0$，变量 x 用来表示当前所处的位置，初始时在起点$b_0=0$。

当当前位置 x没有到达终点$b_n$时，继续循环寻找下一个合适的停靠点。寻找在当前油量范围内可以到达的最远的停靠点，即寻找**最大点p，**使得$b_p$这个停靠点在当前距离x和$x+C$ 之间。

如果下一个停靠点的位置$b_p$与当前位置 x 一样，说明找不到比当前位置更远的加油站，当前加油无法使车子继续行驶，则返回无解。否则更新当前位置 x为选择的最远可到达的停靠点$b_p$，将选择的停靠点$b_p$加入到集合 S中。

证明该贪心算法是最优的（反证法）

假设贪心算法不是最优的，设$0=g_0<g_1<\cdots <g_p=L$表示贪心算法选择的停靠点集合，$ 0 = f_0 < f_1 < \dots < f_q = L$ 表示最优解中的停靠点集合。假设贪心算法和最优解在前 r个停靠点处是相同的，即$f_0=g_0,f_1=g_1,\dots ,f_r=g_r$，其中 r是最大的值。

在 r+1个停靠点处，贪心算法选择了$g_{r+1}$，而最优解选择了$f_{r+1}$。由于贪心算法的选择策略是选择当前可达范围内最远的停靠点，因此根据贪心选择的规则，贪心选择的停靠点$g_{r+1}$ 必然是比最优解选择的停靠点$f_{r+1}$更远的，即$g_{r+1}>f_{r+1}$。

如果$f_{r+1}$是最优解中的第r+1个停靠点，并且$g_{r+1}$停靠点比$f_{r+1}$停靠点更远，可用将$f_{r+1}$替换为$g_{r+1}$，行驶更远的距离，贪心算法后续的选择仍然是可行的，甚至可能更优。但这与最多有r个相同元素的解冲突，这与假设贪心算法不是最优的会导致矛盾。故贪心算法必须是最优的。

2.4 硬币找零

假设货币面额为 1、5、10、25、100（单位：分），设计一种方法，以最少的硬币数量支付给顾客指定金额。

贪心策略：在每次迭代中，选择不超过剩余金额的最大面值硬币加入找零中，直到支付完成。

按从小到大的顺序排列硬币面值，准备一个空集合 S 来记录选择的硬币。每次迭代选择当前剩余金额 𝑥下可以使用的最大面值硬币ck。 如果没有适合的硬币（即所有硬币面值均大于 𝑥），说明无解。将选择的硬币面值从 𝑥中扣除，并记录在集合 S 中。 重复上述过程，直至 𝑥=0。最后 S 中包含了用于支付的所有硬币。

证明贪心算法对于美国硬币系统（1、5、10、25、100）是最优的。

归纳法：

①对于小金额$x\le c_k$，贪心算法直接选择最接近x的最大硬币$c_k$，显然是最优的。
②假设对于所有 $x<c_k$，贪心算法能以最少硬币数找到最优解。
考虑任意$c_k\le x<c_{k+1}$，贪心算法会选择面值为$c_k$的硬币作为第一步。如果最优解没有选择$c_k$，由于$c_k$本身是小面值硬币的倍数（例如$c_k=5,10,25$等）,则必须用足够数量的小面值硬币$c_1,c_2,\dots ,c_{k-1}$来凑出至少$c_k$的金额。这种方法会使用更多硬币，无法优于贪心算法。因此，最优解必须选择硬币$c_k$，此时问题简化为金额$x-c_k$的找零问题。

③根据归纳假设，对于金额$x-c_k$，贪心算法可以找到最优解。因此，贪心算法在金额x上也是最优的。

表格通过列出美国硬币系统的约束条件和小面值硬币的最大组合值，证明了贪心算法在每一步选择面值最大且不超过当前金额的硬币是正确且最优的。

每种硬币的限制：1 分硬币最多使用 4 枚。5 分硬币和 10 分硬币的总数量最多为 2 枚。25 分硬币最多使用 3 枚。100 分硬币没有限制，但只在大金额时才使用。

小面值硬币的最大组合值：面值$c_k$的硬币若未使用，由小于$c_k$ 的硬币组成的金额有一个上限。例如：面值小于 5 的硬币最多组合出 4 分。面值小于 10 的硬币最多组合出 9 分。面值小于 25 的硬币最多组合出 24 分。面值小于 100 的硬币最多组合出 99 分。

贪心算法在某些货币系统中可能是次优的。例如，对于美国邮资面值系统（1, 10, 21, 34, 70, 100, 350, 1225, 1500），贪心算法并不总是能找到最优解。

目标金额：140

贪心解法使用了 8 枚硬币（100, 34, 1, 1, 1, 1, 1, 1）。

最优解：2 枚硬币（70, 70）

2.5 Scheduling to Minimizing Lateness

在单一资源场景下，给定一组任务，每个任务有如下特性：

• $t_j$：处理时间。

• $d_j$：截止时间。

• $s_j$：开始时间。

• $f_j=s_j+t_j$：完成时间。

任务的延迟定义为：$l_j=\max (0,f_j-d_j)$,如果任务在截止时间后完成，延迟就是完成时间与截止时间的差值；如果在截止时间前完成，延迟为0。

目标是安排任务顺序，使最大延迟$L=\max l_j$最小化。

如上图共有 6 个任务，这是按完成任务时间递增排序，显然这并不是最优策略，最大延迟应该为1。如下图所示：

• 按处理时间$t_j$的升序对任务排序（优先完成处理时间最短的任务）

  按照这种贪心策略首先完成任务1，然后再完成任务2，延迟为1。但是如果先完成任务2再完成任务1，延迟为0，显然这种贪心策略不是最优的。

• 按松弛时间$d_j-t_j$的升序对任务排序（优先完成松弛时间最小的任务）。松弛时间：任务剩余的可用时间，即任务完成前的可分配空闲时间。排序方式：$(d_1-t_1)\le (d_2-t_2)\le \cdots \le (d_n-t_n)$。

按照松弛时间进行排序，首先完成任务2，然后再去处理任务1，最终延迟为11-2=9。但是最大延迟应为1。显然也不是最优的。

• 按截止时间$d_j$的升序对任务排序（优先完成截止时间最早的任务）。

使用贪心算法，按任务的截止时间递增顺序调度所有任务，从而最小化最大延迟。

首先按任务截止时间$d_j$升序排序，确保先处理截止时间较早的任务。初始化当前时间t = 0，遍历每个任务j，分配时间区间$[s_j,f_j]$：

• 任务开始时间$s_j=t$
• 任务完成时间$f_j=t+t_j$

然后更新当前时间 $t=t+t_j$。最后输出所有任务的时间区间$[s_j,f_j]$。

在最小化最大延迟的最优调度中，任务的执行是连续的，没有空闲时间（即没有无意义的时间间隔）。由于贪心调度严格按照截止时间顺序调度任务，它自然没有逆序（按照按截止时间排序$d_i\le d_j$排序,但任务j被调度在任务i之前），确保了最小化最大延迟的最优性。

引理：交换两个相邻且顺序错误的任务（即逆序任务），会减少一个逆序的数量，并且不会增加最大延迟。

假设在交换之前，任务的最大延迟为l，交换后为l′，我们需要证明：交换后，最大延迟 l′不大于交换前的最大延迟l。

• 除了任务i和j外，其他任务k的延迟不会变化：$l_k^{\prime }=l_k\text{对于所有}k\ne i,j$。因此，交换不会影响任务k的延迟。

• 任务i的延迟不会增加：交换后任务i可能会变得早些完成，所以它的延迟$l_i^{\prime }$不会大于交换前的延迟 $l_i$：$l_i^{\prime }\le l_i$。因此，任务i的延迟不会增加。

• 任务j的延迟不会增加：如果任务j在交换前已经延迟（即$l_j>0$），交换后，任务j会在任务i之后完成，从而延迟不会增加。

任务j在交换前完成时间为$f_j$，它的延迟为：$l_j=f_j-d_j$。交换后，任务j将在任务i完成之后开始，因此其完成时间变为。此$f_i^{\prime }$时任务j的延迟变为：$l_j^{\prime }=f_j^{\prime }-d_j$。由上图知j完成时间为$f_i$，所以上面第二个等号成立。又按截止任务时间排序有$d_i\le d_j$，所以第三个不等号成立，因此第四个也成立。

证明贪心调度S是最优的。

我们要证明，贪心算法生成的调度S是最优的，即它能够最小化最大延迟，并且它是最少逆序的调度。

假设$S^{\ast }$是一个最优调度，并且具有最少的逆序。可以假设$S^{\ast }$是没有空闲时间的调度。

• 如果$S^{\ast }$没有逆序，那么$S^{\ast }$和贪心调度S是相同的，意味着$S=S^{\ast }$，这时贪心调度就是最优的。

• 如果$S^{\ast }$有逆序，假设i和j是一个相邻的逆序任务（即任务j被调度在任务i之前，尽管ji < j），我们交换i和j的顺序：

  • 交换i和j并不会增加最大延迟。交换后的延迟要么相等，要么减小，因为我们已经证明交换相邻逆序任务不会增加最大延迟。
  • 交换i和j会严格减少逆序的数量，因为逆序数减少了 1。

如果交换i和j可以减少逆序数，并且不会增加最大延迟，这就与$S^{\ast }$是最优调度且具有最少逆序的假设相矛盾。因为根据定义，$S^{\ast }$是最少逆序的调度，交换i和j后，得到一个逆序更少的调度S，但S的最大延迟不变，因此S也是一个最优调度，且逆序更少。因此贪心调度S是最优的。

2.6最优离线缓存

在缓存管理中，最优离线缓存问题旨在通过合理的缓存替换策略来最小化缓存未命中的次数。具体来说，有以下定义和目标：

• 缓存容量: 假设缓存能够存储k个物品。
• 请求序列: 有一系列的物品请求，表示为$d_1,d_2,...,d_m$。
• 缓存命中 (Cache Hit): 如果请求的物品已经存在于缓存中，则为命中。
• 缓存未命中 (Cache Miss): 如果请求的物品不在缓存中，则需要将其加载到缓存中。如果缓存已满，则需要替换掉现有的某个物品。

目标是设计一个替换调度，使得缓存未命中的次数最小。也就是说，如何在物品请求的过程中，减少需要替换的物品，以最大限度地减少未命中的次数。

假设缓存容量k = 2，初始缓存包含物品a 和 b，请求序列如下： a, b, c, b, c, a, a, b。

按照最优的替换调度，最终会有 2 次缓存未命中。初始缓存: [a, b],具体调度过程如下：

• 请求 a: 缓存命中，不替换。
• 请求 b: 缓存命中，不替换。
• 请求 c: 未命中，替换一个物品a，缓存为 [c, b]。
• 请求 b: 缓存命中，不替换。
• 请求 c: 缓存命中，不替换。
• 请求 a: 未命中，替换一个物品c，缓存为 [a, b]。
• 请求 a: 缓存命中，不替换。

Farthest-In-Future (FF) 是一种离线缓存替换策略，它的核心思想是：在每次缓存未命中时，选择将来最晚被请求的物品进行替换。

2.7 其它

(1）背包问题：给定一个背包，其最大承重量为W，有n个物品，每个物品有以下属性：重量为$w_i$, 价值为$v_i$。选取物品或分割物品装入背包，使得背包中物品的 总价值最大化。

注意：这里不是0-1 背包问题(物品只能完整装入或完全不装入)，分数背包问题允许将物品按比例分割，装入部分重量。

贪心策略：每次选择单位价值最大的物品或物品部分，直到背包装满为止。如果是0-1背包该策略可能不是最优的。

（2）最优装载问题：假设有一艘载重量为W的轮船，以及一批集装箱，每个集装箱的重量为$w_i$。在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船，使得装载的集装箱的总重量不超过轮船的最大载重 W。

贪心策略：按集装箱的重量从小到大排序，优先选择重量较轻的集装箱装载。通过选择轻的集装箱，可以装入更多集装箱，并且这里只考虑W。

（3）哈夫曼编码

哈夫曼编码的贪心策略通过每次选择频率最小的两个节点合并，确保每一步都尽可能减少编码的总长度。通过不断合并最小的节点，最终得到的哈夫曼树是最优的前缀编码，能够实现数据压缩的最小编码总长度。

​

结束语

感谢阅读吾之文章，今已至此次旅程之终站 🛬。

吾望斯文献能供尔以宝贵之信息与知识也 🎉。

学习者之途，若藏于天际之星辰🍥，吾等皆当努力熠熠生辉，持续前行。

然而，如若斯文献有益于尔，何不以三连为礼？点赞、留言、收藏 - 此等皆以证尔对作者之支持与鼓励也 💞。