uppose you and your swashbuckling buccaneer friends attack a Spanish galleon. When the smoke clears you find that you have emerged victorious but now you must begin the more difficult and dangerous task of dividing up the booty. If the division isn’t reasonably fair, you’ll face a mutiny that makes the original skirmish look like a tea party.

The “booty division problem” can be tricky if the treasure includes many discrete items with different values. Sharing 10,000 doubloons is relatively easy but dividing a chest of jewelry with assorted values evenly can be difficult. Fortunately, pirates aren’t generally known for their math skills, so perhaps no one will notice that the shares aren’t worth the same amount. In computer science, the “booty division problem” usually goes by the more prosaic name “partition problem.”

Here are a couple of slightly more realistic partition problem examples. Suppose you need to divide an estate among several heirs. The estate includes a house, some cars, and a boat, none of which can be divided. Estate lawyers have much better math skills than pirates, so if this division isn’t reasonably equitable, you could be in trouble. Or suppose you need to assign software developers with different skill levels to several software projects. If the division isn’t fair, you may face a mutiny of a different kind.

Dividing a collection of resources evenly can be a tough problem. For example, assume you have 20 items (pieces of treasure, estate assets, developers, or whatever) and you need to divide them into two groups. There are 2^20 or just over 1,000,000 possible ways to assign the items to the two groups. While many are obviously poor assignments (such as assigning all items to one group), many of the possible solutions will look sensible, so picking the best solution can be time-consuming.

As the number of items in the problem increases, the number of possible solutions grows by a power of two. With 30 items to divide, there are about one billion possible solutions; with 40 items, there are more than one trillion possible solutions. Even if your computer can evaluate one million solutions per second, it would take more than 11 days to check them all. You need only add a few more items to make solving the problem take years or longer.

While there’s no fast way to enumerate every possible solution and pick the best one, there is a relatively simple model for studying this kind of problem and many others. You can model the assignment of items to one group or another as a decision tree.

This article explains how you can use decision trees to model some extremely complicated problems and describes a few tricks for searching them.

Trees Please
Often you can represent combinatorial problems such as the “booty division problem” by using a tree. Each node in the tree corresponds to a partial assignment of the items in the treasure to the buccaneers. Each branch corresponds to making a new assignment.

I’ll illustrate by starting with a simple problem where you need to divide items with different values between two people. The tree’s root node corresponds to an empty assignment.

The left branch out of the root node corresponds to assigning the first item to the first person. The right branch out of the root corresponds to assigning the first item to the second person.

At the second level of the tree, left branches correspond to assigning the second item to the first person and right branches correspond to assigning the second item to the second person.

More generally, at every node in the tree, the left branch represents assigning the next item to the first person and the right branch corresponds to assigning the next item to the second person. The result is a full binary tree with height equal to the number of items that you need to divide.

Figure 1 shows a decision tree for dividing four items between two people. The nodes below left branches are blue and labeled “0” to indicate that the corresponding items are assigned to Person 0. Nodes below right branches are yellow and labeled “1” to indicate that their corresponding items are assigned to Person 1.

	?
Figure 1. Divide and Conquer: You can model the “booty division problem” for two people with a binary tree.

Each path from the root to a leaf node corresponds to a complete assignment of the items to the people. The node labels tell you to whom each item is assigned. For example, the leftmost path through the tree assigns every item to the Person 0. The path just to the left of the center in Figure 1 assigns the first item to the Person 0 and the other three items to Person 1.

You can model many similar problems with decision trees. For example, in shipping, the “bin packing” problem is to pack a number of items of different weights into as few bins with fixed capacity as possible. For example, suppose you have 10 packages with weights between 10 and 20 pounds all destined for the same location, and you want to ship them in boxes that can hold 50 pounds each. How many boxes do you need?

You can model this problem with a decision tree where each branch represents putting an item in a different box. With 10 items, you might need as many as 10 boxes so the tree would have 10 branches at each node and a total of 10^10 = 10 billion nodes.

Variations on the bin packing problem consider the packages’ two-dimensional areas, three-dimensional volumes, or exact weights and shapes. You can also model them with decision trees, although determining whether a selection of packages can fit in a box is much more complicated.

The knapsack problem poses another question that you can model with decision trees. The knapsack problem is, given a set of items of different weights and values, and a knapsack that can hold a certain amount of weight, what combination of items should you place in the knapsack to maximize the total value? This problem also has piratical applications (which jewels do you stuff in your sea chest before running from the sinking ship?) in addition to some real-world purpose. For example, which experiments should you load on a small satellite to get the best value?

For another example of decision trees, consider tic-tac-toe. You can represent each board position as a node. Each branch out of a node represents a player taking a particular square.

	?
Figure 2. Your Move: You can model the tic-tac-toe problem with decision tree.

Figure 2 shows part of the decision tree for tic-tac-toe. The root node represents the initial empty board. The nine nodes on the next level represent player X taking one of the nine available squares. At the third level of the tree, player O can take one of the eight remaining squares so each second-level node has eight branches. The figure shows the third level nodes when player X picks the center square.

Each node in the fourth level of the tree has seven branches corresponding to the seven remaining squares that player X can take. The tic-tac-toe decision tree continues in this manner, with each node having one fewer branches than its parent node, until the tree’s ninth level, where the nodes have no branches and represent complete assignments of every square (no more moves) to one player or the other. This tree has 9! = 362,880 nodes (not counting the root node) so it can take a while to search the tree completely.

You can model other games using similar decision trees, although the trees are truly enormous. During each turn a chess player can move one of up to 16 pieces in possibly several ways (for example, you can move a queen in up to 27 ways). If you could move only eight pieces four ways each, then each node would have 32 branches. A decision tree for only the first six moves would contain around 1 billion nodes. While the rest of this article shows some ways to search decision trees in general, this kind of game tree requires special algorithms.

Now that you have an idea of the enormous breadth of problems that decision trees can help solve, this article and the sample application focus on the two-person “booty division problem.” You can apply its techniques to other decision trees.

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.

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

When Exhaustive Search Is Not an Option
Exhaustive search, with or without short-circuiting, is guaranteed to find the best possible solution. Unfortunately when the tree grows big enough, exhaustive searching is impossible. My (pretty fast) computer can search a tree containing 20 items and 2 billion nodes in about a quarter of a second but adding only a few more items to the problem causes the tree to become too big to handle. A tree containing 30 items has 1024 times as many nodes and would take about 4 minutes to search. A 40-item tree contains around 2 quadrillion items and would take more than 3 days to search. With 50 items, my computer would require more than 8.5 years to evaluate every possible solution.

With such large trees, exhaustive search isn’t an option. In those cases, you need to turn to heuristics. A heuristic is an algorithm that is likely?but not guaranteed?to produce a good result.

One of the simplest heuristics for tree searching is to follow a random path through the tree. The program starts at the root node, and picks a random branch to move down at each successive node. This corresponds to assigning the items randomly to Person 0 or Person 1. If you follow enough random paths, you will sometimes try the same path twice and you’ll waste some time. For really big trees, however, the odds of following exactly the same path are very small.

In a large tree, the odds of you finding the best possible solution, or even one that’s good, are slim. To give yourself a chance of finding a reasonably useful result, you need to test a lot of random solutions and hope you get fairly lucky.

The following code shows how the BootyDivider program tests random solutions. It starts by asking you how many trials you want to run. It clears out previous results and then enters a loop to perform the trials.

For each trial, the program resets the total assigned values for each person. It then randomly assigns each item to Person 0 or Person 1. It calls CheckForImprovement to see if the new random solution is better than the previous solution and calls ShortCircuit to see if it has found a perfect division. After it finishes the trials, the routine displays the results:

   ' Perform random trials.   Private Sub btnAlgRandom_Click( _    ByVal sender As System.Object, ByVal e As System.EventArgs) _    Handles btnAlgRandom.Click      ' Get the number of trials.      Dim num_trials_txt As String = InputBox( _         "# trials:", "# Trials", _         (3 * m_NumItems ^ 3).ToString())      If num_trials_txt.Length = 0 Then Exit Sub      Dim num_trials As Integer = Val(num_trials_txt)      If num_trials = 0 Then Exit Sub         ClearResults(txtRandomNodesVisited, _         txtRandomTime, txtRandomDifference)      Dim start_time As DateTime = Now         ' Perform the trials.      For trial As Integer = 1 To num_trials         m_NodesVisited += m_NumItems            ' Reset the test totals.         m_TestTotalValue(0) = 0         m_TestTotalValue(1) = 0            ' Make random assignments.         Dim rnd As New Random         For i As Integer = 0 To m_NumItems - 1            ' Pick the person.            Dim person As Integer = rnd.Next(0, 2)               ' Assign the item.            m_TestAssignedTo(i) = person            m_TestTotalValue(person) += m_ItemValues(i)         Next i            ' See if the test solution is an improvement.         CheckForImprovement()            ' Short-circuit.         If ShortCircuit() Then Exit For      Next trial         Dim stop_time As DateTime = Now      ReportResults(txtRandomNodesVisited, txtRandomTime, _         txtRandomDifference, stop_time.Subtract(start_time))   End Sub

Interesting Improvements
When you pick random solutions, you can’t really expect the result to be very good. These trees can be truly gargantuan and sometimes there are only a few solutions that give optimal results. Often the chance of randomly picking a solution that’s even mediocre is small. While it may be hard to randomly pick a good solution, it is often possible to improve a bad solution until it is relatively respectable.

The following code shows how the BootyDivider program generates random solutions and then tries to improve them. It starts much as the previous code did, by asking you how many trials you want to run. Then for each trial, it generates a random solution.

Once it has a random solution, the code tries randomly swapping items from one person to the other. If a swap improves the solution, the program keeps it. If a swap hurts the solution, the program swaps the item back. For example, suppose Person 1’s loot has a total value of 100 while Person 2’s loot has a value of 120. It would improve the solution to swap an item of value 7 from Person 2 to Person 1, giving new totals of 107 and 113.

The program continues trying random swaps until it fails to find any improvement for several tries in a row. In the example in Listing 1, if there are m_NumItems items then the program tries making improvements until it fails m_NumItems times in a row. You could increase this number to try more swaps before giving up:

Swapping single items from one person’s loot to the other’s can sometimes improve a solution but there are times when swapping a single item isn’t good enough to find the best possible solution. Sometimes you need to swap more than one item between the two totals to make an improvement.

For example, suppose items with values 20 and 40 have been assigned to Person 0 and items with values 30 and 50 have been assigned to Person 1 so their respective totals are 60 and 80 and the difference is 20. Moving an item from Person 0 to Person 1 makes the difference greater, so that won’t help. Moving the item with value 30 from Person 1 to Person 0 changes the totals to 90 and 50, which makes the solution worse?increasing the difference to 40. Similarly, moving the item with value 50 from Person 1 to Person 0 changes the totals to 110 and 30, which makes the solution even worse with a new difference of 80.

However, if you move the item of value 20 from Person 0 to Person 1 and move the item with value 30 from Person 1 to Person 0, you get equal totals of 70. Unfortunately there’s no way to get from the initial solution to the improved one by moving a single item from one person to the other and evaluating after each move.

You can devise more complex improvement strategies that move more than one item at a time but those can get fairly complicated. In some cases it’s faster to try more trials with the simpler improvement strategy than it is to use a more complex strategy.

Hill Climbing
Many heuristics fall into the category of “hill climbing” algorithms. These are called “hill climbing” algorithms because they are similar to an approach a lost hiker can follow at night to find the highest peak nearby. At any given position, the hiker can move uphill. That moves the hiker higher and therefore closer to the highest possible altitude. Of course, the hiker may get stuck on a smaller hill and not reach the highest possible peak, but at least this technique is straightforward.

When searching a decision tree, a hill climbing heuristic should always move closer to a good solution if possible. The BootyDivider program does this by examining the items in the solution one at a time and adding each item to the person who has the smaller total value at any given time.

The following code shows how the program does this. After clearing previous results, the program loops through the items adding each to whichever person has the smaller total value so far.

   ' Add items to the person with the smaller current total.   Private Sub btnAlgHillClimbing_Click( _    ByVal sender As System.Object, ByVal e As System.EventArgs) _    Handles btnAlgHillClimbing.Click      ClearResults(txtHillClimbingNodesVisited, _         txtHillClimbingTime, txtHillClimbingDifference)      Dim start_time As DateTime = Now         ' Make the assignments.      For i As Integer = 0 To m_NumItems - 1         ' See which person has the smaller total.         Dim person As Integer         If m_BestTotalValue(0) < m_BestTotalValue(1) Then            person = 0         Else            person = 1         End If            m_BestAssignedTo(i) = person         m_BestTotalValue(person) += m_ItemValues(i)      Next i      m_BestDifference = _         Abs(m_BestTotalValue(0) - m_BestTotalValue(1))      m_NodesVisited = m_NumItems         Dim stop_time As DateTime = Now      ReportResults(txtHillClimbingNodesVisited, _         txtHillClimbingTime, txtHillClimbingDifference, _         stop_time.Subtract(start_time))   End Sub

This heuristic isn't particularly sophisticated, and is unlikely to produce the best possible result but it is extremely fast, requiring only a single pass through the items. It also often produces a result that is better than selecting the best solution from among a set of randomly chosen solutions.

By thinking about the nature of the problem, you can fine-tune this heuristic to get a much better solution. For example, you can improve the heuristic by simply sorting the items by value before starting and then considering them in order of decreasing value. Initially the algorithm assigns items with large values, so the totals change drastically. Later, the algorithm assigns items with smaller values, so changes to the totals are not as dramatic. The heuristic uses the smaller values to refine the totals to make them closer to each other.

This improved heuristic is still not guaranteed to produce the best possible solution but it often works quite well and is still extremely fast.

Tree Pruning
The final technique described in this article is called branch and bound. The idea is to search the tree much as an exhaustive search does. After moving down a branch in the tree, however, the algorithm finds bounds for the best possible solution that it can achieve by continuing down that branch. If the best possible solution cannot improve on the best solution found so far, the algorithm stops exploring that part of the tree, which can prune off big chunks of the tree and save a lot of searching.

To bound possible solutions, the BootyDivider program tracks the total value of unassigned items. If the current totals for the two people ever differ by so much that adding all the unassigned items to the smaller total will not give an improved solution, the program stops evaluating that solution.

For example, suppose the program previously found a solution where the difference between Person 0's total and Person 1's total is 10. Now suppose the program is considering a partial solution where Person 0 has total value 100, Person 1 has total value 50, and the total value of the unassigned items is 35. If the program assigned all of the remaining items to Person 1, the difference between the two totals would be 15, which is worse than the solution already found with a difference of 10 so there's no point in the program continuing to assign items. If there are a lot of unassigned items, that can trim off a big piece of the tree.

The BootyDivider program's branch and bound code starts much as its exhaustive search does. It warns you if there are a lot of items, resets the solution, and calls a method to recursively assign items to the solution.

The BranchAndBoundAssignItem method in Listing 2 assigns the items. It is similar to the ExhaustiveAssignItem method described earlier except for two changes.

The BranchAndBoundAssignItem method takes a parameter called total_unassigned that tells it the total value of all unassigned items. Then, the code uses that parameter to see if it can improve on the best solution so far. Before it recurses, the method determines whether reducing the current difference by the value of all of the unassigned items will improve the best solution. If doing so cannot improve the solution, the method exits without calling itself recursively.

	?
Figure 3. The Sample Application In Action: The sample BootyDivider program lets you compare different methods for solving the "booty division problem."

Tips for Modeling Problems as Trees
You can model many difficult problems as decision trees. After you figure out how a tree corresponds to the original problem, you can search the tree exhaustively for the best possible solution. When the trees are too large for an exhaustive search to find the best possible solution, using branch and bound can help, but for really big solutions you need to turn to heuristics.

Figure 3 shows the sample BootyDivider program after it has solved a 20-item partition problem using each of the methods described in this article. You can see that both the exhaustive search and the branch and bound approaches found a perfect division, although branch and bound found it much more quickly and visited a much smaller part of the decision tree. Using random solutions, the application found a mediocre solution, while random solutions with improvement found a better solution after examining fewer solutions. Hill climbing found a slightly better solution and sorted hill climbing found a fairly good solution, particularly considering how fast it is. (Note that the results do not always work out this way. Sometimes a random search gets lucky and stumbles across a perfect solution when the other heuristics don't.)

When faced with a truly gigantic decision tree, try the fast heuristics such as hill climbing and sorted hill climbing first to see what kinds of solutions are possible. Then run lots of trials of random and improved random solutions. With a little work, you can write a program that tries new random solutions forever, constantly displaying the best solution it has found so far. When you run out of time or you feel the solution is good enough, you can stop the program and use the best solution it found. You may not find the best solution possible, but you may find one good enough to prevent a mutiny.