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

Question

我有一个数组a1到每个包含m个元素。我有另一个对称的n X n矩阵b，它包含阵列之间的距离。我想从每个数组x1到xn中选择一个元素，限制为以下约束。 （a1是一个数组，x1是从a1取的单个值）

1. 对于每个xi（最初是aiu）和xj（最初是ajv），其中i与j不同，u和v是原始数组索引，我们有| u - v | <= bij。
2. x1到xn的总和是所有可能的这样的集合的最大值。

一个例子

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

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

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

现在，当我只有两个数组时，我可以在O（n2）时间内在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中选择了一个值，但尚未从其他步骤中进行选择。 （选择的数组不必是列表的前缀，甚至是连续的。）
2. 如果已对每个数组进行了选择，则返回（从此递归调用中）获得的分数。
3. 考虑到对于每对所选阵列和剩余阵列，可以在后者中选择的索引的间隔给定对前者中所做选择的距离的限制。
4. 每个剩余的数组相交这些间隔。如果任何交叉点为空，则拒绝此建议的选择集并回溯。
5. 否则，选择具有最小可用选项的剩余阵列。将每个选项添加到建议的选择集并递归。返回找到的最佳分数以及获取它的选择（如果有），或拒绝和回溯。

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

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