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
