找到最佳点来切割一组间隔

Question

给定实线上的一组区间和一些参数 d > 0。找到相邻点之间的间隙小于或等于 d 的点序列，使得包含任何点的区间数最小化。为了防止琐碎的解决方案，我们要求序列中的第一个点在第一个间隔之前，而最后一个点在最后一个间隔之后。间隔可以被认为是右开的。

这个问题有名字吗？甚至可能是算法和复杂性界限？

一些背景： 这是由拓扑数据分析中的一个问题引发的，但它似乎很笼统，以至于它可能对其他主题很有趣，例如任务调度（假设工厂每年必须至少关闭一次并希望最小化维护造成的任务数量......）我们正在考虑整数规划和最小削减，但 d 参数不太合适。我们还在 n^2 和 n*logn 时间内实现了近似贪婪解决方案，但它们可能会遇到非常糟糕的局部最优解。

给我看一张图片

我用线画间隔。下图显示了 7 个区间。d 是这样的，您必须至少每四个字符剪切一次。在图表的底部，您会看到图表的两个解决方案（用 x 和 y 标记）。x 穿过顶部的四个区间，而 y 穿过底部的三个区间。y 是最优的。

 ——— ———
 ——— ———
   ———
   ———
   ———
x x   x x
y   y   y

给我看一些代码： 我们应该如何fun在下面的代码片段中定义？

 ——— ———
 ——— ———
   ———
   ———
   ———
x x   x x
y   y   y

在这个小例子中，最优解将削减第一个区间，但不会削减第二个和第三个区间。显然，该算法也应该适用于更复杂的例子。

更严格的测试如下：给定 [0, 100] 上间隔开始时间的均匀分布和 [0, d] 上的长度均匀分布，可以通过规则网格 [0, d, 2d] 计算预期的切割次数, 3d,..] 略低于 0.5*n。最佳解决方案应该更好：

intervals = [(0, 1), (0.5, 1.5), (0.5, 1.5)]
d = 1.1
fun(intervals, d)
>>> [-0.55, 0.45, 1.55]  # Or something close to it

Answer 1

您可以通过动态规划来最佳地解决这个问题，方法是维护一个数组S[k]，其中S[k]是最佳解决方案（覆盖最大的空间），同时k在其中有一个点的间隔。然后，您可以重复删除最低的S[k]，以所有可能的方式扩展它（将自己限制在间隔的相关端点加上S[k]+ delta 中的最后一个点），并S使用这些新的可能解决方案进行更新。当表中可能的最低值S[k]覆盖整个范围时，您就完成了。

intervaltree使用pip 的Python 3 解决方案：

from intervaltree import Interval, IntervalTree

def optimal_points(intervals, d, epsilon=1e-9):
    intervals = [Interval(lr[0], lr[1]) for lr in intervals]
    tree = IntervalTree(intervals)
    start = min(iv.begin for iv in intervals)
    stop = max(iv.end for iv in intervals)

    # The best partial solution with k intervals containing a point.
    # We also store the intervals that these points are contained in as a set.
    sols = {0: ([start], set())}

    while True:
        lowest_k = min(sols.keys())
        s, contained = sols.pop(lowest_k)
        # print(lowest_k, s[-1])  # For tracking progress in slow instances.
        if s[-1] >= stop:
            return s

        relevant_intervals = tree[s[-1]:s[-1] + d]
        relevant_points = [iv.begin - epsilon for iv in relevant_intervals]
        relevant_points += [iv.end + epsilon for iv in relevant_intervals]
        extensions = {s[-1] + d} | {p for p in relevant_points if s[-1] < p < s[-1] + d}

        for ext in sorted(extensions, reverse=True):
            new_s = s + [ext]
            new_contained = set(tree[ext]) | contained
            new_k = len(new_contained)
            if new_k not in sols or new_s[-1] > sols[new_k][0][-1]:
                sols[new_k] = (new_s, new_contained)