Finding an optimal solution

More a general programming question

[Stark]

I have a script that produces an effective grid of information within a PHP data structure such as the following:

. ¦ 1 ¦ 2 ¦ 3 ¦ 4 
--+---------------- 
1 ¦ 9 ¦ 1 ¦ 6 ¦ 4 
--+---+---+---+---- 
2 ¦ 5 ¦ 4 ¦ 8 ¦ 3 
--+---+---+---+---- 
3 ¦ 5 ¦ 7 ¦ 2 ¦ 7 
--+---+-------+---- 
4 ¦ 3 ¦ 6 ¦ 5 ¦ 5 

(Took me ages to type that out and it's still all over the place)

Now, I want to be able to map columns to rows on a 1 to 1 basis, such that I am selecting the lowest possible total score.

e.g. I could do (1,1) (2,2) (3,3) (4,4) for a total of 9+4+2+5 = 20

This isn't the optimal solution though as replacing the first two with (1,2) and (2,1) would lower the total to 13. This may or may not be optimal, I just pulled the numbers out of the air.

The questions is, what sort of algorithm do I use for an n x n matrix to be able to identify the optimal (or near optimal) mapping of columns to rows so that I minimise the total of their cells?

Any ideas of where to start looking would be greatly appreciated even if no-one can provide an answer for me. I suspect the problem isn't very straight-forward!

[Stark]

Well, in case anyone comes across a similar problem, I have found the following:

The problem is called a linear assignment problem and can be solved using the Hungarian Method.

I believe this page provides one of the simplest explanations with a nice worked example

[ee.oulu.fi...]

[mcibor]

Such optimalization methods can be also solved using:

- genetic algorithm
- neural net
- bough and branch method

However with the above mentioned methods you can't be sure that the result is correct. They are developed because they are much faster than counting all possible answers. (My colleague was using them to search a total of 125! possibilities - Matlab could count that number, not mentioning doing the proper counting!)

Best regards
Michal Cibor