找到最佳点以切割一组间隔
Find optimal points to cut a set of intervals
给定实线上的一组区间和一些参数 d > 0。找到相邻点之间的间隙小于或等于 d 的点序列，使得包含任何点的区间数最小化.
为了防止简单的解决方案，我们要求序列中的第一个点在第一个区间之前，最后一个点在最后一个区间之后。区间可以认为是右开的。
这个问题有名字吗？甚至可能是算法和复杂性界限？
一些背景：
这是由拓扑数据分析中的一个问题引起的，但它看起来很笼统，可能对其他主题很有趣，例如任务安排（给定一家工厂每年至少要停产一次，并希望尽量减少维护造成的任务数量……）
我们在考虑 integer programming and 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, 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)
您可以通过维护数组 S[k] 通过动态规划最佳地解决此问题，其中 S[k] 是最佳解决方案（涵盖最大数量的 space），同时具有 k 间隔中有一个点。然后你可以重复删除你的最低 S[k]，以所有可能的方式扩展它（将你自己限制在区间的相关端点加上 S[k] + delta 中的最后一个点），并更新 S 与那些新的可能的解决方案。
当您的 table 中的最低可能 S[k] 覆盖整个范围时，您就完成了。
A Python 3 使用来自 pip 的 intervaltree 的解决方案：
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)
如果范围和精度可以迭代，我们可以先合并并计算间隔。例如，
[(0, 1), (0.5, 1.5), (0.5, 1.5)] ->
[(0, 0.5, 1), (0.5, 1, 3), (1, 1.5, 2)]
现在让 f(n, k) 代表数轴上 k 点到 n 的最优解。那么：
f(n, k) = min(
num_intervals(n) + f(n - i, k - 1)
)
num_intervals(n) is known in O(1)
from a pointer in the merged interval list.
n-i is not every precision point up to n. Rather, it's
every point not more than d back that marks a change
from one merged interval to the next as we move it
back from our current pointer in the merged-interval
list.
需要注意的一个问题是，我们需要为任何最优 f(n, k) 存储最右边点和前一点之间的距离。这是为了避免加入 f(n - i, k - 1)，其中倒数第二个点与当前 n 的距离小于 d，从而使新的中间点 n - i 变得多余且无效这个解决方案。 （我不确定我是否充分考虑了这个问题。也许有人可以指出不对的地方。）
我们如何知道 k 是否足够高？鉴于最优解可能低于当前k，我们假设递归会阻止我们根据上段的思路找到一个实例：
0.......8
——— ———
——— ———
———
———
———
x x x x
y y y
d = 4
merged list:
[(1, 3, 2), (3, 4, 5), (4, 5, 3), (5, 6, 5), (6, 8, 2)]
f(4, 2) = (3, 0) // (intersections, previous point)
f(8, 3) = (3, 4)
There are no valid solutions for f(8, 4) since the
break point we may consider between interval change
in the merged list is before the second-to-last
point in f(8, 3).
给定实线上的一组区间和一些参数 d > 0。找到相邻点之间的间隙小于或等于 d 的点序列，使得包含任何点的区间数最小化. 为了防止简单的解决方案，我们要求序列中的第一个点在第一个区间之前，最后一个点在最后一个区间之后。区间可以认为是右开的。
这个问题有名字吗？甚至可能是算法和复杂性界限？
一些背景： 这是由拓扑数据分析中的一个问题引起的，但它看起来很笼统，可能对其他主题很有趣，例如任务安排（给定一家工厂每年至少要停产一次，并希望尽量减少维护造成的任务数量……） 我们在考虑 integer programming and 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, 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)
您可以通过维护数组 S[k] 通过动态规划最佳地解决此问题，其中 S[k] 是最佳解决方案（涵盖最大数量的 space），同时具有 k 间隔中有一个点。然后你可以重复删除你的最低 S[k]，以所有可能的方式扩展它（将你自己限制在区间的相关端点加上 S[k] + delta 中的最后一个点），并更新 S 与那些新的可能的解决方案。
当您的 table 中的最低可能 S[k] 覆盖整个范围时，您就完成了。
A Python 3 使用来自 pip 的 intervaltree 的解决方案：
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)
如果范围和精度可以迭代，我们可以先合并并计算间隔。例如，
[(0, 1), (0.5, 1.5), (0.5, 1.5)] ->
[(0, 0.5, 1), (0.5, 1, 3), (1, 1.5, 2)]
现在让 f(n, k) 代表数轴上 k 点到 n 的最优解。那么：
f(n, k) = min(
num_intervals(n) + f(n - i, k - 1)
)
num_intervals(n) is known in O(1)
from a pointer in the merged interval list.
n-i is not every precision point up to n. Rather, it's
every point not more than d back that marks a change
from one merged interval to the next as we move it
back from our current pointer in the merged-interval
list.
需要注意的一个问题是，我们需要为任何最优 f(n, k) 存储最右边点和前一点之间的距离。这是为了避免加入 f(n - i, k - 1)，其中倒数第二个点与当前 n 的距离小于 d，从而使新的中间点 n - i 变得多余且无效这个解决方案。 （我不确定我是否充分考虑了这个问题。也许有人可以指出不对的地方。）
我们如何知道 k 是否足够高？鉴于最优解可能低于当前k，我们假设递归会阻止我们根据上段的思路找到一个实例：
0.......8
——— ———
——— ———
———
———
———
x x x x
y y y
d = 4
merged list:
[(1, 3, 2), (3, 4, 5), (4, 5, 3), (5, 6, 5), (6, 8, 2)]
f(4, 2) = (3, 0) // (intersections, previous point)
f(8, 3) = (3, 4)
There are no valid solutions for f(8, 4) since the
break point we may consider between interval change
in the merged list is before the second-to-last
point in f(8, 3).