12

假设我有一个区间 (a,b)，以及多个子区间 {(a i ,b i )} i，它们的并集是 (a,b)。有没有一种有效的方法来选择仍然覆盖（a，b）的这些子区间的最小基数子集？

4

4 回答 4

15

从 a 或 b 开始的贪心算法总是给出最优解。

证明：考虑覆盖 a 的所有子区间的集合 S a。显然，其中之一必须属于最优解。如果我们将其替换为来自 S a的子区间 (a max ,b max )，其右端点 b max在 S a中最大（到达最右侧），剩余的未覆盖区间 (b max ,b) 将是最优解的剩余区间，因此它不能被比最优解的类似未覆盖区间更多的子区间覆盖。因此，由 (a max ,b max ) 和剩余区间的最优解 (b max,b) 也将是最优的。

因此，只需从 a 开始并迭代地选择到达最右边的区间（并覆盖前一个区间的结尾），重复直到你点击 b。我相信如果您将间隔存储在增强间隔树中，则可以在 log(n) 中选择下一个间隔。

于 2008-11-16T21:27:16.137 回答
1

听起来像动态规划。

这是算法的说明（假设间隔在按结束时间排序的列表中）：

//works backwards from the end
int minCard(int current, int must_end_after)
{
    if (current < 0)
        if (must_end_after == 0)
            return 0; //no more intervals needed
        else
            return infinity; //doesn't cover (a,b)

    if (intervals[current].end < must_end_after)
        return infinity; //doesn't cover (a,b)

    return min( 1 + minCard(current - 1, intervals[current].start),
                minCard(current - 1, must_end_after) );
           //include current interval or not?
}

但它也应该涉及缓存（记忆）。

于 2008-11-15T22:53:50.597 回答
0

有两种情况需要考虑：
情况 1：在一个区间的结束时间之后没有重叠的区间。在这种情况下，选择开始时间最短、结束时间最长的下一个区间。(amin, bmax)。
情况 2：有 1 个或多个间隔与您正在查看的最后一个间隔重叠。在这种情况下，开始时间无关紧要，因为您已经涵盖了这一点。所以优化完成时间。(a, bmax)。

案例 1 也总是选择第一个区间作为最优集中的第一个区间（证明与 @RafalDowgrid 提供的相同）。

于 2012-04-05T18:00:47.907 回答
-2

您的意思是，子区间仍然以这样一种方式重叠，即 (a,b) 在所有点上都完全覆盖？

也许将子区间本身拆分为与它们来自何处相关联的基本块，因此您可以列出每个基本块区间的选项，同时考虑子区间覆盖的其他区域。然后，您可以使用基于每个子子间隔的搜索，并且至少确保没有留下任何间隙。
然后需要搜索..有效..那会更难。

可以消除任何完全被另一组较小数字覆盖的间隔集合，并在预处理后解决问题。
对整体的最小化不就是对至少一半的最小化吗？我不知道。

找到期刊的链接，但无法阅读。:(

这将是一个命中集合问题，并且通常是 NP_hard。
也无法阅读，但看起来是相反的问题。
无法阅读它，但另一个链接提到了拆分间隔。
这是有关几何优化问题的随机算法的可用参考。这个pdf的
第35页有一个贪心算法。Karp (1972)
的第 11 页提到了 hit-set 并且被引用了很多。 谷歌结果。研究很有趣，但我现在得走了。

于 2008-11-16T00:09:29.570 回答