贪心算法，调度

Question

我正在尝试理解贪心算法调度问题的工作原理。

因此，我已经阅读和谷歌了一段时间，因为我无法理解贪心算法调度问题。

我们有n个工作要在单个资源上安排。任务（i）具有请求的开始时间s（i）和完成时间f（i）。

有一些贪心的想法可以选择...

- 按照s的递增顺序接受(“最早开始时间”) - 按照f - s的递增顺序接受(“最短任务时间”) - 按照冲突数量的递增顺序接受(“最少冲突”) - 按照f的递增顺序接受(“最早完成时间”)

书中说最后一个，按照f的递增顺序接受总是会给出最优解。

然而，它没有提到为什么它总是提供最优解，以及为什么其他三个不会提供最优解。

他们提供了这张图，说明为什么其他三个不能提供最优解，但我不明白它是什么意思。

由于我的声誉不高，我无法发布任何图像，所以我将尝试绘制它。 |---| |---| |---| |-------------------------| 按照s的递增顺序接受 低估的解决方案 |-----------| |-----------| 　　　|-----| 按照f - s的递增顺序接受 低估的解决方案 |----|　 |----|　|----| 　|----|

　|-----|　|-----|　|-----|

　|-----|　　　　|-----|

　|-----|　　　　|-----|

按冲突数量的递增顺序接受。 低估的解决方案

这就是它的样子，我不明白这是每种情况的反例。

如果有人能解释为什么每个贪心想法是否有效，那将非常有帮助。

谢谢。

- Andy Min

---

请详细说明您的条件。您是否提前知道所有任务的开始和结束时间，还是会在一段时间后出现新任务？您是否被允许将任务移动到其他时间进行处理？如果可以，那么您会因此受到惩罚吗？您如何评估什么是“好”的结果？只有完全执行的任务才值得做吗？长时间的任务比短时间的任务更重要吗？ - kajacx

Answer 1

我想我可以解释一下这个问题。假设我们有n个工作任务，它们的开始时间为s[1..n]，结束时间为f[1..n]。如果我们按照结束时间对它们进行排序，那么我们将始终能够完成最多数量的任务。让我们看看为什么。

如果一个工作任务结束得更早（即使它在序列中开始得更晚，是一个短工作），那么我们总是有更多的时间来完成后面的工作任务。假设我们有其他工作任务可以在此间隔内开始/完成，以增加我们的任务数量。现实情况并非如此，因为如果在此之前已经完成了任何任务，那么最早完成的任务将是我们要处理的任务。而且，如果到目前为止还没有完成任何任务（但已经开始），那么如果我们选择它，我们将不会完成任何任务，但现在我们至少已经完成了一个任务。因此，在任何情况下，这都是最优选择。

在一个时间段内完成的最大任务数有很多可能的解，EFT提供了其中一种解决方案。但它总是最大可能的任务数。

希望我能解释清楚。

- vish4071

---

非常感谢。这真的帮了很多！:D - Andy Min

Answer 2

由于 @vish4071 已经解释了为什么选择最早完成时间会导致最优解，我将只解释反例。任务 [a,b] 开始于 a 并结束于 b。我将使用您提供的反例。

1. 最早开始时间

假设有以下任务： [1,10]，[2,3]，[4,5]，[6,7]。最早开始时间策略将选择 [1,10]，然后拒绝其他 3 个任务，因为它们都与第一个任务冲突。但是我们可以看到，[2,3]、[4,5]、[6,7] 是最优解，因此最早开始时间策略并不总是产生最优结果。

2. 最短执行时间

假设有以下任务： [1,10]，[11,20]，[9,12]。该策略将选择 [9,12]，然后拒绝其他两个任务，但最优解是 [1,10]、[11,20]。因此，最短执行时间策略并不总是产生最优结果。

3. 最少冲突次数

这个策略似乎很有前途，但是您提供的 11 个任务的例子证明它并不是最优解。假设以下任务： [1,4]，3x[3,6]，[5,8]，[7,10]，[9,12]，3x[11,14] 和 [13,16]。 [7,10] 只与其他任务发生了 2 次冲突，少于任何其他任务，因此它将首先被最少冲突次数策略选择。然后会选择 [1,4] 和 [13,16]，并拒绝所有其他任务，因为它们与已选任务冲突。那是 3 个任务，但是可以选择 4 个任务而不发生冲突：[1,4]、[5,8]、[9,12] 和 [13,16]。

您还可以看到，在这些例子中，最早完成时间策略将始终选择最优解。请注意，在具有相同数量的选择任务的情况下，可能存在多个最优解。此时，最早完成时间策略将始终选择其中之一。

- kajacx