java - 找到满足某些约束的矩阵

Question

问题的另一种描述:Compute a matrix which satisfies certain constraints

给定一个函数，其唯一参数是一个 4x4 矩阵(int[4][4] 矩阵)，确定该函数的最大可能输出(返回值)。

4x4 矩阵必须满足以下约束:

1. 所有条目都是介于 -10 和 10(含)之间的整数。
2. 它必须是对称的，entry(x,y) = entry(y,x)。
3. 对角线项必须为正，entry(x,x) > 0。
4. 所有 16 个条目的总和必须为 0。

该函数必须只对矩阵的值求和，没有什么特别的。

我的问题:

给定这样一个对矩阵的某些值求和的函数(矩阵满足上述约束)，我如何找到该函数的最大可能输出/返回值？

例如:

/* The function sums up certain values of the matrix, 
   a value can be summed up multiple or 0 times. */

// for this example I arbitrarily chose values at (0,0), (1,2), (0,3), (1,1).
int exampleFunction(int[][] matrix) {
    int a = matrix[0][0];
    int b = matrix[1][2];
    int c = matrix[0][3];
    int d = matrix[1][1];

    return a+b+c+d;
}

/* The result (max output of the above function) is 40, 
   it can be achieved by the following matrix: */
    0.   1.   2.   3.
0.  10  -10  -10   10
1. -10   10   10  -10
2. -10   10    1   -1
3.  10  -10   -1    1


// Another example:

// for this example I arbitrarily chose values at (0,3), (0,1), (0,1), (0,4), ...
int exampleFunction2(int[][] matrix) {
    int a = matrix[0][3] + matrix[0][1] + matrix[0][1];
    int b = matrix[0][3] + matrix[0][3] + matrix[0][2];
    int c = matrix[1][2] + matrix[2][1] + matrix[3][1];
    int d = matrix[1][3] + matrix[2][3] + matrix[3][2];

    return a+b+c+d;
}

/* The result (max output of the above function) is -4, it can be achieved by 
   the following matrix:  */
    0.   1.   2.   3.
0.   1   10   10  -10
1.  10    1   -1  -10
2.  10   -1    1   -1
3. -10  -10   -1    1

我不知道从哪里开始。目前我正在尝试估计满足约束条件的 4x4 矩阵的数量，如果数量足够小，则可以通过蛮力解决问题。

是否有更通用的方法？这个问题的解决方案是否可以推广，以便它可以很容易地适应给定矩阵上的任意函数和矩阵的任意约束？

Answer 1

您可以尝试使用 linear programming techniques 来解决这个问题.

想法是将问题表达为一些不等式、一些等式和一个线性目标函数，然后调用一个库来优化结果。

Python代码:

import scipy.optimize as opt
c = [0]*16
def use(y,x):
    c[y*4+x] -= 1

if 0:
    use(0,0)
    use(1,2)
    use(0,3)
    use(1,1)
else:
    use(0,3)
    use(0,1)
    use(0,1)
    use(0,3)
    use(0,3)
    use(0,2)
    use(1,2)
    use(2,1)
    use(3,1)
    use(1,3)
    use(2,3)
    use(3,2)
bounds=[ [-10,10] for i in range(4*4) ]
for i in range(4):
    bounds[i*4+i] = [1,10]
A_eq = [[1] * 16]
b_eq = [0]
for x in range(4):
    for y in range(x+1,4):
        D = [0]*16
        D[x*4+y] = 1
        D[y*4+x] = -1
        A_eq.append(D)
        b_eq.append(0)

r = opt.linprog(c,A_eq=A_eq,b_eq=b_eq,bounds=bounds)
for y in range(4):
    print r.x[4*y:4*y+4]
print -r.fun

这打印:

[  1.  10. -10.  10.]
[ 10.   1.   8. -10.]
[-10.   8.   1. -10.]
[ 10. -10. -10.   1.]
16.0

说你的第二种情况的最佳值是 16，给定的矩阵。

严格来说，您需要的是整数解。当输入可以是任何实数值时，线性规划解决此类问题，而当输入必须是整数时，整数规划解决此类问题。

在您的情况下，您很可能会发现线性规划方法已经提供了整数解决方案(它适用于给定的两个示例)。当出现这种情况时，可以肯定这是最优答案。

但是，如果变量不是整数，您可能需要找到一个整数编程库。