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.)

Look at the picture on the right. The goal is to find a path through the array of numbers from the first row to the last row. When moving from one row to the next, you can move one column left or right, or keep the same column as the row above. The goal is to find the path that maximizes the total of the numbers visited.

The following code shows how the program makes the array of numbers when you click the Make Numbers button.

private void btnMakeNumbers_Click(object sender, EventArgs e)
{
    NumRows = (int)nudNumRows.Value;
    NumCols = (int)nudNumCols.Value;
    Numbers = new int[NumRows, NumCols];
    Random rand = new Random();
    for (int row = 0; row < NumRows; row++)
    {
        for (int col = 0; col < NumCols; col++)
        {
            Numbers[row, col] = rand.Next(1, 99);
        }
    }
    BestPath = null;

    // Display the numbers.
    DisplayNumbers();

    // Enable the Find Path button.
    btnFindPath.Enabled = true;
    lblTotal.Text = "";
}

The code reads the number of rows and columns you entered and then randomly generates the array of numbers. It then calls DisplayNumbers to display the numbers. I'll describe that method later after I explain how the program generates the best path.

The following FindBestPath method finds the best path through the array.

// The best path.
private int[] BestPath = null;
private int BestTotal = int.MinValue;

// Find the best path.
// Return the path's total value.
private int FindBestPath()
{
    // Make a test path, one entry per row.
    int[] test_path = new int[NumRows];

    // Start in row 0 and try each column.
    for (int col = 0; col < NumCols; col++)
    {
        test_path[0] = col;
        FindPath(test_path, 1);
    }

    // Return the best total.
    return BestTotal;
}

The method starts by creating a test_path array with one entry per row. It will hold the column used in each row.

The program then tries using each column as the first number visited. For each column, it fills in that column number in test_path[0] and then calls the following FindPath method to explore solutions that begin with that first column.

// Recursively explore paths starting with the indicated row.
// Return the path's total value.
private void FindPath(int[] test_path, int row)
{
    // 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.
        int total = 0;
        for (int r = 0; r < NumRows; r++) total += Numbers[r, test_path[r]];
        if (total > BestTotal)
        {
            // This is an improvement.
            BestTotal = total;
            Array.Copy(test_path, BestPath, NumRows);
        }
    }
    else
    {
        // We don't have a complete solution.
        // 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)
        {
            test_path[row] = prev_col - 1;
            FindPath(test_path, row + 1);
        }

        // Column
        test_path[row] = prev_col;
        FindPath(test_path, row + 1);

        // Column + 1
        if (prev_col < NumCols - 1)
        {
            test_path[row] = prev_col + 1;
            FindPath(test_path, row + 1);
        }
    }
}

The FindPath method does the most interesting work. It recursively fills in the test_path array. When the array is completely full, it checks the test solution's value to see if it is an improvement over the current best solution.

The method starts by checking its row parameter to see if the test solution is complete. If row >= NumRows, then the method has been called to fill in the entry for the row after the last row in the array. That means the test array is full so the method adds up the total value of the solution, compares it to the best solution found so far, and saves it if this is an improvement.

If the test solution is not complete, the method tries each of the three possible values for the column in this row and then recursively calls itself to try values for the rest of the test solution's rows. (Eventually the recursive calls fill in all of the rows' values and previous case occurs so the method checks for an improved solution.)

That's all there is to finding the best solution. The following code shows how the program displays the numbers and the best solution, if there is one.

// Display the numbers and the best path.
private void DisplayNumbers()
{
    // Display the numbers.
    string txt = "";
    for (int row = 0; row < NumRows; row++)
    {
        txt += Environment.NewLine;
        for (int col = 0; col < NumCols; col++)
        {
            txt += string.Format("{0,3}", Numbers[row, col]);
        }
    }
    txt = txt.Substring(Environment.NewLine.Length);
    rchNumbers.Text = txt;

    // Display the best path.
    if (BestPath == null) return;
    rchNumbers.Select();
    rchNumbers.SelectionBackColor = Color.White;
    for (int row = 0; row < NumRows; row++)
    {
        int start = 1 +
            row * (NumCols * 3 + Environment.NewLine.Length - 1) +
            BestPath[row] * 3;
        rchNumbers.Select(start, 2);
        rchNumbers.SelectionBackColor = Color.LightGreen;
    }
    rchNumbers.Select(0, 0);

    // Display the best path in the Console window.
    for (int row = 0; row < NumRows; row++)
        Console.Write(Numbers[row, BestPath[row]] + " ");
    Console.WriteLine("");            
}

The code first loops through the numbers a builds a multiline string that contains them all. It sets the rchNumbers RichTextBox's Text property to the result.

Next the code gives the RichTextBox a white background. It then loops over the rows. For each row, it gets the column that is part of the best solution and calculates the location of that row and column in the text. It selects the corresponding text and sets the RichTextBox's background color to light green for the selection.

The moves the RichTextBox's selection point to the beginning of the text so nothing is shown as selected. It finishes by displaying the values selected in the best solution in the Console window so you can verify that the highlighted values match the best solution.

This technique of building a solution by recursively trying every possibility for each of the required entries is quite powerful. You can use this method to solve many hard problems, although it requires you to look at a lot of potential solutions so it only works for relatively small problems. (My book talks more about this and explains some approaches you can use to solve larger problems.)

   

 

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.