Making Delicate Decisions : Page 2

Exhausting Explorations
The most straightforward way to search the decision tree shown in Figure 1 is to exhaustively visit every node in the tree. At each leaf node, the program determines the corresponding solution's value and decides whether that beats the best solution so far.

For the two-person "booty division problem," you can use the difference between the values of the two peoples' loot as the solution's value. For example, if Person 0's loot is worth 100 doubloons and Person 1's loot is worth 110 doubloons, then the value of the solution is 10. The goal is to search the decision tree to find the solution with the smallest value. An outcome where the treasure is divided exactly evenly will have a value of 0.

The following code shows how the BootyDivider sample program (which you can download in both VB.NET and C# versions) performs an exhaustive tree search. The btnAlgExhaustive_Click event handler executes when you click the Exhaustive button, and manages the process:

   Private Sub btnAlgExhaustive_Click( _
      ByVal sender As System.Object, _
      ByVal e As System.EventArgs) _
      Handles btnAlgExhaustive.Click
      If m_NumItems > 25 Then
         If MessageBox.Show( _
            "Warning: This tree contains " & _
            FormatNumber(2 ^ (m_NumItems + 1) - 2, 0) _ 
            & " nodes" & vbCrLf & vbCrLf & _
            "Do you want to continue?", _
            "Continue?", MessageBoxButtons.YesNo, _
            MessageBoxIcon.Question) _
            = Windows.Forms.DialogResult.No _
            Then Exit Sub
      End If
   
      ClearResults(txtExhaustiveNodesVisited, _
         txtExhaustiveTime, txtExhaustiveDifference)
      Dim start_time As DateTime = Now
   
      ' Assign the first item.
      ExhaustiveAssignItem(0)
   
      Dim stop_time As DateTime = Now
      ReportResults(txtExhaustiveNodesVisited, _
         txtExhaustiveTime, txtExhaustiveDifference, _
         stop_time.Subtract(start_time))
   End Sub

The preceding method warns users if the completed tree would contain too many nodes, calls the ClearResults method to clear out some result variables, and then calls the ExhaustiveAssignItem method, which does all the real work. Finally, it calls ReportResults to display the results.

The ExhaustiveAssignItem method takes a parameter indicating the index of the item it should assign. If the ShortCircuit method (described shortly) returns True, the program has found a perfect solution so the method simply exits:

   ' Assign item number next_index and
   ' then recursively assign the other items.
   Private Sub ExhaustiveAssignItem(ByVal next_index As Integer)
      ' Short-circuit.
      If ShortCircuit() Then Exit Sub
   
      ' See if we have assigned all items.
      If next_index >= m_NumItems Then
         ' We have assigned all items.
         ' See if the test solution is an improvement.
         CheckForImprovement()
      Else
         ' We have not assigned all items.
   
         ' Assign the item to person 0.
         m_TestAssignedTo(next_index) = 0
         m_TestTotalValue(0) += m_ItemValues(next_index)
         ExhaustiveAssignItem(next_index + 1)  ' Recurse.
         m_TestTotalValue(0) -= m_ItemValues(next_index)
   
         ' Assign the item to person 1.
         m_TestAssignedTo(next_index) = 1
         m_TestTotalValue(1) += m_ItemValues(next_index)
         ExhaustiveAssignItem(next_index + 1)  ' Recurse.
         m_TestTotalValue(1) -= m_ItemValues(next_index)
   
         m_NodesVisited += 2
      End If
   End Sub

If the perfect solution was not found (no short circuit), the method checks the index that it should assign. If the index is greater than or equal to the number of items we are trying to divide, then every item has been assigned so the method calls CheckForImprovement to save the new solution if it is an improvement.

Otherwise, when no perfect solution has been found and not all the items have been assigned, ExhaustiveAssignItem tries assigning the next item. First it assigns the item to Person 0. It sets the item's m_TestAssignedTo entry to indicate that the item is assigned to Person 0 and adds the item's value to Person 0's total assigned value. The method then recursively calls itself to assign the next item.

After the recursive call returns, the ExhaustiveAssignItem method removes the item from Person 0's assignments and assigns it to Person 1. It sets the item's m_TestAssignedTo entry to indicate that the item is assigned to Person 1, adds the item's value to Person 1's total, and calls itself recursively to assign the next item.

The recursive calls to ExhaustiveAssignItem move up and down the tree until they have traversed every node and visited every leaf node—representing a complete assignment. When the original call returns to the btnAlgExhaustive_Click event handler, the program's variables contain the best possible solution.

Author's Note: I skipped a lot of code that initializes the test, saves the best solutions, deals with displaying results, and otherwise provides support for the algorithms, but you can download the code to see those details.

Obviously, because recursively evaluating every possible solution takes time, you want to stop if you happen to discover a perfect division of the items. The ShortCircuit method handles that by returning True and thus halting the recursion if the current solution divides the booty exactly equally between the two people.

You can control whether the program uses short circuiting or not by checking the program's Allow Short Circuit check box. You can check and uncheck the box to see the difference. Checking it sets the program's m_AllowShortCircuit variable to True. Note that the program will only short circuit if it is possible to exactly divide the loot. If the loot cannot be divided evenly (for example, if the total value of all items is odd), then short circuiting never occurs, and the program uses the exhaustive search to visit every node in the tree.

The ShortCircuit method first checks the value of the m_AllowShortCircuit variable to see whether it is allowed to use short-circuiting, checks whether there is any solution yet, and checks whether the two people have identical total assignment values:

   ' Return True if we have an optimal solution.
   Private Function ShortCircuit() As Boolean
       ' Return true if:
       '   - We are allowed to short-circuit.
       '   - We have assigned values.
       '   - The totals are equal.
       Return m_AllowShortCircuit AndAlso _
           m_BestTotalValue(0) > 0 AndAlso _
           (m_BestTotalValue(0) = m_BestTotalValue(1))
   End Function

Previous Page

Next Page