找到满足一定约束的矩阵
对问题的另一种描述：计算满足一定约束条件的矩阵
给定一个函数，其唯一参数是一个4x4矩阵（ int[4][4] matrix ），确定该函数的最大可能输出（返回值）。
4×4矩阵必须满足以下约束条件：
该函数只能总结矩阵的值，没有什么奇特的。
我的问题：
给定这样的函数来总结矩阵的某些值（矩阵满足上述约束条件），我如何找到该函数的最大可能输出/返回值？
例如：
/* 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
我不知道从哪里开始。 目前，我试图估计满足约束的4×4矩阵的数量，如果数量足够小，问题可以通过强力解决。
有更通用的方法吗？ 这个问题的解决方案是否可以推广到可以很容易地适应给定矩阵上的任意函数和矩阵的任意约束？
你可以尝试使用线性编程技术来解决这个问题。
其思想是将问题表达为一些不等式，一些等式和一个线性目标函数，然后调用一个库来优化结果。
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，用给定的矩阵。
严格地说，你需要整数解决方案。 当输入可以是任何实数值时，线性规划解决了这种类型的问题，而当输入必须是整数时，整数规划解决了这种类型的问题。
在你的情况下，你可能会发现线性规划方法已经提供了整数解（它为两个给定的例子）。 发生这种情况时，肯定这是最佳答案。
但是，如果变量不是整数，则可能需要找到整数编程库。
按降序对矩阵中的元素进行排序并存储在数组中。逐个遍历数组中的元素并将其添加到变量。在将元素添加到变量时减少其值的点迭代。存储的值在变量中给出最大值。
maxfunction(matrix[][])
{
array(n)=sortDescending(matrix[][]);
max=n[0];
i=1;
for i to n do
temp=max;
max=max+n[i];
if(max<temp)
break;
return max;
}
您需要首先考虑哪些矩阵可以满足规则。 对角线上的4个数字必须为正值，对角线的最小和为4（四个1值），最大值为40（四个10值）。
所有16个项目的总和为0 - 或者换句话说，sum（diagnoal）+ sum（矩阵的剩余部分）= 0。
既然你知道sum（对角线）是正的，那意味着sum（矩阵的剩余部分）必须是负的并且相等 - 基本上是和（对角线）*（ - 1）。
我们也知道矩阵的其余部分是对称的 - 所以你可以保证总和（矩阵的余数）是偶数。 这意味着对角线也必须是偶数，并且矩阵的上半部分的总和恰好是对角线*（ - 1）的一半。
对于任何给定的功能，你需要一些细胞并对它们进行求和。 现在，您可以将这些功能视为适合类别。 对于仅从对角线取得所有4个单元的函数，最大值将是40.如果函数取所有12个不是对角线的单元，则最大值为-4（负最小对角线）。
其他类别的功能有一个简单的答案：
1）对角线上的一个和对角线上/下的矩阵的整个一半 - 最大值为3.对角线单元格将为10，其余为1,1，2（最小值为偶数）和半矩阵将总和为-7。
2）对角线和半个矩阵的两个单元格 - 最大值是9.两个对角线单元格被最大化为二十，其余的单元格是1,1 - ，因此半矩阵在-11上相加。
3）从对角线和半个矩阵中的三个单元 - 最大值是14。
4）整个对角线和矩阵的一半 - 最大值为20。
您可以继续使用选择函数的类别（使用对角线中的一些和其余部分），并轻松计算每个类别选择函数的最大值。 我相信他们都可以被映射。
然后，唯一的步骤就是将您的新选择功能置于正确的类别，并且知道最大值。
链接地址: http://www.djcxy.com/p/63243.html上一篇: Find a matrix which satisfies certain constraints
下一篇: algorithm for finding least area occupied with n rectangulars