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.
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.
This is very interesting problem, I don't know anything about this algorithm.
Maybe seeing other explainations might help?
http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.pdf
http://www.npac.syr.edu/copywrite/pcw/node222.html
http://www.florin.com/valore/guests/sce2.html
http://cheng.ececs.uc.edu/cs543/5-22.html
Maybe seeing other explainations might help?
http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.pdf
http://www.npac.syr.edu/copywrite/pcw/node222.html
http://www.florin.com/valore/guests/sce2.html
http://cheng.ececs.uc.edu/cs543/5-22.html
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.
Sigh, a printing error led me to disorientation searching for munkras.
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... :)
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.
It is an interesting problem though. I need to think about it more.
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. :)
It's kinda hard to explain what I really meant here but I'm sure everybody can see a pattern on the looping. :)
3 5 5 4 1
2 2 0 2 2
2 4 3 1 0
0 4 1 0 0
1 2 1 3 33 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 33 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 33 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 33 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 33 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 3Level 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 3It's kinda hard to explain what I really meant here but I'm sure everybody can see a pattern on the looping. :)
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 :-)
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 ;-)
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 ;-)
Don't forget, the matrix can be any size < 20.
The pattern is recursive.
Step one: Matrix is fed into the routine.
Step two: Pick number in the top row and test all paths.
Picking {3} we can remove the rest of {3}'s row and column.
...and we're left with 4x4 matrix.
Goto step one - until matrix is 2x2 then max value can be determined by:
...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. ;)
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. ;)
/me thinks of an FSM solution... if there is one. :)
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.
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.
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:
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:
This algo here:
http://math.uc.edu/~halpern/Linear.progr.folder/Handouts.lp.02/Hungarian.algorithm.pdf
ps: i am use this in prog.
http://math.uc.edu/~halpern/Linear.progr.folder/Handouts.lp.02/Hungarian.algorithm.pdf
ps: i am use this in prog.