1

I had the following question I was trying to solve:

You are given a n*n matrix. Every cell of the matrix contain some value (positive).

You are currently at (0,0) and you have to go to right most and bottom most cell ((n-1)*(n-1)). You can move either right or down.

I am aware of finding the most optimal solution for this using the dynamic programming approach. But what is the best way to find the kth optimal solution?

3
  • 2
    This is related to Project Euler problem #81.
    – user40980
    Oct 26, 2014 at 20:31
  • 1
    It's not entirely clear from your description what you mean by "optimal solution". What are you optimizing for? Oct 27, 2014 at 0:05
  • Optimal meaning minimum path from (0, 0) to (n, n).
    – redDragon
    Oct 27, 2014 at 14:13

2 Answers 2

2

In the classic version(k = 1, solve for best path), the key insight used is as follows.

1) In computing best path for cell (i, j) (best[i][j] is the cost of best path from top-left to (i, j)), we notice that this path could either come from it's left or upper neighbor. Thus we do (leaving aside corner cases for a moment)

best[i][j] = min(best[i][j-1], best[i-1][j]) + value[i][j]

2) Now, if we want to compute k best paths from top-left corner to (i, j), we can again follow a similar, but more general technique. Here, best[i][j] can be thought of as a list of k best paths instead of one best path.

best[i][j] = merge_and_select_k(best[i-1][j], best[i][j-1], k)

merge_and_select_k takes two input lists, an integer k - It concatenates the two lists and keeps only the k best values. Of course, you must also add value[i][j] to all these selected items.

3) Loop over the matrix, just like in the classic version and compute best[i][j] for every i and j. Your final result is best[n][n][k].

4) This works because, we only need to consider best[i-1][j] and best[i][j-1] for computing best[i][j]. Time complexity is O(k * n * n) and space complexity is O(k * n), as we only need keep the values for current and previous rows.

5
  • Space complexity is O(k*n) only if we're not interested in the path itself - but only in it's length. Otherwise - how is this different to the addendum to my own answer?
    – Ordous
    Dec 5, 2014 at 16:29
  • Aah, didn't see your addendum. Space complexity is still O(k * n) if we are only interested in the path values. It's O(k * n * n) if we are also interested in the actual paths(routes) themselves.
    – VinyleEm
    Dec 5, 2014 at 16:33
  • Can you explain merge_and_select_k a bit more?
    – redDragon
    Dec 6, 2014 at 2:32
  • I think an example would suffice. merge_and_select_k([3, 4, 12], [1, 21, 100], 3) should give 3 best values from the two lists -> [12, 21, 100].
    – VinyleEm
    Dec 6, 2014 at 7:30
  • Thanks for the idea. If we need to store even the path and not just the distance, what would you suggest?
    – redDragon
    Dec 8, 2014 at 0:02
0

This is likely not the best way, but given there are no other answers, here is a way.

The problem of finding the k-th optimal path is AFAIK not very well studied for matrices, but is quite common in graphs. In fact, Wikipedia has some examples of how it can be done in a weighted directed graph. Hence a solution that transforms you matrix to a graph and employs the algorithm from the Wiki:

Algorithm:

Transform your matrix into a weighted directed graph. Every entry in your matrix will be a vertex, and vertex A has an edge to vertex B iff A was above or to the left of B in the matrix. The weight of the edge is the end vertex value.

Now, use Yen's algorithm to find the k-th optimal path. (it's a fairly known, but long algorithm, so not posting it here).

Complexity

Creating the graph is trivial and takes linear time in the size of your matrix. The resulting graph has N^2 vertexes and 2N(N-1) edges. Yen's algorithm requires K*l calls to Dijkstra, where l is the length of the spur paths (In this case it's 2N, since all paths here are at most 2N length).

Hence the total runtime is expected to be O(K * N^3 * log(N)). This is a very pessimistic bound, but you may find that the cubic behaviour is indeed true - this solution does not use any pros from the graph structure being matrix-like.


After thinking about this a bit more:

There is an obvious naive solution that just takes the standard dynamic programming approach, and instead of storing the shortest path to each node stores the k shortest paths.

This solution will be faster than the above, clocking at O(K * N^2). However, it uses O(K * N^2) space, which is much larger than O(N * (K + N)) of the above solution. I guess here you would need to make a decision on what resource is more scarce.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.