最大化数组间的最小距离

Question

假设你有n个已排序的数字数组，需要从每个数组中选择一个数字，使得所选元素之间的最小距离最大。

例子：

arrays:
[0, 500]
[100, 350]
[200]

2<=n<=10，每个数组可能有 ~10^3-10^4 个元素。

在这个例子中，最大化最小距离的最优解是选择数字：500、350、200或0、200、350，其中最小距离是150，并且是每种组合的最大可能值。

我正在寻找一种算法来解决这个问题。我知道可以使用二分查找来查找最大的最小距离，但我不知道如何确定是否存在至少为d的最大最小距离的解决方案，以便于二分查找工作。我认为动态规划可能有所帮助，但尚未通过DP找到解决方案。

当然，生成所有具有n个元素的组合并不高效。我已经尝试过回溯算法，但由于它会尝试每种组合，因此速度很慢。

- frank

Answer 1

n ≤ 10表明我们可以对n进行指数依赖。以下是一个O(2ⁿ m n)时间复杂度的算法，其中m为数组的总大小。

我考虑的动态规划方法是，对于每个子集的数组，计算出在有效边界上的所有对（最大数量，最小距离），其中我们必须从子集中的每个数组中选择一个数字。有效边界是指如果有两个对(a，b) ≠ (c，d)，其中a≤c且b≥d，则(c，d)不在有效边界上。我们将希望保持这些边界排序以进行快速合并。

空子集的基本情况很容易：有一对(最小距离=∞，最大数字=−∞)。

对于任何按包含顺序扩展非空数组子集，我们都会为子集中的每个数组计算一个边界，表示该数组贡献最大数字的解集。然后我们合并这些边界。(天真地做这件事会让我们再花费log n的因素，但也许不值得费力避免，因为n ≤ 10，但我们可以在开始时合并数组，以便未来的合并使用桶来避免这种情况。)

从一组数组和另一个数组构建新的边界还涉及合并。我们在边界的开头(即最小的最大数字)和数组的开头(即最小的数字)初始化一个迭代器。当两个迭代器都没有超过末尾时，

1. 发出一个候选对(min(minimum distance, array number − maximum number), array number)。
2. 如果min小于或等于最小距离，则增加边界迭代器。如果min小于或等于数组数字−最大数字，则增加数组迭代器。

剔除候选对，只留下有效边界。有一种优雅的方法可以在代码中实现这一点，但解释起来更麻烦。

- David Eisenstat

---

谢谢您的回复！！！ 我想我大致明白了，但您可否提供一个例子？ - frank

所以你保留所有候选者，只保留高效的？如何高效地执行此操作？ 假设您有2个数组A=[2,4]，B=[6,10]，一开始您有空子集E={}和前沿：(10^10,-10^10)（假设10^10是最高值）。然后，您创建E并集A的前沿=[(10^10,2)]，E并集B的前沿=[(10^10,6)]，那么A并集B是什么？ - frank

@frank 我们在执行 B 之后得到了 [(4,6),(8,10)] 的 {A}，而在执行 A 之后没有得到 {B}，因此结果为 [(4,6),(8,10)]。 - David Eisenstat

既然你最初提到空子集，那么这个怎么样：（最小距离=∞，最大数字=−∞），因此对于A = A union empty，我们遵循规则得到[(10^10,2)]（如果在我们的例子中无穷大=10^10）？？你能提供一个完整的最小示例来理解你的算法吗？ - frank

@DavidEisenstat 这怎么是O(1)的？ - Abhinav Mathur

Answer 2

我将提供一个算法，对于给定的距离d，将输出是否可以进行选择，其中任何一对选择数字之间的距离至少为d。然后，您可以进行二分搜索，以找到算法输出“是”的最大d，以便找到问题的答案。

假设最小距离d已知。以下是算法：

for every permutation p of size n do:
    last := -infinity
    ok := true
    
    for p_i in p do:
        x := take the smallest element greater than or equal to last+d in the p_i^th array (can be done efficiently with binary search).
        if no such x was found; then
            ok = false
            break
        end

        last = x
    done

    if ok; then
        return "YES"
    end
done

return "NO"

因此，我们通过暴力破解数组的顺序。然后，对于每个可能的顺序，我们使用贪心方法从每个数组中选择元素，按顺序进行选择。例如，以您提供的示例为例：

arrays:
[0, 500]
[100, 350]
[200]

假设d = 150。对于排列1 3 2，我们首先从第一个数组中取0，然后找到第三个数组中大于或等于0 + 150（为200）的最小元素，然后找到第二个数组中大于或等于200 + 150（为350）的最小元素。由于我们可以从每个数组中找到一个元素，因此算法输出“YES”。但是，例如对于d = 200，算法将输出“NO”，因为没有任何可能的顺序会导致成功的选择。

上述算法的复杂度为O(n! * n * log(m))，其中m是数组中元素的最大数量。我认为这足够了，因为n非常小。（对于m = 10^4，10！* 10 * 13〜5 * 10^8。它可以在现代CPU上的一秒钟内计算出来。）

- yemre

---

谢谢你的回答！ 这正是我正在寻找的，一个简单明了的算法，带有简单的示例和解释！！ 我思考了几天关于你的算法的正确性。我不确定为什么它保证找到最佳答案？？ （我没有找到任何反例，并且在很大程度上您的方法是有道理的，我只是在思考如何证明正确性 - 用简单的术语/想法，而不是数学证明） - frank

在第一个for循环中，我们有一个固定的d和一个固定的数组顺序。首先，我们考虑perm中的第一个数组。我们从这个数组中选择的数字将是最小的数字，因此选择不是该数组中最小值的数字是没有意义的。所以，我们取最小元素。现在转到第二个数组...同样的事情适用。如果存在比上一个+d更大的较小元素，则选择元素是没有意义的。继续进行第三个...等等。 我希望现在更清楚了。 - yemre

Answer 3

让我们看一个最佳选择的例子，x（水平数组 A、B、C、D）：

A            x
B    b    x        b
C   x             c
D     d             x

我们基于范围的递归可能是：让f（low，excluded）表示子集中没有excluded元素的两个选择元素（从数组1到n）之间的最大最近距离，其中low是最低的选择元素。然后：

(1)

f(low, excluded) when |excluded| = n-1:
  max(low)
    for low in the only permitted array

(2)

f(low, excluded):
  max(
    min(
      a - low,
      f(a, excluded')
    )
  )
  for a ≥ low, a not in excluded'
    where excluded' = excluded ∪ {low's array}

我们可以限制a。一方面，我们能够达到的最大值是

(3)

m = (highest - low) / (n - |excluded| - 1)

这意味着 a 不需要比 low + m 更高。

其次，我们可以为所有的 f(a, excluded') 存储结果，以 excluded' 为键（我们有2^10个可能的键），每个键对应一个按 a 排序的装饰二叉树。装饰将是右子树中可实现的最高结果，这意味着我们可以在对数时间内找到所有 f(v, excluded'), v ≥ a 的最大值。

后者建立了一种支配关系，显然我们对于更大的 a 和更大的 f(a, excluded') 都感兴趣，以便在（2）中最大化 min 函数。选择一个中间的 a，我们可以使用二分查找。如果我们有：

a - low < max(v, excluded'), v ≥ a

  where max(v, excluded') is the lookup
  for a in the decorated tree

然后我们向右看，因为max(v, excluded)表示右侧有更好的答案，其中a - low也更大。

如果我们有：

a - low ≥ max(v, excluded), v ≥ a

然后我们记录这个候选项并向左查看，因为向右，答案固定为max(v, excluded)，鉴于a-low不能减少。

为了在范围[low, low + m]（见（3））上进行二进制搜索，而不是在一开始合并和标记所有数组，我们可以将它们保持分开，并比较当前允许从中选择a的每个数组中最接近mid的候选项。（树具有混合结果，由子集键入。）（这部分的流程对我来说不是完全清楚的。）

使用此方法的最坏情况，鉴于n = C是常数似乎是

O(C * array_length * 2^C * C * log(array_length) * log(C * array_length))

C * array_length is the iteration on low
Each low can be paired with 2^C inclusions
C * log(array_length) is the separated binary-search
And log(C * array_length) is the tree lookup

简化：

= O(array_length * log^2(array_length))

实际上，可能会有许多提前退出的死胡同分支，无法进行完整选择。

如果不清楚，迭代是在选择中固定的最低元素上进行的。换句话说，我们希望对于所有不同的low和excluded，得到最佳的f(low, excluded)。对于自下而上，我们将从最高值向下迭代，因此我们迭代时存储a的结果。

- גלעד ברקן