algorithm - 任务调度中的 NP 完备性

Question

因此，这是一个发人深省的问题，可以让我的教授理解 NP 完全性的概念。由于 NP-Completeness 的规则，我知道为什么应该有一个解决方案，但我不知道如何找到它。那么问题来了:

问题是一个简单的任务调度问题，有两个处理器。每个处理器可以处理n任务中的一个，任意两个任务可以同时完成。每个任务都有一个结束时间e，必须在这个时间之前完成。每个任务还​​有一个持续时间 d。结束时间、持续时间、系统当前时间(时间将从0开始)等所有时间值均为整数。所以我们得到了一个包含 n 任务的列表，我们需要使用这两个处理器来调度它们。如果无法安排任何一个，则算法必须返回无解。请记住，顺序无关紧要，哪个处理器获得哪个任务也无关紧要，只要没有重叠并且每个任务都在截止日期之前完成即可。

所以这就是问题变得概念化/抽象化的地方，假设我们可以访问一个特殊的小函数，我们不知道它是如何工作的，我们所知道的是:给定一个 n 列表tasks 和当前的计划，它会返回 true 或 false 基于算法是否可以从这一点解决。这个函数假设已经安排好的任务是固定的，它只会改变未安排任务的时间。然而，这个函数所做的只是返回 true 或 false，如果它确实找到了解决方案，它不会给你正确的时间表。关键是您可以在调度问题的实现中使用特殊功能。目标是解决调度问题，并使用对特殊函数的多项式调用次数返回一个工作调度，其中每个作业都已正确调度。

编辑:澄清一下，问题是:创建一个解决方案来安排所有 n 任务，而不会超过截止日期，使用对“特殊函数”的多项式调用。

我认为这道题是证明验证一个解是多项式的，但是发现它是非多项式的。但是我的教授坚持认为有一种方法可以通过调用特殊函数的多项式次数来解决这个问题。由于整个问题是 NP 完全问题，这将证明运行时的非多项式方面出现在“算法的决策部分”。

如果您希望我解决任何问题，请发表评论，我知道这不是对问题的完美解释。

Answer 1

给定一个神谕 M返回 true或 false仅:

输入:任务 - 任务列表输出:schedule:每个任务的三元组(任务，处理器，开始)算法:

While there is some unscheduled task:
   let p be the processor that currently finished up his scheduled tasks first
   let x be the first available time on x
   for each unscheduled task t:
      assign t with the triplet: (t,p,x)
      run M on current tasks
      if M answers true:
            break the for loop, continue to next iteration of while loop
      else:
            unassign t, and continue to next iteration of for loop
    if no triplet was assigned, return NO_SOLUTION
return all assigned triplets

• 以上在多项式时间内运行 - 它需要 O(N^2)调用 M .
• 上述算法的正确性可以通过归纳来证明，归纳假设为After round k在 while 循环中，如果在它之前有一个解决方案，那么在它之后(以及在分配某些任务之后)仍然有一个解决方案。在证明这一说法后，算法的正确性很容易实现 k=#tasks

正式证明上述主张:

• 归纳基础对于 k=0 是微不足道的。
• 假设:对于任意k < i，“如果k轮前有解，k轮后仍有解”的说法是正确的
• 证明:

假设有一些解决方案 { (tj,pj,xj) | j=1,...,n} , 按 j<u <-> xj<xu 订购，并假设 t1,t2,...,ti-1 的分配与算法产生的相同(归纳假设)。现在，我们要分配 ti ，我们将能够做到这一点，因为我们将找到最小的可用时间戳 (xi)，并在其上放置一些任务。我们要找一些任务，因为ti是一种可能性 - 它不会“失败”并产生“NO_SOLUTION”。
此外，由于该算法在迭代i 中不产生“NO_SOLUTION” , 来自 M 的正确性, 它会产生一些任务 t , 通过分配 (t,p,x) - 仍然会有解决方案，以及步骤 i 的声明已证明。