Getting N top scores from a matrix

Question

I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example:

M[4][4] = { (13, 8, 5, 3), (11, 9, 7, 4), ( 8, 6, 2, 1), ( 6, 5, 4, 1) }

So the top 6 scores of that matrix will be:

top_scores = { (13, 11, 8, 6), // 38 (13, 11, 8, 5), // 37 (13, 11, 6, 6), // 36 (13, 11, 8, 4), // 36 (13, 9, 8, 6), // 36 (13, 11, 6, 5), // 35 }

What I want is to get the best scores directly, not calculating all the possible combinations and picking the top ones, because the matrix can be much bigger. I've tried to solve it with different approaches, but I failed in all of them.

Answer 1

What you want to do is view your problem as a problem on a directed layered graph. This will allow you to solve the problem using algorithms for the $k$-th shortest paths problem.

In your example you would construct this graph:

The arcs with no label have weight zero.

Finding the $k$-th shortest paths from $s$ to $t$ will find the $k$ top scores according to your definition. There are many efficient algorithms for obtaining the $k$-th shortest paths, including a variation on Dijkstra's algorithm which is probably the easiest to implement.

PS. Some of these algorithms require that the weights of the arcs be non-negative. That can be easily achieved in your case, by adding a large enough constant to every weight, e.g., shifting every weight by +13 in your example. The result is equivalent, since all the paths from $s$ to $t$ contain the same number of arcs.