algorithm - 定位一个有序的间隔序列以最大程度地与另一个固定间隔序列对齐

Question

我有两个间隔序列。

第一个是固定的且不重叠的，所以像这样:

[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 到大约 34M，所以我想要更好的东西。

任何帮助都会很热!

Answer 1

好的，这是一个经过深思熟虑的答案。它应该在多项式时间内工作，但我没有费心检查索引是什么。很可能会得到比此处概述的答案更好的索引。细节作为练习留给读者 :-) 我希望它不会太不清楚。

我将解决方案的分数定义为出现在两个区间列表中的整数个数。设 f(i,m) 是仅使用前 i 个区间长度可能获得的最高分，条件是你的区间都不超过 m。对于固定的 i，函数 f 本质上是一个从整数到整数的有界子集的(非严格)递增函数。因此:

• 当 m > 0 时，f(i,m) 的所有值都相等，除了有限的许多异常(exception)；
• 对于 m < 0，f(i,m) 的所有值都相等，只有有限的许多异常(exception)。

这意味着可以使用有限数据结构来表示 f(i,m) 的所有值(仍然考虑 i 的固定值)。

现在让 F(i) 成为代表 f(i,m) 所有值的数据结构的值。我声称，给定 F(i)，可以计算 F(i+1)。为此，我们只需要为所有 x 回答以下问题:如果我将新区间放在 x 处，我能得到的最佳解决方案有多好？但我们知道这是什么 - 它只是 f(i,x) + 我们从这个区间得到的分数。

因此，如果 n 是第二个列表中的间隔数，则最佳解决方案的分数将为 F(n)。

要真正找到解决方案，您可以从这里开始倒推。

您知道您可以获得的最高分是多少。假设它是 s_0。然后把最后一个区间尽量往左边放，条件是它能让你得分s_0。即找到最小的m使得f(n,m) = s_0；并放置间隔，使其仅停留在 m 处的边界内。

然后，让 s_1 成为您需要从所有其他间隔获得的分数，以便获得总计 s_0。 next-last区间尽可能放在最左边，条件是你仍然可以得分s_1。即找到最小的m使得f(n,m) = s_1；并放置间隔，使其仅停留在 m 处的边界内。

等等……