java - 从比预定义距离更近的数组中查找更高的值

Question

我有数组 a₁ 到 a_n，每个数组包含 m 个元素。我有另一个对称 n X n 矩阵 b 包含数组之间的距离。我想从每个数组 x₁ 到 x_n 中选择一个元素，限制为以下约束。 (a₁ 是一个数组，x₁ 是取自 a₁ 的单个值)

1. 对于每个 x_i(原来是 a_iu)和 x_j(原来是 a_jv>)，其中 i 与 j 不同，u 和 v 是原始数组索引，我们有 |u - v| <= b_ij.
2. x₁ 到 x_n 的总和是所有可能的集合中的最大值。

一个例子

a1 = [1, 2, 3, 8, -1, -1, 0, -1]
a2 = [1, 2, 4, 0, -1, 1, 10, 11]

b  = |0, 2|
     |2, 0|

选择的值是 x₁ = 8 和 x₂ = 4。可以注意到我们没有从第二个中选择 10 或 11，因为最接近的可能它们中任何一个的值都仅为 0。

现在，当我只有两个数组时，我可以在 O(n²) 时间内在 java 中执行以下操作，我猜，并找到最大总和，即 12 在这种情况下。如何为 2 个以上的阵列实现更好的解决方案？

int[][] a = new int[][]{{1, 2, 3, 8, -1, -1, 1, -1}, {1, 2, 4, 0, -1, 1, 10, 11}};
int[][] b = new int[][]{{0, 2}, {2, 0}};
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < a[0].length; i++) {
    for (int j = Math.max(i - b[0][1], 0); j < Math.min(a[1].length, i + b[0][1]); j++) {
        maxVal = Math.max(maxVal, a[0][i] + a[1][j]);
    }
}
System.out.println("The max val: "+maxVal);

Answer 1

您不能在这里使用动态规划，因为没有最佳子结构:b_1n 条目可能会破坏从 x_1 到 x_{n-1} 的非常有值(value)的路径。所以通常很难避免指数时间。然而，对于一组合理限制选择的 b_ij，有一个简单的回溯方法应该具有合理的性能:

1. 在每一步中，都会从一些 a_i 中选择一个值，但尚未从其他 a_i 中选择一个值。 (选择的数组不需要是列表的前缀，甚至不需要是连续的。)
2. 如果对每个数组都做出了选择，则返回(从这个递归调用中)获得的分数。
3. 考虑，对于每对所选数组和剩余数组，考虑到前者选择的距离限制，后者可供选择的索引区间。
4. 将每个剩余数组的这些区间相交。如果任何路口为空，则拒绝这组建议的选择并回溯。
5. 否则，选择具有最小 可用选项集的剩余数组。将每个选择添加到建议选择集中并递归。返回找到的最佳分数和为获得它所做的选择(如果有)，或者拒绝并回溯。

识别最受约束的数组对性能至关重要:它构成了一种模糊信念传播的形式，有效地修剪了与先前选择所必需的当前选择不兼容的 future 选择。根据您期望的输入类型，根据可实现的分数进行进一步的优先级排序/修剪可能有值(value)。

我的 35 行 Python 实现，给定一个 10x10 的小整数随机矩阵和一个常量 2 的 b_ij，在几秒钟内运行。 b_ij=3(每对数组最多允许 10 个值中的 7 个值!)花了大约一分钟。