Find a matrix which satisfies certain constraints
Another description of the problem: Compute a matrix which satisfies certain constraints
Given a function whose only argument is a 4x4 matrix ( int[4][4] matrix ), determine the maximal possible output (return value) of that function.
The 4x4 matrix must satisfy the following constraints:
The function must only sum up values of the matrix, nothing fancy.
My question:
Given such a function which sums up certain values of a matrix (matrix satisfies above constraints), how do I find the maximal possible output/return value of that function?
For example:
/* 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
I don't know where to start. Currently I'm trying to estimate the number of 4x4 matrices which satisfy the constraints, if the number is small enough the problem could be solved by brute force.
Is there a more general approach? Can the solution to this problem be generalized such that it can be easily adapted to arbitrary functions on the given matrix and arbitrary constraints for the matrix?
You can try to solve this using linear programming techniques.
The idea is to express the problem as some inequalities, some equalities, and a linear objective function and then call a library to optimize the result.
Python code:
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
This prints:
[ 1. 10. -10. 10.]
[ 10. 1. 8. -10.]
[-10. 8. 1. -10.]
[ 10. -10. -10. 1.]
16.0
saying that the best value for your second case is 16, with the given matrix.
Strictly speaking you are wanting integer solutions. Linear programming solves this type of problem when the inputs can be any real values, while integer programming solves this type when the inputs must be integers.
In your case you may well find that the linear programming method already provides integer solutions (it does for the two given examples). When this happens, it is certain that this is the optimal answer.
However, if the variables are not integral you may need to find an integer programming library instead.
按降序对矩阵中的元素进行排序并存储在数组中。逐个遍历数组中的元素并将其添加到变量。在将元素添加到变量时减少其值的点迭代。存储的值在变量中给出最大值。
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;
}
You need to first consider what matrices will satisfy the rules. The 4 numbers on the diagonal must be positive, with the minimal sum of the diagonal being 4 (four 1 values), and the maximum being 40 (four 10 values).
The total sum of all 16 items is 0 - or to put it another way, sum(diagnoal)+sum(rest-of-matrix)=0.
Since you know that sum(diagonal) is positive, that means that sum(rest-of-matrix) must be negative and equal - basically sum(diagonal)*(-1).
We also know that the rest of the matrix is symmetrical - so you're guaranteed the sum(rest-of-matrix) is an even number. That means that the diagonal must also be an even number, and the sum of the top half of the matrix is exactly half the diagonal*(-1).
For any given function, you take a handful of cells and sum them. Now you can consider the functions as fitting into categories. For functions that take all 4 cells from the diagonal only, the maximum will be 40. If the function takes all 12 cells which are not the diagonal, the maximum is -4 (negative minimal diagonal).
Other categories of functions that have an easy answer:
1) one from the diagonal and an entire half of the matrix above/below the diagonal - the max is 3. The diagonal cell will be 10, the rest will be 1, 1, 2 (minimal to get to an even number) and the half-matrix will sum at -7.
2) two cells of the diagonal and half a matrix - the max is 9. the two diagonal cells are maximised to two tens, the remaining cells are 1,1 - and so the half matrix sums at -11.
3) three cells from the diagonal and half a matrix - the max is 14.
4) the entire diagonal and half the matrix - the max is 20.
You can continue with the categories of selecting functions (using some from the diagonal and some from the rest), and easily calculating the maximum for each category of selecting function. I believe they can all be mapped.
Then the only step is to put your new selecting function in the correct category and you know the maximum.
链接地址: http://www.djcxy.com/p/63244.html下一篇: 找到满足一定约束的矩阵