A question was posted on Stack Overflow asking for an algorithm to solve this problem:
I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The subset will consist of n elements, where one and only one element is taken from each row and from each column of A. The output should provide a solution (B) such that the sum of the elements that make up B is the maximum possible value, given these constraints (eg. 25 in the example below). If multiple instances of B are found (ie. different solutions which give the same maximum sum) the solution for B which has the largest minimum element should be selected.
B could also be a selection matrix which is nxn, but where only the n desired elements are non-zero.
For example: if A =
|5 4 3 2 1| |4 3 2 1 5| |3 2 1 5 4| |2 1 5 4 3| |1 5 4 3 2|
=> B would be
|5 5 5 5 5|
I proposed a dynamic programming solution which I suspect is as efficient as any solution is going to get. I've copy-pasted my proposed algorithm below.
- Let $A$ be a square array of $n$ by $n$ numbers.
- Let $A_{i,j}$ denote the element of $A$ in the
i
th row andj
th column. - Let $S( i_1:i_2, j_1:j_2 )$ denote the optimal sum of non-overlapping numbers for a square subarray of $A$ containing the intersection of rows $i_1$ to $i_2$ and columns $j_1$ to $j_2$.
Then the optimal sum of non-overlapping numbers is denoted S( 1:n , 1:n )
and is given as follows:
$$S( 1:n , 1:n ) = \max \left \{ \begin{array}{l} S( 2:n , 2:n ) + A_{1,1} \\ S( 2:n , 1:n-1 ) + A_{1,n} \\ S( 1:n-1 , 2:n ) + A_{n,1} \\ S( 1:n-1 , 1:n-1 ) + A_{n,n} \\ \end{array} \right.$$
Note that S( i:i, j:j ) is simply Aij.
That is, the optimal sum for a square array of size n
can be determined by separately computing the optimal sum for each of the four sub-arrays of size n-1
, and then maximising the sum of the sub-array and the element that was "left out".
S for |# # # #|
|# # # #|
|# # # #|
|# # # #|
Is the best of the sums S for:
|# | | #| |# # # | | # # #|
| # # #| |# # # | |# # # | | # # #|
| # # #| |# # # | |# # # | | # # #|
| # # #| |# # # | | #| |# |
This is a very elegant algorithm and I strongly suspect that it is correct, but I can't come up with a way to prove it is correct.
The main difficulty I am having it proving that the problem displays optimal substructure. I believe that if the four potential choices in each calculation are the only four choices, then this is enough to show optimal substructure. That is, I need to prove that this:
| # |
| # # #|
| # # #|
| # # #|
Is not a valid solution, either because it's impossible (i.e. proof by contradiction) or because this possibility is already accounted for by one of the four "n-1
square" variations.
Can anyone point out any flaws in my algorithm, or provide a proof that it really does work?
O(N^3)
if it worked, except it doesn't work. So pooh. $\endgroup$