我想了解贪心算法调度问题是如何工作的。
所以我一直在阅读和谷歌一段时间，因为我不能理解贪婪算法调度问题。
我们在单个资源上有n个作业要调度。作业(i)具有请求的开始时间s(i)和结束时间f(i)。
有一些贪婪的想法，我们选择…
- 按s("最早开始时间")的递增顺序接受
- 按f - s("最短作业时间")从小到大接受
- 按冲突数递增的顺序接受("最少冲突")
- 按f("最早完成时间")的递增顺序接受
书上说最后一个，接受f的递增顺序总是给出最优解
然而，它没有提到为什么它总是给出最优解，为什么其他3个不能给出最优解。
他们提供了一个图表，说明为什么其他三个不能提供最佳解决方案，但我不明白这是什么意思。
由于我的声望很低，所以我不能发布任何图像，所以我将尝试画它。
|——|——|——|
|-------------------------|
s的递增阶数低估了解决方案
|-----------| |-----------|
| - - - |
f-s的递增顺序低估了解决方案
|----| |----| |----| |----|
|-----| |-----| -----|
|-----| -----|
|-----| -----|
冲突数递增顺序。低估了解决方案
这就是它的样子，我不明白为什么这是每个场景的反例。
如果有人能解释为什么每个贪婪的想法都行得通/行不通，那将是很有帮助的。
谢谢。
我想我能解释清楚。
假设我们有n个作业，开始时间是s[1..n]，完成时间是f[1..n]。因此，如果我们按照完成时间进行排序，那么，我们总是能够完成大多数任务。让我们看看，如何。
如果一个作业完成得较早(即使它在系列中较晚开始，一个较短的作业)，那么，我们总是有更多的时间用于后面的作业。让我们假设，我们有其他作业可以在这个间隔内启动/完成，这样我们的任务数量就可以增加。现在，这实际上是不可能的，如果任何任务在这之前完成，那么这将是完成时间最早的一个，所以我们将研究这个。如果任何任务到现在还没有完成(但已经开始)，那么如果我们选择了它，我们就不会完成任何任务，但现在我们至少完成了一个任务。所以，在任何情况下，这都是最优选择。
有许多可能的解决方案可以在一个时间间隔内完成最大数量的任务，EFT给出了这样一个解决方案。但它总是可能的最大值。
我希望我能解释清楚。
由于@vish4071已经解释了为什么选择最早的完成时间将导致最优解决方案，我将只解释反例。任务[a,b]从a开始，到b结束。我将使用您提供的反例。
- 最早开始时间
假设任务[1,10], [2,3], [4,5], [6,7]。最早的开始时间策略将选择[1,10]，然后拒绝其他3个，因为它们都与第一个发生碰撞。然而，我们可以看到[2,3], [4,5], [6,7]是最优解，所以最早的开始时间策略并不总是产生最优结果。
假设任务[1,10], [11,20], [9,12]。该策略将选择[9,12]，然后拒绝其他两个，但最优解是[1,10], [11,20]。因此，最短执行时间策略并不一定能得到最优结果。
这个策略看起来很有希望，但是你的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]。
您还可以看到，在这些示例中，最早完成时间策略总是选择最优解。请注意，对于相同数量的选定任务，可能存在多个最优解决方案。在这种情况下，最早完成时间策略总是选择其中之一。