将一个有序区间序列定位到另一个固定区间序列以实现最大对齐

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到约3400万，所以我需要更好的方法。

任何帮助都会很热情！

- user3099140

---

有趣的问题。这与最佳适配内存分配不完全相同，因为您希望针对整个集合进行最佳适配，而不仅仅是一次一个长度，但它类似于您可用范围不重叠。您实际上并不关心使用哪个块，因此等长块是可替换的；这应该让您执行更简单的搜索，然后扩展结果。预先计算组合长度的存在（即，在微不足道的情况下知道如果任何范围可以接受长度为24，那么这立即是一个最优解）也可能加快速度。...玩得开心.... - keshlam

我闻到了动态规划的味道.. - phs

关于动态规划，我没有看到它。 如果递归函数的定义是在固定一个区间后查找最佳匹配，则问题没有相同的子问题（即根据放置第一个区间的位置不同，放置其他区间是不同的任务）。 - user3099140

Answer 1

好的，这里是一个半成品的答案。它应该可以在多项式时间内运行，但我没有费心去检查索引是什么。可能有可能获得比这里概述的答案更好的索引。细节留给读者作为练习 :-) 希望不会太不清楚。

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

• 所有f(i,m)的值，对于m>0，都相等，除了有限个例外；
• 所有f(i,m)的值，对于m<0，都相等，除了有限个例外。

这意味着可以使用有限的数据结构来表示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。将倒数第二个区间尽可能向左放置，但仍需满足能够获得 s_1 的条件。也就是说，找到最小的 m 使得 f(n,m) = s_1；并将该区间放置在恰好留在 m 边界内。

如此往复...

- David Knipe

---

这里有几个问题我还没有理解透彻，但主要是我不明白这如何保证最优性。你知道对于任何m，f(0, m)都是0。你可以通过查看添加第一个区间后可以获得的最佳分数来获得f(1, m)，因为它允许放置的位置没有歧义。但是对于f(2, m)，通过添加第二个区间可以获得的最佳分数取决于您放置第一个区间的位置。你的算法中哪一部分实际上将分数限制在除了sum(length(interval) for interval in intervals)之外的任何其他地方？ - user3099140

我的问题实际上是，为了从f(i)到达f(i+1)，您需要遍历所有f(i)的最优解列表，以将它们用作添加间隔i + 1的基础，因为重叠是被禁止的。最优解列表呈指数增长趋势。请忽略关于边界的最后一个问题。 - user3099140

我先从（稍微）简单的任务开始，即找出最佳解决方案的好坏程度，而不实际找到解决方案。假设我们知道F(i)，并想计算F(i+1)。对于任何m，我们可以找到在新区间以m为起点的情况下可能的最佳得分；它只是f(i+m)+(新区间的得分)。注意：我们只需要f(i,m)而不需要解决方案的详细信息。将此得分称为g(i,m)。让w成为新区间的宽度；那么这样的解决方案的边界是m+w。因此，f(i+1,m'+w)是所有m<=m'的g(i,m)的最大值。 - David Knipe

好的，我之前没有理解你是强制让新区间从m之后开始，但这样做并不能保证最优性。对于[1..2]、[4..5]、[7..8]、[10..11]、[13..14]、[16..17]、[19..21]和3、2、2、2、2、2，我们有F(1)等于f(1, 21) = 3。然后所有n > 1的F(n)仍然是3。关键在于：仅为一个区间获得最佳分数可能会导致您失去在添加更多区间时获得最佳分数的机会，因此这种方法行不通。我有什么遗漏吗？ - user3099140

首先，不要担心我的数字可能会出错。我在之前没有计算所有的细节。F(i) 不仅是 f(i,m) 的一个值，它是一个数据结构，告诉您 f(i,m) 的所有值。因此，F(1) 告诉我们：f(1,1)=0，f(1,2)=1，f(1,3)=2，...，f(1,21)=2，f(1,22)=3。从这里，我们可以得到 g(1,m) 的所有值。例如，对于 g(1,15)，我们将区间 2 放置在 [15,16]（分数+1）；因此，最佳的总分数=（来自区间 1 的最佳分数）+1=f(1,15)+1=2+1=3。另外，g(1,14)=3；但是，g(1,13)=f(1,13)+2=4。然后，f(2,17)=max_{m<=15}g(1,m)，它刚好是 4。因此，我们可以计算出所有 m 的 f(2,m)。 - David Knipe