algorithm - 贪心算法，调度

Question

我想了解贪婪算法调度问题的工作原理。

所以我一直在阅读和谷歌搜索一段时间，因为我无法理解贪心算法调度问题。

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

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

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

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

但是它没有提到为什么它总是给出最优解，为什么其他 3 个不会给出最优解。

他们提供的图表说明了为什么其他三个不会提供最佳解决方案，但我不明白这是什么意思。

由于我的声望很低，所以我不能发布任何图像，所以我会尝试绘制它。

『|---| |---| |---|
|------------------------|
s 的升序低估的解决方案

|------------| |------------|
|-----|
f-s 的递增顺序低估的解决方案

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

『|-----| |-----| |-----|

『|-----| |-----|

『|-----| |-----|

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

这就是它的样子，我不明白为什么这是每个场景的反例。

如果有人能解释为什么每个贪婪的想法行得通/行不通，那将非常有帮助。

谢谢。

Answer 1

我想我可以解释一下。
比方说，我们有 n 个作业，开始时间为 s[1..n]，结束时间为 f[1..n] .所以如果我们按照完成时间排序，那么，我们总能完成最多的任务。让我们看看如何。

如果一项工作较早完成(即使它在系列中较晚开始，这是一项短期工作)，那么，我们总是有更多时间处理较晚的工作。让我们假设，我们有其他的工作可以在这个时间间隔内开始/完成，这样我们的任务数量就会增加。现在，这实际上是不可能的，因为如果有任何任务在此之前完成，那将是完成时间最早的任务，因此我们将处理该任务。而且，如果有任何任务到现在还没有完成(但已经开始)，那么如果我们选择它，我们就不会完成任何任务，但现在我们实际上至少完成了一个。所以，无论如何，这都是最优的选择。
有许多可能的解决方案，其中可以在一个时间间隔内完成最大数量的任务，EFT 给出了一个这样的解决方案。但它始终是可能的最大数量。

我希望我能解释清楚。