A problem described in my algo book:

Given an N by N matrix, for example,
3 5 5 4 1
2 2 0 2 2
2 4 4 1 0
0 1 1 0 0
1 2 1 3 3

Task: take N numbers, one from each row. These N numbers should be in different columns. Give the maximum of the sum of the N numbers.

in this case, it's 16 (4+2+3+4+3):
3 5 5 [4] 1
[2] 2 0 2 2
2 4 [3] 1 0
0 [4] 1 0 0
1 2 1 3 [3]

How would you work this out? N can be up to 20 something, so brute force search is out of the question.

( the algorithm introduced in that book is poorly explained, so I'm looking for help here. Kuhn Munkras is the algo's name. )

Thanks in advance.
Posted on 2002-11-25 07:54:20 by C.Z.
Posted on 2002-11-25 09:40:31 by bitRAKE
thank you bitRAKE. Seems that I have to dig into the terminology in order to be able to undertand. (seems pretty hard! :)).
Sigh, a printing error led me to disorientation searching for munkras.
Posted on 2002-11-25 11:08:03 by C.Z.
hmm, this sounds interesting, I think I have an idea... :) but I'm thinking of brute force. It's kinda hard to see the patterns on the matrix, if we are not using brute force style. I'll see what I can do... :)
Posted on 2002-11-25 11:28:20 by stryker
It's a bad idea to search all possibilities because the number of solutions to test for an NxN matrix is N! (n factorial) which is ~ 2.4x10^18 for a 20x20 matrix.

It is an interesting problem though. I need to think about it more.
Posted on 2002-11-25 16:42:31 by iblis
I have come up with a solution - it's brute force but aside from that, it's hard since the numbers are random. I haven't read some docs yet. :)
3 5 5 4 1

2 2 0 2 2
2 4 3 1 0
0 4 1 0 0
1 2 1 3 3
12341
3 5 5 4 [color=blue]1[/color]

2 2 0 [color=blue]2[/color] 2
2 4 [color=blue]3[/color] 1 0
0 [color=blue][b]4[/b][/color] 1 0 0
[color=blue][b]1[/b][/color] 2 1 3 3
12302
3 5 5 4 [color=blue]1[/color]

2 2 0 [color=blue]2[/color] 2
2 4 [color=blue]3[/color] 1 0
[color=blue][b]0[/b][/color] 4 1 0 0
1 [color=blue][b]2[/b][/color] 1 3 3
12241
3 5 5 4 [color=blue]1[/color]

2 2 0 [color=blue]2[/color] 2
[color=blue][b]2[/b][/color] 4 3 1 0
0 [color=blue][b]4[/b][/color] 1 0 0
1 2 [color=blue][b]1[/b][/color] 3 3
12401
3 5 5 4 [color=blue]1[/color]

2 2 0 [color=blue]2[/color] 2
2 [color=blue][b]4[/b][/color] 3 1 0
[color=blue][b]0[/b][/color] 4 1 0 0
1 2 [color=blue][b]1[/b][/color] 3 3
12411
3 5 5 4 [color=blue]1[/color]

2 2 0 [color=blue]2[/color] 2
2 [color=blue][b]4[/b][/color] 3 1 0
0 4 [color=blue][b]1[/b][/color] 0 0
[color=blue][b]1[/b][/color] 2 1 3 3
... This can be placed in an inner loop and the variable that determines how many times to loop depends on the "deepness"/level of the array
Level 5 = 3 5 5 4 1

Level 4 = 2 2 0 2 2
Level 3 = 2 4 3 1 0
Level 2 = 0 4 1 0 0
Level 1 = 1 2 1 3 3
The main loop only loops on the topmost values: 3, 5, 5, 4 and 1 - going from left to right (1, 4 ... 3) after that, we're done and we should be able to find out the solution.

It's kinda hard to explain what I really meant here but I'm sure everybody can see a pattern on the looping. :)
Posted on 2002-11-25 17:29:41 by stryker
Quite an interesting little problem, the O(n^3) Kuhn-Munkres algorithm looks interesting.

Just to get everybody going, here is a simple way to get a halfway decent solution :-)

S = arbitrary possible solution (the diagonal is an obvious choice)


do {
for all pairs (x,y) in S
{
if (swapping (x,y) improves the solution) swap (x,y);
}
} while (any swapping occurred);


Since checking for a swap is constant time, this is O(n^3) worst case. The solution found should be at least half of the maximum solution.

On random squares it's quite fast and close to the maximum.

---

I ran it on 10,000 random 20x20 squares (~1.5 seconds), and on average it was O(n^2) and about 6% below the theoretical limit (sum of the maximum in each column).

The Kuhn-Munkres algorithm should have absolutely no problems on N=20 ;-)
Posted on 2002-11-25 18:09:27 by Jibz
Don't forget, the matrix can be any size < 20.
The pattern is recursive.

Step one: Matrix is fed into the routine.
[size=12] 3 5 5 4 1

2 2 0 2 2
2 4 3 1 0
0 4 1 0 0
1 2 1 3 3[/size]


Step two: Pick number in the top row and test all paths.
[size=12]{3}5 5 4 1

2 2 0 2 2
2 4 3 1 0
0 4 1 0 0
1 2 1 3 3[/size]


Picking {3} we can remove the rest of {3}'s row and column.
[size=12]{3}

2 0 2 2
4 3 1 0
4 1 0 0
2 1 3 3[/size]

...and we're left with 4x4 matrix.

Goto step one - until matrix is 2x2 then max value can be determined by:
[size=12][a b]  value = a+d, if a+d > b+c

[c d] value = b+c, if b+c > a+d[/size]

...and return the value. Then add it with the { } and return value... etc...



This works fine until the size of the matrix grows. At 20x20 the number of patterns searched will be 20factorial = 2.4x10^18, which will take almost forever. ;)
Posted on 2002-11-25 18:22:00 by iblis
/me thinks of an FSM solution... if there is one. :)
Posted on 2002-11-25 21:27:46 by stryker
what is FSM? :confused:

Jibz, that idea is exactly what I had come to at first (swap untill no better solution can be reached). :) although it's fast, it isn't as fast as kuhn munkres's.

thanks everyone for discussing it.
Posted on 2002-11-30 01:35:54 by C.Z.
finite state machine, same idea used by some string searching algorithms...

It's hard to come up with the right conditions though... :(

I'm already mixing a lot of combos for the condition from levels to positions to adjacent arrays whether on top or left or bottom or right...

It's just way to hard since when the matrix grows at a random rate from 5x5 to 12x12 to 7x7... it's hard to keep up with the conditions...

I'm also thinking about treating the matrix as thought it was like a triangle...perhaps I could come up with something :)

I have a lot of weird ideas though, you don't want to know all... :grin:
Posted on 2002-11-30 02:06:00 by stryker
Posted on 2002-11-30 13:17:42 by Nexo