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?

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

  • 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 '14 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 '14 at 16:33
  • Can you explain merge_and_select_k a bit more? – redDragon Dec 6 '14 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 '14 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 '14 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, privacy policy and cookie policy

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