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) _
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, _
= Windows.Forms.DialogResult.No _
Then Exit Sub
Dim start_time As DateTime = Now
' Assign the first item.
Dim stop_time As DateTime = Now
txtExhaustiveTime, txtExhaustiveDifference, _
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.
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)
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.
' 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
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 noderepresenting 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.
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))