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 likelybut not guaranteedto 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) _
' 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
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)
' See if the test solution is an improvement.
If ShortCircuit() Then Exit For
Dim stop_time As DateTime = Now
ReportResults(txtRandomNodesVisited, txtRandomTime, _
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 worseincreasing 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.