matrices with lowest difference between their sum
I have to find the difference between the sum of 4 sub-matrices, which I get after splitting the matrix A in any way, in order to get the lowest difference between the sum of sub-matrix.
For example, for a matrix A,
3 0 2 -8 -8
5 3 2 2 3
2 5 2 1 4
3 4 -1 4 2
-3 6 2 4 3
I could split it like this:
3 | 0 2 -8 -8
5 | 3 2 2 3
2 | 5 2 1 4
-------------------
3 4 -1 | 4 2
-3 6 2 | 4 3
The sum of all elements within each sub-matrix gives the following result:
10 | 8
-------
11 | 13
Afterwards, I compute all the possible absolute differences between the sums, ie
abs(10 - 8) = 2
abs(10 - 11) = 1
abs(10 - 13) = 3
abs(8 - 11) = 3
abs(8 - 13) = 5
abs(11 -13) = 2
Finally, I chose the maximum distance, which is 5 .
However, if I split the matrix A in any other way, it will give a different maximum distance, which I don't want. I have to find just 5 , but if I'll do this brute force, I just spend too much time on finding all possibilities. Does this problem has a name, or may be you can give me a hint?
ADDED
The allowable splits are a horizontal split followed by a vertical split above and a possibly different vertical split below the horizontal split. In the example, there are 4 x 4 x 4 = 64 allowable partitions of the matrix.
The max difference between the submatrices of a particular partition is formed by considering all pairs of the 4 submatrices of that partition (there will be 6 such pairs) and taking the largest difference between the sums of the elements of one of the submatrices of the pair and the sum of the elements of the other submatrix of the pair. We wish to find the minimum over all max differences.
The actual matrix may be up to 4000 x 4000.
There are some speed-ups over brute force. First of all, by accumulating sums along rows and then down columns you can build a table giving, for each point, the total sum of all points, including that one, no further up than it and no further right than it. Then you can compute the sum in any rectangle by subtracting at most four of these sub-totals: roughly speaking the sum from the top right corner plus the sum from the bottom left corner minus the sums from the other two corners.
For the split pattern the OP has diagrammed, with a horizontal line splitting the entire matrix followed by different vertical lines splitting in each half, the vertical splits must be the most even vertical split of their half. If the most extreme difference between sums is within a vertical split, evening the vertical splits can only improve it. If the most extreme difference between sums is between (for example) a high sum from the top left and a low sum on the bottom right, then evening out either vertical split will either bring the high sum down or the low sum up, evening out the most extreme difference. This means you need only consider the best split in the top half and the best split in the bottom half - you don't need to consider all pairs of splits.
For the case where you have two vertical splits on the same side of a horizontal split, you do not have to try all pairs of positions for the vertical splits: you can start with the leftmost split at the far left, and adjust the rightmost split to cut the remainder as evenly as possible in two. Then move the leftmost split slowly to the right and, as you do so, the rightmost split can be repeatedly adjust to move to the right so as to keep splitting the remainder as evenly as possible.
Using these ideas, it seems to me that, for each possible split pattern, you can find the minimum cost split of that pattern in time, given the position of the longest line in that pattern, which is O(N) for a square matrix of side N, so with N positions for a longest line that is O(N^2), which is about the same time as it takes to build up a table of sums of points below and to the left of each point, which takes time linear in the total number of cells in the matrix, or O(N^2) for a square matrix of side N. - but it is annoying that there seem to six different split patterns.
链接地址: http://www.djcxy.com/p/19152.html下一篇: 矩阵的总和之间的差异最小