1

这个问题的灵感来自另一个关于进程分配的问题。这是对那里讨论的问题的一种扭曲和增强。

我们有n 个进程，我们需要将它们分配给尽可能少的处理器。每个进程都有一个预定的开始和结束时间，我们将根据时间单位来定义，从 1 开始索引；一个进程将运行一些连续的时间单位序列。然后可以调度处理器运行任意数量的非重叠进程。

明显的贪心算法是：

在每一步，将剩余进程的最大不重叠集调度到下一个处理器上。

如何选择最大不重叠集？我们将算法保留为non-deterministic，因为这样更容易分析和拆分为两个子问题。

本质上，前一个问题涉及算法不走运时的行为：该算法可能产生次优分配的最小n是多少（即，需要比必要更多的处理器）？事实证明，答案是n = 4。在某些情况下，两个处理器就足够了，但贪心算法可能需要三个处理器（尽管如果幸运的话，它会分两步完成）。

这个问题涉及如果非确定性总是幸运的会发生什么：

保证该算法次优的最小n是多少？也就是说，我们可以找到一组进程的最小n是多少，其中贪心算法必须使用比必要更多的进程？

由于 Stack Overflow积极鼓励提出和回答你自己的问题，所以我会在这里这样做，你可以告诉我我的部分答案是否可以改进！

4

1 回答 1

0

我认为答案是n = 7。我将尝试证明n = 7 会出错；但这只是给出了一个上限。n = 6会出错吗？我不这么认为，但我不确定。

上限

假设我们有以下进程要调度：

  • [1]（即进程在时间单位 1 期间运行）
  • [2]
  • [4]
  • [5]
  • [1,2,3]（即，进程在时间单位 1 到 3 期间运行）
  • [2,3,4]
  • [3,4,5]

最佳分配看起来需要三个处理器：

  1. [1],[2,3,4]
  2. [2],[3,4,5]
  3. [1,2,3], [4],[5]

但是贪心算法会产生以下结果：

  1. [1], [2], [4],[5]
  2. [1,2,3]
  3. [2,3,4]
  4. [3,4,5]

这里的关键是它会在第一步安排四个（因为它很贪心），然后我们剩下三个成对重叠的过程。

下限

n = 6会出错吗？我不这么认为，但我不确定。在我看来，相关情况似乎是最佳解决方案需要三个处理器，每个处理器运行两个进程。我们能否找到贪心算法在第一个处理器上调度三个，然后留下三个重叠的进程，因此总共需要四个处理器的情况？

我们需要三对，以获得最佳解决方案；但是我们需要以这样一种方式构建这些流程，即如果您在第一步中安排了其中的三个，那么您将无法分两步完成。显然，这三个过程不能包括其中一对，否则解决方案可以像处理对一样继续，但将其中一个作为单例。所以它必须从每一对中取一个。

如果一个进程可能需要不连续的时间块，我们可以这样做：

  • [1]
  • [2]
  • [3]
  • [1,2]
  • [2,3]
  • [1,3]（这是不允许的，因为它会停止并重新开始！）

最佳解决方案是将每个单例与其补码配对；贪心算法会在第一步将所有单例放在一起，然后我们剩下的成对重叠过程将需要另外三个处理器。但是我们作弊了，因为上面列出的最后一个进程没有运行一个连续的时间块。

我们不能将最后一个更改为[3,4]，因为这样它就可以在与 . 相同的处理器上运行[1,2]。事实上，我们不能有三个成对重叠的连续块，除非它们的交集是非空的。所以我们最终会得到类似[1,2,3], [2,3,4],的东西[3,4,5]，就像我们在七个流程案例中所做的那样。问题是似乎不可能再添加三个可以一起调度的进程，并且仍然允许三处理器最优解决方案，而不允许使用三元组之一调度两个单例。如果我们尝试

  • [1]
  • [2]
  • [4]
  • [1,2,3]
  • [2,3,4]
  • [3,4,5]

那么贪心算法可能会在第一步安排[1], [2], ，这将导致最优解（我们正在寻找一种保证非确定性导致次优解的情况）。[3,4,5]

如果我们尝试

  • [2]
  • [3]
  • [4]
  • [1,2,3]
  • [2,3,4]
  • [3,4,5]

那么我们在三个处理器上没有最优解，因为其中四个进程需要时间单位 3。

所有这些思考都向我表明，贪婪算法在n =6 的情况下将是最优的，因此n =7的上限是严格的；但它相当缺乏证明。我们如何证明它对于n =6 总是最优的？

于 2014-10-18T20:16:17.233 回答