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) _
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
person = 1
m_BestAssignedTo(i) = person
m_BestTotalValue(person) += m_ItemValues(i)
m_BestDifference = _
Abs(m_BestTotalValue(0) - m_BestTotalValue(1))
m_NodesVisited = m_NumItems
Dim stop_time As DateTime = Now
txtHillClimbingTime, txtHillClimbingDifference, _
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.
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.
method in Listing 2
assigns the items. It is similar to the ExhaustiveAssignItem
method described earlier except for two changes.
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.
Tips for Modeling Problems as Trees
|Figure 3. The Sample Application In Action: The sample BootyDivider program lets you compare different methods for solving the "booty division problem."|
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.
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.