假设我有一个循环时间线（24 小时周期），在这 24 小时内有 n 个点。我想以给定的固定长度 k (<24h) 的间隔覆盖所有点，并且我想使用尽可能少的间隔。是否有一个很好的算法来确定最佳间隔的起点？
如果我们不允许间隔“环绕”，那么它变得容易（我们可以简单地安排第一个间隔从第一个点开始，覆盖尽可能多的点并为下一个间隔选择下一个点等） .
一个天真的二次解决方案是尝试将每个点作为“第一个”区间的起点并按照上述方式进行操作，但我觉得我们可以做一些更聪明的事情？
问问题
417 次
3 回答
1
简单的答案是……约束编程：
- 给你一组 P 点（比如从午夜开始的分钟数）和 k 间隔长度
您想要长度为 k 的最小间隔数（一组 S 表示间隔的开始），使得
一个。对于所有 p elem P，在 S st p >= s && p <= s+k 中存在 s，换句话说，所有给定点都被“覆盖”（如果你想要它循环，只需在 s+k 上使用 mod）
湾。对于所有 S，不存在 S'st，S' 中的元素数小于 S 中的元素数。换句话说，结果集具有最小基数。
将其提供给 gecode ......你就完成了。
间隔有多种可能的表示，K Apt 的“约束编程原理”一书中很好地解释了权衡。
于 2013-06-25T00:46:34.163 回答
1
请注意您建议的朴素二次解决方案：您需要将每个点视为间隔开始或间隔结束。
我不确定这是最佳解决方案，但它比天真的二次方更好：
让我们将点命名为{P1, ..., Pn}。
由于任何点都必须被至少一个区间覆盖，因此找到所有可能覆盖点P1的区间（假设区间要么从 Pi 开始，要么在 Pi 结束）。对于这些间隔中的每一个，贪婪地继续，就像在线性时间线上一样。
为了进一步优化它，我们需要找到最好的起点，而不是从P1开始——这将是最小数量的间隔可能覆盖的点。我不知道我们是否可以在线性时间内做到这一点，但一个好的启发式方法可能是从它与两个邻居的距离之和最大这一点开始。
编辑：寻找最佳起点的 O( nlogn ) 方式：
我们可以建立一个可能的2n段的列表（对于任何点Pi，一个区间可以从 Pi 开始或在Pi结束）。接下来，将这些区间插入到段树中。
不要使用常规的段树，而不是将区间存储在规范子集中，只需存储它们的数量（参见 Wikipedia 文章中的注释部分）。
树的构建需要 O( nlogn ) 时间。现在，对于每个点Pi，计算它落入的段数（间隔）。每个点需要 O( logn )，或者总共需要 O( nlogn )。
选择间隔数最少的点。如上所述，对于每个间隔继续使用贪心方法。
于 2013-06-24T19:41:35.990 回答
0
也许您可以使用空间填充曲线和带有四键的层次集群。有一个法国网站按照空间填充曲线排列日子：http: //lapin-bleu.net/riviera/ ?p=78 。但是二次算法的问题是什么？
于 2013-06-24T20:09:09.900 回答