非重叠区间的贪婪选择

Question

我正在尝试实现 this paper（GBDP 策略，"matching distance"）中描述的算法，需要一些说明。

基本上，问题是我有一个项目列表，其中每个项目都有一个长度和一个间隔（实际上是两个间隔，但它是同一个想法）。

ID    LENGTH    START    END
1     1000      1        1000
2     20000     5        20005
3     20        30500    30520
4     500       30500    31000
5     200       900      1100

目标是找到具有非重叠范围的项目子集。在论文中，他们说他们首先按长度

对项目进行排序

ID    LENGTH    START    END
2     20000     5        20005
1     1000      1        1000
4     500       30500    31000
5     200       900      1100
3     20        30500    30520

然后继续 "greedily choosing a subset of [items] with non-overlapping intervals." 这就是我感到困惑的地方。我知道贪心算法是什么，但我不确定作者在这里的意思。我猜他们可能只是浏览了列表，只保留那些不与上面的项目重叠的项目。

ID    LENGTH    START    END
2     20000     5        20005
4     500       30500    31000
5     200       900      1100
3     20        30500    30520

请注意，使用这种方法，结果仍然包括具有重叠范围（4 和 3）的项目。

我设法在 Perl 中轻松实现了这种方法，但我认为这可能不是作者的意图。他们的意思是保留不与上面其他项目 any 重叠的项目吗？如果有人解释 "greedy selection" 在这种情况下的含义，我将不胜感激。

Answer 1

你几乎到最后都是正确的（在不正确的地方，你提出了正确的解释作为一个选项）。

首先，如您所说，对事物进行排序，使长度递减：

ID    LENGTH    START    END
2     20000     5        20005
4     500       30500    31000
5     200       900      1100
3     20        30500    30520

现在我们将贪婪地选择间隔，只要它们不与之前选择的任何冲突。因此，选择的集合最初为空，

最初，2 是我们可以做出的最贪婪的选择（长度为 20000）。它不冲突，所以我们将它添加到选择的集合中。
4 和 5 同上。选择的集合现在是 {2, 4, 5}.
下一个贪婪的（以及简单剩余的）选择是 3。由于它与前面的 any 冲突，即 4，我们不能使用它。

结果是{2, 4, 5}，因此。

仅供参考，这与计算机科学中的一个著名问题 - 间隔调度密切相关。如果您尝试优化总 number 场比赛，而不是总 length 场比赛，您 sort by end position and greedily choose.

非重叠区间的贪婪选择

Greedy Selection of Non-overlapping Intervals

algorithm

sorting

bioinformatics

greedy