Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Example-Balancing Scales

 

Consider the set of scales  shown in Figure gif. Suppose we are given a collection of n weights, tex2html_wrap_inline67201, and we are required to place all of the weights onto the scales so that they are balanced.

   figure31926
Figure: A set of scales.

The problem can be expressed mathematically as follows: Let tex2html_wrap_inline67195 represent the pan in which weight tex2html_wrap_inline67185 is placed such that

displaymath67221

The scales are balanced when the sum of the weights in the left pan equals the sum of the weights in the right pan,

displaymath67222

Given an arbitrary set of n weights, there is no guarantee that a solution to the problem exists. A solution always exists if, instead of balancing the scales, the goal is to minimize the difference between between the total weights in the left and right pans. Thus, given tex2html_wrap_inline67201, our objective is to minimize tex2html_wrap_inline67243 where

displaymath67223

subject to the constraint that all the weights are placed on the scales.

Given a set of scales and collection of weights, we might solve the problem by trial-and-error: Place all the weights onto the pans one-by-one. If the scales balance, a solution has been found. If not, remove some number of the weights and place them back on the scales in some other combination. In effect, we search for a solution to the problem by first trying one solution and then backing-up to try another.

Figure gif shows the solution space  for the scales balancing problem. In this case the solution space takes the form of a tree: Each node of the tree represents a partial solution to the problem. At the root (node A) no weights have been placed yet and the scales are balanced. Let tex2html_wrap_inline67243 be the difference between the the sum of the weights currently placed in the left and right pans. Therefore, tex2html_wrap_inline67247 at node A.

   figure31974
Figure: Solution space for the scales balancing problem.

Node B represents the situation in which weight tex2html_wrap_inline67307 has been placed in the left pan. The difference between the pans is tex2html_wrap_inline67309. Conversely, node C represents the situation in which the weight tex2html_wrap_inline67307 has been placed in the right pan. In this case tex2html_wrap_inline67313. The complete solution tree has depth n and tex2html_wrap_inline59778 leaves. Clearly, the solution is the leaf node having the smallest tex2html_wrap_inline67319 value.

In this case (as in many others) the solution space is a tree. In order to find the best solution a backtracking algorithm visits all the nodes in the solution space. That is, it does a tree traversal . Section gif presents the two most important tree traversals--depth-first  and breadth-first . Both kinds can be used to implement a backtracking algorithm.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.