I had the following question I was trying to solve:
You are given a
n*nmatrix. 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
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
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.