Max sum cyclic path of fixed length in matrix

Question

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves are up, down, left, right and each position can be visited multiple times but only contributes to your sum once.

Example: for K = 8

7 3 5 9
1 2 0 4
9 4 2 7
7 6 3 2

Optimal route (I think): 0 2 4 9 7 6 3 2 0

First off, of course K has to even (or the problem should state of length at most K). Secondly I was thinking of a solution along the lines of:

opt[i][j][t] = the maximum sum that can be obtained at position (i,j) at time t

The problem with this is that you can't be sure where you can come from. There is no way to (efficiently) know what values you can use to calculate opt[i][j][t]. I could keep the actual path for each position but that would be $O(nmk^2)$ memory, which is essentially $O(n^6)$ - which is extremely unfeasible. Even the solution itself which is $O(nmk) = O(n^4)$ is probably a little too slow. And, in fact, if I have to check each path that would make the complexity as bad as the memory necessary.

Does anyone have any ideas? I would appreciate hints to try to figure it out myself, not actual solutions. Thanks!

Answer 1

problem with this is that you can't be sure [which path] you can come from.

Indeed. So do it exhaustively for all feasible paths. That is, work on subproblems where you vary $t$ up to $K$, and store their results, at least for a little while. It should be possible to discard partial results corresponding to clearly bad solutions, and consume just $O(t^2)$ memory to remember the cells we should avoid.

Naively one could access a dense matrix opt by dereferencing opt[i][j]. To access the $n$th variant of a matrix with sparse edits applied to it, first probe a mapping to see if edit[(i, j, n)] exists, and if not fall back to dereferencing the dense matrix in the usual way. You may find it convenient to build up a path for the $n$th variant as a list of (i, j, value) tuples.

Additionally, we can decompose into the "outbound" and "inbound" sub-problems. Visiting a cell essentially sets that cell to zero, so each candidate outbound path gives rise to a new matrix. In the end the outbound path length will be $\frac{K}{2}$ and each new matrix gives rise to another $\frac{K}{2}$ inbound problems. The inbound solver would probe a hash map, and would add zero to the reward for any cell appearing in the outbound path.

Consider the Manhattan distance between current cell and origin. A decent heuristic for 1st stage search would be to make that distance strictly increasing on the outbound path, then strictly decreasing on the inbound path, which reduces the search space a little. Your idea about storing optimal values is a good one for further pruning the search space.

Please do keep us posted on your progress, especially on any pruning techniques that seem promising.