专题讲解——贪心 | Thomas He’s Blog

type

status

date

slug

summary

1. 任务调度问题（Scheduling Problem）

我们第一个要研究的案例就是任务调度问题，它的目标是在一个或多个共享资源上调度任务，以达到某个目标的最优解。比如，共享资源可以是计算机的处理器，任务则是进程；共享资源可以是教室，任务则是讲座；共享资源还可以是某一天的时间，任务则是会议。

任务调度是一个很基础的问题，在生活的方方面面中都有它的身影。

1.1 The Setup

不同的任务有不同的性质，不过，我们可以将一些通用的性质给抽象出来。其中，最重要的两个性质是长度（length）和权重（weight）。长度表示完成这个任务所需的时间；权重可以表示这个任务的重要程度或优先级。

调度规定了任务的执行顺序。假设有个任务需要执行，那么就有个不同的调度。调度的数目实在是太多了（因此不能穷举）！那么哪一个调度是最好的呢？

目标函数

这就是我们目标函数（objective function）要解决的问题了。目标函数会给每一个调度打一个分数，我们可以根据这些分数来选择最优的调度。

目标函数多种多样，不同的目标函数选择的最优调度也不同。不过，大多数目标函数都和任务的完成时间（completion time）相关。

📌

完成时间 调度中，任务的完成时间是任务前面任务的总长度和任务的长度之和。

⏰

Quiz 假设有三个任务，它们的长度分别为并且假设任务就按的顺序执行，那么各个任务的完成时间是多少？ a) 1, 2, 3 b) 3, 5, 6 c) 1, 3, 6 d) 1, 4, 6

好，回到我们最初的问题：什么样的调度是一个好的调度呢？

当然，我们期望每个任务的完成时间越短越好。但是，这是不可能的。先执行任务的完成时间短，后执行任务的完成时间长。所以，我们必须做一些取舍。

其中一种取舍是：使得任务的加权完成时间之和最小。用数学表示，目标函数就是：

注意，我们需要在个可能的调度中，找到使得加权完成时间之后最小的那一个。举个例子：假设有三个任务，它们的长度分别为；它们的权重分别为。如果我们先执行任务 1，再执行任务 2，最后执行任务 3，那么这个调度的加权完成时间之和为：

如果你去验证所有种可能的调度，你会发现，这个调度就是使得加权完成时间之和最小的调度。

不过，如何在一般的情况下求解这个问题呢？

📌

问题：求使得加权完成时间之和最小的调度输入：给定个任务，以及它们的长度和权重（长度都权重都为大于 0 的数）。 输出：使得加权完成时间之和最小的调度。

个任务，总共有种调度，所以穷举法肯定是不可行的，我们需要一种更聪明的算法。

1.2 贪心算法

任务调度问题具有一个迭代的结构（有多个步骤）：任务是一个接着一个执行的。所以，我们何不尝试一下贪心算法？

第一步，我们将考察两个特殊情况。对特殊情况的考察有助于对一般情况的理解，并且有助于我们制定贪心策略。

得出算法的过程远比算法本身重要！因为过程是可以重复的，在其它场景中依然可以使用。

两种特殊情况

假定就有这样一种贪心算法，它可以解决这个问题。那么，这个贪心算法长什么样子？

作为新手，我们先来考察两种简单的情况（这个考察过程可以帮助我们了解贪心算法的模样）：

假定所有的任务都具有相同的长度（权重可以不同）。

假定所有的任务都具有相同的权重（长度可以不同）。

⏰

Quiz (1) 如果所有任务的长度相同，那么是先执行权重小的任务呢，还是先执行权重大的任务？ (2) 如果所有任务的权重相同，那么是先执行长度短的任务呢，还是先执行长度长的任务？ a) 大/短 b) 小/短 c) 大/长 d) 小/长

两种不同的贪心算法

通过上面的小测试，可以发现：我们更喜欢权重大、长度短的任务。但是如果这两个性质冲突了怎么办？给定一个权重小、长度短的任务，和一个权重大、长度长的任务，我们该先执行哪一个？

贪心算法最好的情况是什么呢？

在最好的情况下：我们可以想出一个公式，它可以根据长度和权重，给每个任务打一个分数；根据分数，从高到低依次执行每个任务，就能保证任务的加权完成时间之和最小。

如果这样的公式存在，那么它必须满足下面两个性质：

长度一定：权重越大，分数越高。

权重一定：长度越长，分数越低。

😇

头脑风暴 你能想出哪些具有这两个性质的公式？

我们能想到的，最简单的公式，可能就是下面这两个了：和。根据这两个公式，我们可以得出两个不同的贪心算法：

那么这两个算法，哪一个正确呢？或者两个都正确？又或者两个都不正确？

如果我们想排除一个算法，最好的办法就是举例子，使得一个算法的结果比另一个算法的结果更坏。在两种特殊情况下，这两个算法都是适用的。因此，最简单的例子，可能就是：两个任务，它们具有不同的长度和权重；但是在两个算法中，它们的执行顺序刚好相反。

一个简单例子是：和。

GreedyDiff 会先执行任务 2，再执行任务 1；GreedyRatio 刚好相反，它会先执行任务 1，再执行任务 2。

⏰

Quiz 对于上面这个简单的例子，GreedyDiff和GreedyRatio输出的调度，它们的加权完成时间之和分别是多少？ a) 22 和 23 b) 23 和 22 c) 17 和 17 d) 17 和 11

很显然，GreedyDiff这个算法是不正确的。但这并不能说明GreedyRatio是正确的。

对于没有提供正确性证明的算法，即使该算法在某些简单的示例中得出了正确的结论，你也应该始终抱有怀疑的态度；而对于贪心算法，你应该格外怀疑。

不过，在我们的例子中，GreedyRatio是正确的，它能够保证加权完成时间之和是最小的。

`GreedyRatio` 的正确性证明

感兴趣的同学可以自行证明~（提示：exchange argument）

`GreedyRatio` 的实现

2. 贪心算法的性质

从任务调度问题的分析过程中，我们可以得出贪心算法的几个特性：

对于大多数具有迭代结构的问题，我们很容易想出一个甚至是多个看似可行的贪心算法。好处是，当你遇到求最优解问题（问题具有迭代结构），并且卡住的时候，这个时候你可以尝试一下贪心算法。坏处是，我们很难评估哪一个贪心算法是最优的。

贪心算法实现起来比较简单。很多贪心算法，就是一次排序加上的额外处理。

很难评估一个贪心算法是不是正确的；即使它是正确的，证明起来也会很困难。

❓

既然贪心算法的可靠性得不到保证，那啥时候可以使用贪心算法呢？ a) 求解最优解问题。 b) 问题具有迭代结构，也就是问题的解包含一系列的步骤。 c) 没有想到其它更好办法。

3. 霍夫曼编码（Huffman Code）

我们第二个精心选择的案例是：霍夫曼编码。

人人都喜欢压缩。压缩地越多，手机就能存储更多的照片；压缩地越多，下载速度也就越快。霍夫曼算法是一种广泛使用的无损压缩算法。比如，每次播放 MP3 音频文件时，计算机都会使用霍夫曼编码。这一章，我们将学习霍夫曼编码，了解它的最优性；以及学习如何用贪心算法快速计算霍夫曼编码。

3.1 编码

固定长度的二进制编码

归纳总结

参考文献

一些引用

引用文章

💡

欢迎您在底部评论区留言，我们一起交流学习~