Title: Use branch and bound to find the highest value path through a two-dimensional array of numbers in C#

This method is similar to path-finding methods described in my books Essential Algorithms: A Practical Approach to Computer Algorithms and Interview Puzzles Dissected, Solving and Understanding Interview Puzzles. Follow those links for more information including tables of contents.

The example Find the highest value path through a two-dimensional array of numbers in C# uses recursion to exhaustively search for the best possible path through the values in an array.

This is effective and reasonably simple but it can be very time consuming. There are roughly 3 choices at each row in the array (ignoring edge effects) and the program could start in any column. If the array has 14 rows and columns, then there are roughly 14 * 3¹⁴ = 66,961,566 possible paths. (In fact there are only 24,590,106 paths through that array, but that's still a big number.)

Branch and bound is a technique that lets you trim many of the paths from the search. As it recursively builds test solutions, the algorithm keeps track of the test solution's total value. At each step, it calculates the maximum amount by which the value could be increased. For this example, it multiples the number of rows it has not yet examined by the maximum possible value in any array entry and adds that to the test solution's value. It is unlikely that the test solution could actually be improved to that value, but this gives an upper bound on the test solution's value. If the total maximum possible value is smaller than the value of the best solution found so far, then the algorithm stops considering that test solution.

This may seem like a small change that wouldn't remove many paths from the search, but it can be quite effective. You can see in the picture that in one trial branch and bound reduced the number of values recursively examined from 18,136 to only 1,255, less than 10% of the total possible paths.

The following code shows the new search method. The highlighted lines show differences between this version and the previous exhaustive search.

// Recursively explore paths starting with the indicated row. // Return the path's total value. private void FindPath2(int[] test_path, int test_total, int row) { NumFindPathCalls++; // See if we have a complete solution. if (row >= NumRows) { // We have a complete solution. // See if it is better than the best solution so far. if (test_total > BestTotal2) { // This is an improvement. BestTotal2 = test_total; Array.Copy(test_path, BestPath2, NumRows); } } else { // We don't have a complete solution. // See if there's any chance we can improve // on the best solution found so far. int rows_remaining = NumRows - row; if (test_total + MaxValue * rows_remaining <= BestTotal2) return; // Try the possibilities for this row. // Get the column used in the previous row. int prev_col = test_path[row - 1]; // Column - 1 if (prev_col > 0) { int col = prev_col - 1; test_path[row] = col; FindPath2(test_path, test_total + Numbers[row, col], row + 1); } // Column test_path[row] = prev_col; FindPath2(test_path, test_total + Numbers[row, prev_col], row + 1); // Column + 1 if (prev_col < NumCols - 1) { int col = prev_col + 1; test_path[row] = col; FindPath2(test_path, test_total + Numbers[row, col], row + 1); } } }

The example program's DisplayNumbers method shows the branch and bound solution with red letters so you can compare the branch and bound solution to the exhaustive solution shown with a green background. Often the two are the same, but they may be different if there are multiple paths with the same total value.

The branch and bound algorithm still searches a lot of paths, so this only works up to a point. For larger problems, even branch and bound isn't fast enough and you'll need to use heuristics to search for approximate paths through the array. The books I mentioned earlier here and here describe those approaches.

Download the example to experiment with it and to see additional details.