2

There's a well-known dynamic programming problem that goes by the name of the "gold mine." You have a n x n grid, each cell of which contains a certain value of coins. You begin at the bottom left and can only move right, up, or diagonally up and right. The goal of your algorithm is to determine the path through the mine that maximizes the amount of gold you collect.

An example solution: http://www.ideserve.co.in/learn/gold-mine-problem

Is it possible to solve this problem using a divide-and-conquer approach using O(n) space or less, while still using O(n^2) time?

My first suspicion is that you can divide up the grid into quadrants recursively, find the best path in each of those quadrants, then somehow merge the result in the end to get the best path through the whole thing. Using only O(n) space you can store the paths in each quadrant, since the longest path through each of them is 2n - 2. But in doing that you "forget" about other cells that are worth points that weren't chosen, and the answer provided by that algorithm has the tendency to be incorrect. If we look through all the cells at each merge step in an attempt to remember the discarded ones (which takes n^2 time), then the solution to the recurrence relation for running time becomes n^2 log n instead of n^2, via the master theorem. The merge step has to be done in O(n log n) or O(n).

The space requirement here is the kicker more so than the time requirement.

  • 1
    A few observations: If all cells have a >0 value, then moving diagonally is never a good idea and all best paths will always end at the top right. If all cells are >=0, then diagonal movement might not hurt in some cases, and there may be many equivalent best paths that end short of the top right. If cells can have negative values, then diagonal moves may be essential and the best path(s) could end anywhere, even at the bottom left. Interestingly, the >0 and >=0 observations do not hold in the version in your link. – 8bittree Oct 7 '16 at 19:14
  • Do you really need to avoid dynamic programming, or do you just need to avoid the n^2 space requirement? – Winston Ewert Oct 7 '16 at 19:45
  • By O(n) space, do you mean O(n) additional space on top of the Theta(mn) space required to hold the original grid? And should answers assume that the grid is read-only? – Peter Taylor Oct 7 '16 at 21:23
  • When you say O(n), does n mean the width of the input grid or the total number of cells? – Tanner Swett Oct 7 '16 at 23:06
  • @WinstonEwert My exact problem is slightly different - I'm using a well known problem as an example where the same principles apply - but I want to know if it can be done with divide and conquer, specifically. I figured out my own problem, but I'm not sure if the same solution applies here so I'll leave the question open. – NmdMystery Oct 7 '16 at 23:47
1

There's a problem with your divide-and-conquer approach of dividing the grid into four quadrants: The solutions for the quadrants are not independent of each other. And you can't find the optimal solution by combining the locally optimal sub-solutions of each quadrant.

+---+---+
| C | D |
+---+---+
| A | B |
+---+---+

Here, D can be calculated independently. However, the solution for C depends on D, B depends on D, and A depends on B, C, D. (Dependency is determined by reachability.)

Solving the problem for a quadrant does not mean we find the best path. Instead, we have to find the best path for each cell on their left and lower edges, since we do not know where the best path will enter that quadrant.

The exact space complexities depend on what we are trying to calculate:

  • the best path: this will take O(n) space per record for a quadrant with n-long edges.
  • the value of the best path: this will take O(1) space per record.

I'll sidestep that for this discussion and will denote the space requirement with s(n). Then, the solution of a quadrant requires O(n·s(n)) space for the records of the left and lower edge.

The total space complexity of the algorithm is then given through the recurrence relation T(n) = 4·T(n/4) + O(n · s(n)). This would give T(n) ∈ Θ(n · s(n)) for either choice for s(n).

Writing down the algorithm would be extremely tedious, so I'll not do that here. However, the signature of the recursive solver would be:

solve_quadrant(grid: int[n, n],
               x_start: int, x_end: int,
               y_start: int, y_end: int,
               upper_edge: Result[],
               right_edge: Result[])
               -> (left_edge: Result[], lower_edge: Result[])

And the top-level invocation would be:

solve(grid: int[n, n]) -> Result {
  left_edge, lower_edge = solve_quadrant(grid, 0, n, 0, n, {0, ..., 0}, {0, ..., 0})
  return lower_edge[0] // assuming bottom-left is at coordinate (0, 0)
}

Since the divide-and-conquer algorithm has to satisfy the same data dependencies as a dynamic programming solution, it is unlikely to beat the DP solution with space complexity Θ(n · s(n)). In fact, the complexities of the “divide & conquer” algo and the DP algo are equivalent, since they do the same thing the same way – only the strategy for subdivision is different. However, the DP solution is far easier to program since it doesn't have to consider as many edge conditions.

  • This is what I figured all along, but it's a homework question (with different rules regarding what combinations of values can be gathered which makes it more difficult). I found the method to get the value, but the path seems impossible. – NmdMystery Oct 8 '16 at 23:18
0

It turns out there was an answer.

The algorithm to do this works as follows:

Divide up the grid into quadrants. Begin solving the DP values for the top right quadrant, then the top left, then the bottom right. When you're doing this, save only the DP data for the cells that border other quadrants, and get rid of all other working space.

The actual recursion then begins in the bottom left quadrant. This subproblem looks identical to the larger problem - divide up the quadrant in four, and do the same thing again.

When you get down to a grid of size 2x2, solve normally using the DP approach. This is constant time. When you're finished getting the path through that grid, you'll also know what quadrant you're entering next because you've kept the border cells in memory and can make a choice. Now, solve the path through that quadrant, and then the last one.

The path only travels through three quadrants because of the constraints on the moveset. So we're only actually solving three sub-problems, not four. It's because of this that the recurrence still simplifies to O(n^2):

T(n) = 3T(n/2) + O(n^2)

The O(n^2) is the first part of the algorithm, where you're getting the bordering DP cells. The 3T(n/2) is the solving of the three quadrants. This belongs to the case in the Master Theorem where log_b(a) < c, therefore T(n) = O(n^c) = O(n^2).

The recurrence for space is this:

T(n) = T(n / 2) + n

This belongs to the same case in the Master Theorem as the recurrence for the running time. The total space used is O(n).

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.