algorithm - 找到最佳点以切割一组间隔

Question

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

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

一些背景: 这是由拓扑数据分析中的一个问题引起的，但它看起来很笼统，可能对其他主题很有趣，例如任务安排(给定一家工厂每年至少要停产一次，并希望尽量减少维护造成的任务数量……) 我们在想 integer programming和 minimum cuts ，但 d 参数不太适合。我们还在 n^2 和 n*logn 时间内实现了近似贪心解决方案，但它们可能会遇到非常糟糕的局部最优。

给我看一张照片

我用线画间隔。下图显示了 7 个间隔。 d 是这样的，你必须至少削减每四个字符。在图表的底部，您可以看到图表的两个解决方案(标有 x 和 y)。 x 穿过顶部的四个区间，而 y 穿过底部的三个区间。 y 是最优的。

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

给我一些代码: 我们应该如何定义以下代码段中的 fun？

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

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

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

n = 10000
delta = 1
starts = np.random.uniform(low=0., high=99, size=n)
lengths = np.random.uniform(low=0., high=1, size=n)
rand_intervals = np.array([starts, starts + lengths]).T
regular_grid = np.arange(0, 101, 1)
optimal_grid = fun(rand_intervals)

# This computes the number of intervals being cut by one of the points
def cuts(intervals, grid):
    bins = np.digitize(intervals, grid)
    return sum(bins[:,0] != bins[:,1])

cuts(rand_intervals, regular_grid)
>>> 4987  # Expected to be slightly below 0.5*n
assert cuts(rand_intervals, optimal_grid) <= cuts(rand_intervals, regular_grid)

Answer 1

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

使用 pip 中的 intervaltree 的 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)