algorithm - 流程分配算法

Question

我读了一些关于算法的材料，遇到了一个问题。
我们有n个进程，每个进程都有一个预定的开始和结束时间。我们希望使用最少数量的处理器来运行所有这些进程。
考虑以下算法：
在步骤i中，选择当前未分配的进程的最大数量，不重叠，并将它们分配给处理器I。
当没有进程保持未分配状态时，此算法完成。最大i是该算法的输出。n的最小值是多少，这样该算法就不会产生最佳答案？
简而言之：n=5。不过，我不知道这个答案是怎么得出的。你能解释一下吗？

Answer 1

这里有一个贪婪的算法。贪婪算法在每一步都尽其所能，希望这能给出一个整体最优解。它通常给出一个快速算法，并且它有时，但不总是，导致一个最优解。
你的算法是贪婪算法的一个很好的例子，它有时提供一个最佳的解决方案，有时没有。它的优点是它在给出一个近似最优解的过程中运行得很快；这有时比一个给出最优解的非常慢的算法更好。
你的问题有一个重要的含糊不清之处。你说，在步骤i，你应该选择在处理器I上可以调度的剩余进程的最大数量。假设当前可以调度的进程的最大数量是2。如果有很多方法可以选择两个不重叠的过程呢我们如何决定哪两个过程？
我要小心地解决这个模棱两可的问题。假设算法将不确定性地选择一组最大的进程来调度当前处理器。这意味着我们可以把你的问题变成两个不同的问题：
这个算法可能是次优的最小n是多少也就是说，假设算法在选择极大集时是不吉利的。出问题的速度有多快？
这个算法被保证为次优的最小n是多少也就是说，假设算法总是幸运的，如果有一个最大集，则选择正确的极大集。那么事情会以多快的速度出错呢？
你说n=4告诉我你把它解释为第一个问题。我想第二个问题的答案是n=7，尽管我不确定这是一个有趣的问题，我想我会问一个后续问题，我的想法！
如果我们不走运的话，这里是如何看到事情会出错的，n=4我们用时间单位来谈吧在这个例子中，我们将说有四个时间单位（如果您愿意，一天中有四个小时，每个过程需要一个完整的小时数，从一小时开始到结束）假设我们需要运行四个进程：
[1]（即，该过程只占用第一个时间单位）
[2,3,4]（即过程需要时间单位2到4）
[1,2,3]（等）
[4]
现在，有一个分配只适用于两个处理器。在第一个处理器上，我们运行[1]和[2,3,4]；在第二个处理器上，我们运行[1,2,3]和[4]我们的贪婪算法可能会找到这个解并给我们一些最优的结果。但是它可能会调度[1]和[4]在第一个处理器上运行，因为这也是一个最大的集合（它把两个进程放到第一个处理器上）。如果它这样做了，那么就剩下[1,2,3]和[2,3,4]，它们不能一起运行，所以它最终将使用三个处理器。
如果n=4，它可能会出错。n=3会出错吗？我不这么认为。最佳解决方案可能有三种可能：它只需要1个处理器，或2个处理器，或3个处理器如果最优解只需要一个处理器，那么这意味着这三个进程都可以在第一步调度，我们的贪婪算法将找到这个解。如果它需要3个处理器，那么没有两个进程可以同时调度，因此贪婪算法将一次调度一个，并再次找到最优（3个处理器）解决方案。如果需要两个处理器，那么必须是两个进程可以一起运行。如果这是正确的，那么贪婪算法将在第一步选择两个进程。无论它选择哪两个，只剩下一个，这将安排在第二步。所以贪婪算法需要2个处理器，这也是最优的。
正如我所说的，我认为乐观的情况更有趣：这个算法被保证为次优的最小n是多少我会问一个后续问题，并链接到这个！
这是follow-up question。