1

这是算法大师的问题:-)

S是一组可能重叠的自然数区间和b一个盒子大小。假设对于每个区间,范围严格小于b

我想找到大小间隔的最小集合b(我们称之为M),因此所有间隔S都包含在M.

简单的例子:

S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
b = 10
M = {[1..10], [8..18]}
// so ([1..4], [2..7], [3..5]) are inside [1..10] and ([8..15], [9..13]) are inside [8..18]

我认为贪心算法可能并不总是有效,所以如果有人知道这个问题的解决方案(或可以转换成的类似问题),那就太好了。

谢谢!

更新我一直在考虑更多关于它,也许我的第一个直觉是错误的,贪婪算法就是解决这个问题的方法,因为最后所有的间隔都需要被覆盖,它不会使任何选择超级间隔的方式不同......我应该删除这个问题还是有人可以断言这个?

4

2 回答 2

4

算法可能如下。

  1. a = 0
  2. curr = S 中 > a 的最小数。(在我们的例子中 = 1. in [1..4])
  3. 向 M 添加一个区间 [curr..b]。(在我们的例子中 M = {[1..10]})
  4. a = M 中的最大上界。(在我们的例子中 a = 10 )
  5. 转到 2。
于 2010-03-22T16:15:42.663 回答
3

是的,贪心算法是最优的。非正式地,考虑任意解 M。我们将把它转换为贪心解 M' 的超集,而不增加区间数。反复考虑M-M'中最左边的区间I。设 s 是 S 中最左边的区间,其中 I 是 M 中包含 s 的最左边区间。从左到右的贪心算法选择一个区间 I',其左边缘与 s's 对齐。我首先声称 I' 在 I 的右边,因为 I' 是包含 s 的最右边的区间,其次,M - {I} U {I'} 是一个有效的解决方案,因为 I 包含的唯一区间但不是 I' 在 s 的左侧,因此已经包含在某个其他间隔中。不在贪心解中的区间数减少了,所以我们最终达到了贪心解。

于 2010-03-22T16:42:24.857 回答