有一组段的{(a_i,b_i) with i = 1, ..., n}与0 <= a_i < b_i <= 1必须被布置在N行[0,1],而不重叠.
例如,如果一个集合可以由{(0.35,0.41), (0.40,0.43), (0.47,0.88)}和组成N >= 2,则可以排列没有重叠的段.随着N = 1这是不可能的,因为第一和第二部分重叠.
对于必须放置一个段的行没有任何约束,一种可能的算法如下:根据它们的起点对段进行排序a_i,然后将它们一个接一个地放在其中一个N行上.如果不能将段a_i放在任何一条线上而不与任何已经放置的段重叠,则意味着没有解决方案.
如果某些细分市场对他们必须放置的线路有限制怎么办？例如,段(a_2,b_2)可以仅放置在第3行,而将其写为(a_2,b_2;3).
一种可能的情况如下:{(0.45,0.56;-), (0.48,0.67;-), (0.66,0.70;2), (0.68,0.71;-)}和N = 2.如果将第一个段放在第一行上,则第二个段必须在第二个行上,第三个段不能满足约束.相反,如果第一段放置在第二行上,则第二段在第一行上,第三段在第二行上实现约束而第二行在第一行上.
我试过的
尝试满足约束条件的每种组合.在最后一个示例中,{1,2}x{1,2}x{2}x{1,2}在第一个没有任何重叠之后,程序返回组合,这是问题的解决方案.当然它有效,当然它很慢.
绘制一条[0,1]标有点的线,该点是至少一个线段的边界.构建I由两个连续点组成的间隔列表.对于每个元素I采取S涵盖它的段列表.对于构建的每个子集S',S该集合A'等于允许的行号的并集.例如S' = {(0.5,0.6;1,2), (0.4,0.7;2)},A' = {1, 2}.如果基数A'小于基数S',则没有解决方案.不幸的是,相反的情况并非总是如此.
2.根据其他段的约束,扫描每个间隔点并删除不能放置段的行.例如,如果某个段在第2行受到约束,则对于与其具有交集的任何其他段,这不是一个选项.继续扫描间隔列表,直到不再可能减少为止.然后将基本算法1.与此子集的可能组合一起使用.
绘制一个A大小的方阵n(n即段数).如果他们重叠则a_ij等于1,0如果他们不重叠.根据段是否具有约束,仅允许对矩阵的特定操作(如果交换两行,则必须交换相同的列,具有约束的段不能任意交换).如果可以获得具有多个对角块<= N的矩阵作为单位矩阵,那么就有解决方案.不确定它是否是可行的选择,也不确定它是否有意义.
想想I,S,S'和A'中定义2..如果基数A'小于基数S',则中止(无解).如果基数A'等于基数S',A'则从与每个元素相交的段中删除行号S'.
继续扫描,I直到不再可能减少为止.是否真的如果程序没有中止到这一点,那么剩下的就是问题的所有可能的解决方案？(是的,但不仅仅是那些)
例如N = 3,S = {(0.5,0.6;1,2), (0.4,0.7;2), (0.5,0.6;1,2,3)}.其中一个子集就是S' = {(0.5,0.6;1,2), (0.4,0.7;2)}其中一个A' = {1,2}.的基数S'等于基数A',因此人们必须除去{1,2}从允许不是在每个段中的行S'.一个人获得S = {(0.5,0.6;1,2), (0.4,0.7;2), (0.5,0.6;3)}.对第一个段执行相同操作S' = {(0.4,0.7;2)},2并从中获取一个S = {(0.5,0.6;1), (0.4,0.7;2), (0.5,0.6;3)},这是(单个可能的)解决方案.
反例:for N = 2和{(0.5,0.6;-), (0.55,0.7;-), (0.65,0.8;-)},并非每个组合{1,2}x{1,2}x{1,2}都是一个解决方案.原因与(真)解的对称性有关.如果在算法的每次完整运行之后,将其中一个段固定在其允许的一条线上(从而破坏对称性)并重新运行算法,则获得该建议集的解.
这种方式总是可以得到一个解决方案(当它存在时)或程序在不存在时中止吗？
如果5.是正确的,是否可以n从分段解决方案中计算分段的解决方案n-1？
Obeservations(来自评论和我)
强制某些段在某些特定行上的约束可以放宽很多,因为在完成解决方案后,您可以完全自由地重新编号行,而无需更改单行上的段是否重叠.因此,例如,如果两个段应该在第5行,那么所有这些意味着它们必须在同一条线上 ; 如果一个段应该在第3行而另一个在第7行,那么所有这些意味着它们必须位于不同的行上.
如果任何x段未覆盖任何点,则问题可以分为2个具有行[0,x]和[x,1]长和两组不同段的问题.因此,必须假设每个点[0,1]都被至少一个段覆盖.