好吧,我们有作业调度的贪心算法(调度最大数量的作业)。我们可以使用不同的技术
- 最短的工作优先
- 最早开始时间优先
- 首先是冲突最小的工作
- 最早结束时间优先
我有前三个策略的反例,但找不到第四个策略的反例。
这里是前三种方法的反例
最短作业优先:
最早开始时间优先:
在这里,我们可以安排 6 个较小的作业,这些作业稍后开始,而不是安排在一个较早开始的作业上
冲突最小的作业优先:
在这里我们可以安排 4 个冲突为 3,4,4,3 的作业,而不是 3 个冲突最小的作业,即 2,3,3
那么,最后一个最早结束时间优先的反例是什么?我找不到这个的反例。那么,它总是为每组数据给出一个最优解?
更新 1:
我有一个执行者来执行作业,我想执行最大数量的作业。
最佳答案
Earliest End time First 是贪心算法,为上述问题给出最优算法。 (其实你说的这个问题叫Interval Scheduling问题)
证明可以使用 charging argument 完成.您将贪婪算法的输出与最优解进行比较,并争辩说您的解并不比最优解差。
关于algorithm - 作业调度算法的反例 "Earliest End time First",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39240310/