7

编辑:现在我认为这是一个扫描线问题。(见底部的update2)

在这个问题中,我们得到了N对象和M约束。(N可以200kM可以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 回答