贪婪算法，调度

Question

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

因此，由于我无法理解Greedy算法调度问题，因此我已经阅读并进行了一段时间的搜索。

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

我们选择了一些贪婪的想法...

• 以s的升序接受（“最早的开始时间”）
• 以f-s（“最短工作时间”）的升序接受
• 以递增的顺序接受冲突（“最小冲突”）
• 以f的升序接受（“最早完成时间”）

书中说最后一个，以f的递增顺序接受总是会给出最佳解决方案。

但是，它没有提及为什么总是提供最佳解决方案，以及为什么其他3个都不提供最佳解决方案。

他们提供的数字说明了为什么其他三个将无法提供最佳解决方案，但我无法理解其含义。

由于信誉不佳，我无法发布任何图像，所以我将尝试绘制它。

？| --- | | --- | | --- |
| ------------------------- |
s低估解的增加阶

| ----------- | | ----------- |
??? | ----- |
fs被低估的解的增加阶

| ---- |？| ---- |？| ---- | ？| ---- |

？| ----- |？| ----- |？| ----- |

？| ----- | ???? | ----- |

？| ----- | ???? | ----- |

冲突数量的增加顺序。被低估的解决方案

这是它的外观，我不明白为什么这是每种情况的反例。

如果有人能解释每个贪婪的想法为何行不通的话，它将非常有帮助。

谢谢。

Answer 1

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

1. 最早开始时间

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

2. 最短执行时间

Suppose tasks [1,10], [11,20], [9,12]. This strategy would choose [9,12] and then reject the other two, but optimal solution is [1,10], [11,20]. Therefore, shortest execution time strategy will not always lead to optimal result.

3. Least amount of collisions

This strategy seems promising, but your example with 11 task proves it not to be optimal. Suppose tasks: [1,4], 3x[3,6], [5,8], [7,10], [9,12], 3x[11,14] and [13, 16]. [7,10] has only 2 collisions with other tasks, which is less than any other task, so it would be selected first by the least amount of collisions strategy. Then [1,4] and [13, 16] would be selected, and all the other tasks rejected because they collide with already selected tasks. That is 3 tasks, however 4 tasks can be selected without collision: [1,4], [5,8], [9,12] and [13, 16].

You can also see that the earliest finish time strategy will always choose the optimal solution in these examples. Note that more than one optimal solution can exist with same number of selected tasks. In such case, earliest finish time strategy will always choose one of them.

Answer 2

我想我可以解释一下。
可以说，我们有n工作，开始时间为s[1..n]，结束时间为f[1..n]。因此，如果我们根据完成时间对其进行排序，那么我们将始终能够完成大多数任务。让我们看看如何。

如果一项工作完成得较早（即使是本系列的后期开始，这是一项短期工作），那么我们总是有更多时间来完成以后的工作。假设，我们还有其他可以在此间隔内开始/完成的作业，因此我们的任务数量可以增加。现在，实际上不可能做到这一点，就像在此之前完成任何任务一样，那将是最早完成时间的任务，因此我们将在该任务上进行工作。而且，如果到目前为止尚未完成任何任务（但是已经开始），那么如果我们选择了该任务，那么我们将不会完成任何任务，但是实际上我们至少已经完成了一项任务。因此，无论如何，这是最佳选择。
有许多可能的解决方案，可以在一定间隔内完成最大数量的任务，EFT提供了一种这样的解决方案。但这始终是最大数量。

我希望我能解释清楚。