1

我正在阅读算法设计手册第 2 版。有人可以解释一下 ShortestJobFirst 和 OptimalScheduling 算法之间的区别。给出的算法如下

ShortestJobFirst(I) {

  1. 虽然 (I = ∅) 做
  2. 接受来自 I 的最短的工作 j。
  3. 删除 j，以及与 i 相交的任何区间。

}

最优调度（一）

  1. 虽然 (I = ∅) 做
  2. 接受 I 中最早完成日期的工作 j。
  3. 删除 j，以及与 i 相交的任何区间。

我无法理解其含义 “我们的调度问题和机器人问题之间的区别在于，有一种算法可以正确有效地解决电影调度问题。想想第一个终止的作业 - 即包含最右边的点的间隔 x 最左边在所有区间中。这个角色由图 1.5 中的“离散”数学扮演。其他工作很可能在 x 之前开始，但所有这些必须至少部分重叠，所以我们最多可以从组中选择一个。首先要终止的工作是 x，因此任何重叠的工作都可能会阻止它右侧的其他机会。显然，我们永远不会因为选择 x 而失败。这表明了以下正确、有效的算法——”

示例在算法设计手册（本 PDF 第 10/11 页）中。

4

1 回答 1

1

它们都是具有不同成本函数的贪心算法。一个选择运行时间最短的作业，一个选择最先完成的作业。

如果运行时间最短的作业比另一个作业开始得晚，它实际上可能不会首先完成，因此为了让我们的贪心算法更好地工作，我们需要一个不同的成本函数。

考虑：

----JJJ---
-JJJJ-JJJJ

顶部代表ShortestJobFirst。因为JJJ它比JJJJ选择运行的时间短，但是因为您一次只能运行一项作业，它会阻止其他两项作业的运行。另一种选择是OptimalScheduling选择第一个完成，表示为第二行。因为它等于或早于最短的工作完成，所以我们总是至少和我们选择最短的工作一样好。

于 2013-06-02T05:45:20.617 回答