贪心算法，调度
greedy algorithm, scheduling
我正在尝试了解贪心算法调度问题的工作原理。
所以我一直在阅读和谷歌搜索一段时间，因为我无法理解贪心算法调度问题。
我们有 n 个作业要安排在单个资源上。作业 (i) 具有请求的开始时间 s(i) 和完成时间 f(i)。
我们有一些贪心的想法select...
- 按 s 的升序接受 ("earliest start time")
- 接受 f - s 的递增顺序 ("shortest job time")
- 按冲突数量递增的顺序接受 ("fewest conflicts")
- 接受 f 的升序 ("earliest finish time")
而书上说的最后一个，按f的递增顺序接受总是会给出一个最优解。
但是它没有提到为什么它总是给出最优解，为什么其他3个不会给出最优解。
他们提供的图表说明了为什么其他三个不会提供最佳解决方案，但我无法理解它的含义。
由于我的声望低，我不能post任何图像，所以我会尝试绘制它。
‖|---| |---| |---|
|------------------------|
s 的升序
低估的解决方案
|------------| |------------|
|-----|
f-s 的递增顺序
低估的解决方案
|----| |-----| |-----| |-----|
‖|-----| |-----| |-----|
‖|-----| |-----|
‖|-----| |-----|
冲突数量递增。
低估的解决方案
这就是它的样子，我不明白为什么这是每个场景的反例。
如果有人能解释为什么每个贪婪的想法行得通/行不通，那将非常有帮助。
谢谢。
我想我可以解释一下。
比方说，我们有 n 个作业，开始时间为 s[1..n]，结束时间为 f[1..n]。所以如果我们按照完成时间排序，那么，我们总能完成最多的任务。让我们看看，如何。
如果一项工作较早完成（即使它在系列中较晚开始，这是一项短期工作），那么，我们总是有更多时间处理较晚的工作。让我们假设，在此间隔内我们还有其他工作可以 start/complete，这样我们的任务数量就会增加。现在，这实际上是不可能的，因为如果有任何任务在此之前完成，那将是完成时间最早的任务，因此我们将处理该任务。而且，如果有任何任务到现在还没有完成（但已经开始），那么如果我们选择它，我们就不会完成任何任务，但现在我们实际上至少完成了一个。所以，无论如何，这都是最优的选择。
有许多可能的解决方案，其中可以在一个时间间隔内完成最大数量的任务，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].
您还可以看到，在这些示例中，最早完成时间策略将始终选择最优解。请注意，对于相同数量的选定任务，可以存在多个最佳解决方案。在这种情况下，最早完成时间策略将始终选择其中之一。
我正在尝试了解贪心算法调度问题的工作原理。
所以我一直在阅读和谷歌搜索一段时间，因为我无法理解贪心算法调度问题。
我们有 n 个作业要安排在单个资源上。作业 (i) 具有请求的开始时间 s(i) 和完成时间 f(i)。
我们有一些贪心的想法select...
- 按 s 的升序接受 ("earliest start time")
- 接受 f - s 的递增顺序 ("shortest job time")
- 按冲突数量递增的顺序接受 ("fewest conflicts")
- 接受 f 的升序 ("earliest finish time")
而书上说的最后一个，按f的递增顺序接受总是会给出一个最优解。
但是它没有提到为什么它总是给出最优解，为什么其他3个不会给出最优解。
他们提供的图表说明了为什么其他三个不会提供最佳解决方案，但我无法理解它的含义。
由于我的声望低，我不能post任何图像，所以我会尝试绘制它。
‖|---| |---| |---|
|------------------------|
s 的升序
低估的解决方案
|------------| |------------|
|-----|
f-s 的递增顺序
低估的解决方案
|----| |-----| |-----| |-----|
‖|-----| |-----| |-----|
‖|-----| |-----|
‖|-----| |-----|
冲突数量递增。 低估的解决方案
这就是它的样子，我不明白为什么这是每个场景的反例。
如果有人能解释为什么每个贪婪的想法行得通/行不通，那将非常有帮助。
谢谢。
我想我可以解释一下。
比方说，我们有 n 个作业，开始时间为 s[1..n]，结束时间为 f[1..n]。所以如果我们按照完成时间排序，那么，我们总能完成最多的任务。让我们看看，如何。
如果一项工作较早完成（即使它在系列中较晚开始，这是一项短期工作），那么，我们总是有更多时间处理较晚的工作。让我们假设，在此间隔内我们还有其他工作可以 start/complete，这样我们的任务数量就会增加。现在，这实际上是不可能的，因为如果有任何任务在此之前完成，那将是完成时间最早的任务，因此我们将处理该任务。而且，如果有任何任务到现在还没有完成（但已经开始），那么如果我们选择它，我们就不会完成任何任务，但现在我们实际上至少完成了一个。所以，无论如何，这都是最优的选择。
有许多可能的解决方案，其中可以在一个时间间隔内完成最大数量的任务，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].
您还可以看到，在这些示例中，最早完成时间策略将始终选择最优解。请注意，对于相同数量的选定任务，可以存在多个最佳解决方案。在这种情况下，最早完成时间策略将始终选择其中之一。