阵列间最小距离最大化

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

我将给出一种算法，对于给定的距离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)的最小元素。因为我们可以从每个数组中找到一个元素，所以算法输出“是”。例如，对于d = 200，该算法将输出"NO“，因为所有可能的订单都不会导致成功的选择。

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

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')中都是整数的，从而使(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的最接近的候选对象与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))

尽管在实践中，可能会有许多死胡同分支在不可能完全选择的情况下提前退出。

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