The best route traversing a maze

Question

A two dimensional integer matrix with dimension (m,n) is given and one person is allow to traverse from the (0,0) to (m-1,n-1). The valid moves is going right or going down. I am asked to find the max sum path to reach the destination. This is quite simple since

MaxPathSum(i,j) = Math.max(MaxPathSum(i,j-1),MaxPathSum(i-1,j)) + Matrix[i][j]

However, if there are two people both are allowed to traverse from (0,0) to (m-1,n-1). The value of one cell would be set to zero once this cell has been visited by someone. Given this constraint, what would be the max sum of these two paths?

Any hint is appreciated. Thanks.

Answer 1

If values are non-negative (>=0) than there is a pair of maximal paths that do not cross each other. It can be checked by construction.

Suppose that maximal paths (A and B) cross each other, like:

..B.
.B.A
AXA.
.B..

Than we can interchange parts of paths just to touch each other where sum is the same.

..A.
.A.B
AXB.
.B..

Since values are non-negative, sum of new paths is >= that of original A+B

..A.      ..A.
AA.B  or  .A.B
ABB.      AAB.
.B..      .BB.

It seems to me that some DP solution should exist, but I can't find one :-)

There is a greedy approach which finds quite good solution. It uses property that two independent paths can be improved with upper operations. Algorithm is like:

find first maximal path
set 0 to path elements
find second maximal path
improve paths with upper operations

Not optimal part are zeros set on first path elements. These zeros force second path to not cross the first one. Improvement operations use elements around crossing so improvement will add some neighbouring element to the result. It can be used to set first path elements to value of some neighbour's value. Right now, I am not sure which neighbour to use since there are more combinations, especially if crossing is a longer overlap. I think that good start point is to set it to minimal possible neighbour's value.

Answer 2

First of all notice that each step always increases the Manhattan distance from the origin (x + y) by one. This means that if you move two markers at once down two paths, moving each alternately, then if the paths cross the counters must end up on top of each other: you can't have one marker reaching a square the other vacated several moves ago.

Now you can think of the original MaxPathSum(i,j)=... calculation as a dynamic program on a state space where the state is the position of a single marker. For two paths one obvious thing to do would be to run a dynamic program on a state space where the state is the position of two markers. Then you could have MaxPathSum(i,j,k,l)=... where a more complex expression considers the four possible moves of two markers and ensures that Matrix[i,j] is not counted twice if i==j && k==l. Because of what we have worked out above, we only have to consider collisions of this form, so we don't have to remember the paths the markers have taken to their current positions.

This looks like it squares the size of the state space. It's bad, but not quite that bad, again because of the Manhattan distance constraint. You can do the recursion calculations in a series of steps, with each step working out all the answers for the states of a particular Manhattan distance from the origin. You only need to consider pairs of states that have the same Manhattan difference of each other. If you have an NxN array, the original calculation costs O(N^2). If you want to do it in steps where each step covers all the cells with a particular Manhattan distance then you have O(N) steps each covering O(N) cells. If you are worrying about two paths then you still have O(N) steps but each step covers O(N^2) pairs of cells, so the total cost is O(N^3) - but the input data (the matrix) is of size O(N^2) so you could equally well think of this as O(N^1.5) or raising the original cost to the power 1.5.