最大化阵列之间的最小距离

Question

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

示例：

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

2<=n<=10 并且每个数组可以有 ~10^3-10^4 个元素。

在此示例中，最大化最小距离的最佳解决方案是选择数字：500、350、200 或 0、200、350，其中最小距离为 150，是每个组合的最大可能值。

我正在寻找一种算法来解决这个问题。我知道我可以对最大最小距离进行二分搜索，但我看不出如何确定是否存在最大最小距离至少为 d 的解决方案，以便二分搜索起作用。我在想也许动态编程会有所帮助，但还没有找到 dp 的解决方案。

当然，生成所有包含 n 个元素的组合效率不高。我已经尝试过回溯，但它很慢，因为它尝试了所有组合。

Answer 1

n ≤ 10 表明我们可以对 n 取指数依赖。这是 O(2ⁿ m n) 时间算法，其中 m 是数组。

我想到的动态规划方法是，对于数组，计算所有对（最大数量，最小距离）有效边界，我们必须从每个边界中选择一个数字子集中的数组。通过有效边界我的意思是如果我们有两对 (a, b) ≠ (c, d) 且 a ≤ c 且 b ≥ d，则 (c, d) 不在有效边界。我们希望对这些边界进行分类快速合并。

具有空子集的基本情况很简单：有一对，（最小距离 = ∞, 最大数 = −∞).

对于数组的每个非空子集，以某种顺序扩展包含顺序，我们计算子集中每个数组的边界，表示该数组贡献的解决方案的子集最大数量。然后我们合并这些边界。（天真地这让我们付出了代价 log n 的另一个因素，可能不值得避免麻烦鉴于 n ≤ 10，但我们可以通过在开始启用未来的合并以使用分桶。）

从数组的一个子集和另一个数组构造一个新的边界还涉及合并。我们在开始时初始化一个迭代器边界（即最小最大数）和开始处的迭代器数组（即最少的数字）。虽然两个迭代器都没有结束，

发出一个候选对(min(最小距离,数组数-最大数), 数组数).
如果最小值小于或等于最小距离，增加边界迭代器。如果最小值小于或等于数组编号 − 最大数，递增数组迭代器。

剔除候选对以仅留下有效边界。有一种在代码中执行此操作的优雅方法，但更难以解释。

Answer 2

让我们看一个具有最佳选择的示例，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')以最大化min函数在(2)中。在中间挑一个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）），而不是一开始就合并和标记所有数组，我们可以将它们分开并比较最接近的候选者到 mid 我们目前可以从每个数组中选择 a 。（树有混合结果，以子集为键。）（这部分的流程对我来说并不完全清楚。）

使用此方法的最坏情况，因为 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 的结果。

Answer 3

我将给出一个算法，对于给定的距离 d，将输出是否有可能做出选择，其中任何一对所选数字之间的距离至少为 d .然后，您可以对算法输出“YES”的最大值 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，我们首先从第1个数组中取0，然后我们在第3个数组中找到大于等于0+150（它是200）的最小元素（它是200），然后我们找到最小的元素在大于或等于 200+150（它是 350）的第二个数组中。因为我们可以从每个数组中找到一个元素，所以算法输出“YES”。但是对于 d = 200 例如，算法将输出“否”，因为 none 可能的排序将导致成功选择。

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

最大化阵列之间的最小距离

Maximize minimum distance between arrays

algorithm

optimization

dynamic-programming

combinatorics

backtracking