我有两个间隔序列。
第一个是固定的且不重叠,类似于:
第二个不是固定的,因此它只是一个区间长度的有序列表:
手头的任务是:
最优的解决方案是将长度为10的区间放置在[58..68]处,将长度为12的区间放置在[74..86]处,这样只有数字25、26和77在一个列表中而不在另一个列表中。
我能想到的唯一有点帮助的事情是,如果我按顺序放置区间,我知道已经创建的区间有多少“惩罚”,因此我有一个上限分数,这意味着我有一个可接受的启发式,并且我可以进行A*搜索而不是查看整个树。然而,数字的总范围从0到约3400万,所以我需要更好的方法。
任何帮助都会很热情!
第一个是固定的且不重叠,类似于:
[1..10], [12..15], [23..56], [72..89], ...
第二个不是固定的,因此它只是一个区间长度的有序列表:
[7, 2, 5, 26, ...]
手头的任务是:
- 将第二个列表中的每个区间放置在给定的起始点,使得第二个列表成为一个固定的、不重叠的区间列表,就像第一个列表一样,并保持其顺序
- 找到最小化整数数量的对齐方式,这些整数在其中一个列表的某个区间中,但不在另一个列表的任何区间中
[25..26], [58..68], [74..76], [78..86]
[10, 12]
最优的解决方案是将长度为10的区间放置在[58..68]处,将长度为12的区间放置在[74..86]处,这样只有数字25、26和77在一个列表中而不在另一个列表中。
我能想到的唯一有点帮助的事情是,如果我按顺序放置区间,我知道已经创建的区间有多少“惩罚”,因此我有一个上限分数,这意味着我有一个可接受的启发式,并且我可以进行A*搜索而不是查看整个树。然而,数字的总范围从0到约3400万,所以我需要更好的方法。
任何帮助都会很热情!