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

(This method is similar to one that is described on my forthcoming book A Practical Introduction to Computer Algorithms. I'll post more about it later when it's closer to publication.)

The examples Recursively 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 * 314 = 66,961,566 possible paths. In fact there are 24,590,106 paths through that array, 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 of an 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 more than 24 million to only 30 thousand.

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 algorithm still searches a lot of paths so this only works up to a point. For larger problems, even it isn't fast enough and you'll need to use heuristics to search for approximate paths through the array.

(The example program's DisplayNumbers method also shows the branch and bound solution with red letters so you can compare it to the exhaustive solution that has a green background.)

   

 

What did you think of this article?




Trackbacks
  • No trackbacks exist for this post.
Comments
  • No comments exist for this post.
Leave a comment

Submitted comments are subject to moderation before being displayed.

 Name

 Email (will not be published)

 Website

Your comment is 0 characters limited to 3000 characters.