从比预定义距离更近的阵列中查找更高的值

Question

我有一个₁到_n的数组,每个包含m个元素.我有另一个对称的n X n矩阵b,它包含阵列之间的距离.我想从每个数组x ₁到x _n中选择一个元素,限制为以下约束.(一个₁是一个数组,并且x ₁从拍摄的单个值₁)

1. 对于每个x _i(最初是_iu)和x _j(最初是_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} 的非常有价值的路径。因此，一般来说，可能很难避免指数时间。然而，对于一组确实合理限制选择的 b_ij ，有一个简单的回溯方法应该具有合理的性能：

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

识别最受约束的数组对于性能至关重要：它构成了一种模糊置信传播的形式，可以有效地修剪与先前选择所需的当前选择不兼容的未来选择。根据您期望的输入类型，根据可实现的分数进行进一步的优先级划分/修剪可能是有价值的。

我的 35 行 Python 实现在给定一个由小整数组成的 10x10 随机矩阵和 b_ij 为常数 2 的情况下运行了几秒钟。b_ij=3（每对数组最多允许 10 个值中的 7 个！）大约需要一分钟。