5

所以这是一个发人深省的问题，可以让我的教授理解 NP-Completeness 的概念。由于 NP-Completeness 的规则，我明白为什么应该有一个解决方案，但我不知道如何找到它。所以这里是问题：

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

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

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

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

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

4

1 回答 1

2

M给定一个返回true或false只返回的预言：

输入：任务 - 任务列表输出：调度：每个任务算法的三元组（任务，处理器，开始）：

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.
  • 上述算法的正确性可以通过归纳来证明，其中归纳假设是在kwhile循环的一轮之后，如果它之前有一个解，那么它之后还有一个解（并且在一些任务分配之后）。在证明了这一主张之后，算法的正确性很容易实现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”。
此外，由于该算法在迭代中不会产生“NO_SOLUTION” i，因此从 的正确性来看M，它将产生一些任务t，通过分配(t,p,x)- 仍然会有一个解决方案，并且步骤的声明得到了i证明。

于 2015-04-30T07:55:02.980 回答