7

编辑：现在我认为这是一个扫描线问题。（见底部的update2）

在这个问题中，我们得到了N对象和M约束。（N可以200k，M可以100k）。每个物体要么是黑色的，要么是白色的。每个约束的形式(x, y)是指在对象的范围内x..y，只有一个白色对象；其余的都是黑色的。我们想确定可以存在的白色对象的最大数量，或者是否不可能满足约束。

我观察到，如果一个约束完全包含在另一个约束中，则内部约束将决定可以放置白色对象的位置。此外，如果在另一个约束中包含多个不相交的约束，这应该是不可能的，因为它违反了每个约束只能有一个白色对象的事实。该算法应该足够快，可以在 2-3 秒内运行。

更新：其中一个答案提到了确切的封面问题；这是一个不是 NP 完全的特殊实例吗？

更新 2：如果我们将每个约束更改为开始和结束事件，并对这些事件进行排序，我们是否可以系统地扫过这些事件并分配白色对象？

4

2 回答 2

2

您的问题可以表示为精确覆盖问题：约束区间形成要覆盖的集合，每个白色对象都覆盖了它所在的约束区间。那么，您的问题是找到一个白色对象的子集，该子集恰好覆盖每个约束间隔一次。

精确覆盖问题通常是 NP 完全的，尽管这显然并不一定意味着它们的任何特定子集都是。然而，仍然存在可以非常有效地解决大多数此类问题的算法，例如Knuth 的算法 X（由dance links实现）。

您的问题的一维结构也可能允许更直接的专门解决方法。然而，算法 X 是解决此类问题的一个非常好的通用工具。（例如，最快的数独求解器通常使用类似的东西。）

于 2013-04-06T18:33:59.367 回答
1

是的，有一个（点）扫描算法。这个有点不雅，但我认为它有效。

首先，扫描嵌套间隔。按排序顺序处理开始和结束事件（决胜局留给您），并保留一个不知道包含另一个间隔的活动间隔列表。要处理开始事件，请附加相应的时间间隔。要处理结束事件，请检查相应的时间间隔I是否已被删除。如果不是，则从列表中删除之前的I所有剩余间隔。对于每一个这样的 ，将两个其并集为集差的区间附加到涂黑区间的列表中。JIJJ \ I

其次，扫一扫以收缩被涂黑的区间。换句话说，删除已知为黑色的对象，重新编号，并相应地调整约束。如果整个约束被涂黑，则没有解决方案。

第三，扫一扫，解决现在非嵌套区间的问题。贪婪的解决方案被证明是最优的。

示例：假设我有半开约束 [0, 4), [1, 3), [2, 5)。第一次扫描会产生中断 [0, 1) 和 [3, 4)。第二次扫描留下约束 [a, c), [a, c), [b, d)。* 贪婪扫描将白色对象放置在新位置 a、c、d（旧位置 1、4、5）。

第二次扫的图解：

0 1 2 3 4 5  old coordinates
[       )
  [   )
    [     )
**    **     blackouts
  a b   c d  new coordinates
[       )
  [   )
    [     )
于 2013-04-07T16:51:34.130 回答