How do I find the optimal path through a grid?

user_19165728 0
Viewed 42

Overview of the problem: You are a truffle collector, and are given a grid of numbers representing plots of land with truffles on them. Each plot has a certain number of truffles on it. You must find the optimal path from the top of the grid to the bottom (the one that collects the most truffles). Importantly, you can start from any cell in the top row. When you are at a cell, you can move diagonally down to the left, directly down, or diagonally down to the right. A truffle field might look like this:

The truffle fields also do not have to be square. They can have any dimensions.

So, I have created an iterative algorithm for this problem. Essentially, what I have done is iterate through each cell in the top row, finding the greedy path emanating from each and choosing the one with the largest truffle yield. To elaborate, the greedy path is one in which at every step, the largest value that can be reached in the next row from the current cell is chosen.

This algorithm yields the correct result for some truffle fields, like the one above, but it fails on fields like this:

This is because when the algorithm hits the 100 in the third column, it will go directly down to the 3 because it is the largest immediate value it can move to, but it does not consider that moving to the 2 to the left of it will enable it to reach another 100. The optimal path through this field obviously involves both cells with a value of 100, but the greedy algorithm I have now will never yield this path.

So, I have a hunch that the correct algorithm for this problem involves recursion, likely recursive backtracking in particular, but I am not sure how to approach creating a recursive algorithm to solve it. I have always struggled with recursion and find it difficult to come up with algorithms using it. I would really appreciate any ideas you all could provide.

Here is the code. My algorithm is being executed in the findPath method: https://github.com/jhould007/Programming-Assignment-3/blob/master/Truffle.java.

algorithm java
1 Answers

You could use recursion, but there's a simple iterative fix to your approach as well.

  1. Instead of the top row, start with the bottom one. Create a 1D array values and initialise it with the values of the bottom row.
  2. Start iterating curr_row from row max_row-1 to 0. For each iteration, create a temporary array temp and initialise it with 0's.
  3. For a row curr_row in the iteration, value[i] represents the max value that you can get if you start from row curr_row+1 (basically the next row) and column i.
  4. To update temp in each iteration, we just need to pick the best path from the next row, which can be fetched from values array.
for column in range [0, max_column]:
    temp[column] = truffle_value[column] + max(value[column], value[column+1], value[column-1])

// since temp holds the values for the next iteration in our loop
value = temp

In the end, the answer will simply be max(values).

user_93507200
Related