1

Steven S. Skiena在他的《算法设计手册》一书中提出了以下问题：

            在此处输入图像描述

现在考虑以下调度问题。想象一下，您是一个需求量很大的演员，他收到了在正在开发的n 个不同电影项目中出演的提议。每个优惠都在拍摄的第一天和最后一天指定。要接受这份工作，您必须承诺在整个期间都有空。因此，您不能同时接受间隔重叠的两个工作。

对于像你这样的艺术家来说，接受工作的标准很明确：你想尽可能多地赚钱。因为这些电影中的每部电影都为每部电影支付相同的费用，这意味着您寻求尽可能多的工作（间隔），这样它们中的任何一个都不会相互冲突。

例如，考虑图 1.5 [上图] 中的可用项目。我们最多可以出演四部电影，即“离散”数学、编程挑战、计算赌注，以及停止状态或施泰纳树中的一部。

您（或您的代理）必须解决以下算法调度问题：

问题：电影调度问题

输入：线上的一组n 个区间。

输出：可以从I中选择的相互不重叠区间的最大子集是多少？

我想知道，这是 TSP 的一个实例（也许是一个简化的实例）？

4

2 回答 2

1

这个问题可以通过简单地选择完成日期最早的电影来解决，然后从那里开始一个O(n^2)过程（可能有更快的解决方案）。由于我们找到了多项式时间解，它不是 TSP 的一个实例，除非：(1) P=NP，并且 (2) (1) 的证明非常简单。

于 2013-08-24T12:35:25.213 回答
-2

以下是解决此问题的方法：

  1. 创建一棵树，其顶点为薄膜，边缘重叠。也就是说，如果两个顶点的时间表重叠，则两个顶点由一条边连接。因此，这个问题可以重述如下：“给定一个图 G，找到未连接顶点的最大子集。”

  2. 现在可以将上述问题与已知的 NP-hard 问题联系起来。具体来说，创建一个具有相同顶点和互补边的图 G'。也就是说，如果原始图 G 没有，则 G' 在顶点之间有一条边。现在问题可以这样重新表述：“给定一个图 G'，找到最大团，其中团是所有顶点相互连接的子集。”

Clique 是一个众所周知的 NP-hard 问题。因为您的调度问题等同于 Clique - 瞧！这也是NP难的。

于 2013-08-23T23:44:38.437 回答