这是MSP的TSP的实例？ [英] Is this MSP an instance of the TSP?

问题描述

在他的书中，的算法设计手册的，史蒂芬S. Skiena提出以下问题：

In his book, The Algorithm Design Manual, Steven S. Skiena poses the following problem:

＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;

            

现在考虑下面的调度问题。想象一下，你是一个高度indemand演员，谁一直psented与提供出演$ P $的 N 的正在开发不同的电影项目。每个报价自带指定了拍摄的第一天和最后一天。要接受这份工作，你必须致力于成为可在这整个期间。因此，你不能同时接受两份工作的时间间隔重叠。

Now consider the following scheduling problem. Imagine you are a highly-indemand actor, who has been presented with offers to star in n different movie projects under development. Each offer comes specified with the first and last day of filming. To take the job, you must commit to being available throughout this entire period. Thus you cannot simultaneously accept two jobs whose intervals overlap.

有关的艺术家，如自己的标准作业验收是明确的：你想尽可能多的钱越好。因为这些电影的支付每部电影同样的费用，这意味着你寻求尽可能多的就业机会（间隔），使得没有两个人互相冲突。

For an artist such as yourself, the criteria for job acceptance is clear: you want to make as much money as possible. Because each of these films pays the same fee per film, this implies you seek the largest possible set of jobs (intervals) such that no two of them conflict with each other.

例如，考虑图1.5 [上述]可用的项目。我们可以最多四部电影，分别是离散数学，编程挑战，计算投注出演，，要么停止状态或施泰纳的树之一。

For example, consider the available projects in Figure 1.5 [above]. We can star in at most four films, namely "Discrete" Mathematics, Programming Challenges, Calculated Bets, and one of either Halting State or Steiner’s Tree.

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

You (or your agent) must solve the following algorithmic scheduling problem:

问题：电影调度问题

输入：一组的 I 的的的 N 的间隔就行

Input: A set I of n intervals on the line.

输出：什么是互不重叠的间隔可以从选择最大的子集的 I 的

Output: What is the largest subset of mutually non-overlapping intervals which can be selected from I?

我不知道，这是在TSP（可能是一个简化的）？

I wonder, is this an instance of the TSP (perhaps a simplified one)?

推荐答案

这个问题可以解决，只需选择具有最早完成日期的影片，并从那里，一个 0出发（N ^ 2 ）程序（可能有更快的解决方案）。既然我们已经找到了一个多项式时间的解决方案，它不是TSP的实例，除非：（1）P = NP，和（2）有一个尴尬容易证明（1）

This problem can be solve by simply choosing the film with the earliest finish date, and proceeding from there, an O(n^2) process (there may be even faster solutions). Since we've found a polynomial time solution, it's not an instance of TSP, unless: (1) P=NP, and (2) there's an embarrassingly easy proof of (1).

这篇关于这是MSP的TSP的实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！