Representing the Solution Space

This section presents an interface for the nodes of a solution space. By using an interface, we hide the details of the specific problem to be solved from the backtracking algorithm. In so doing, it is possible to implement completely generic backtracking problem solvers.

Although a backtracking algorithm behaves as if it is traversing a solution tree, it is important to realize that it is not necessary to have the entire solution tree constructed at once. Instead, the backtracking algorithm creates and destroys the nodes dynamically as it explores the solution space.

Program  defines the Solution interface. The Solution interface extends the Comparable interface defined in Program  and it extends the Cloneable interface defined in java.lang. Each instance of a class that implements the Solution interface represents a single node in the solution space.

  
Program: Solution interface.

The Solution interface extends the Comparable interface. Consequently, instances of the Solution class can be inserted in the various containers discussed in the preceding chapters. The Solution interface adds the following methods:

isFeasible

This method returns true if the solution instance is a feasible solution to the given problem. A solution is feasible if it satisfies the problem constraints.

isComplete

This method returns true if the solution instance represents a complete solution. A solution is complete when all possible decisions have been made.

getObjective

This method returns the value of the objective function for the given solution instance.

getBound

This method returns a value that is a lower bound (if it exists) on the objective function for the given solution instance as well as all the solutions that can possibly be derived from that instance. This is a hook provided to facilitate the implementation of branch-and-bound backtracking which is described in Section .

getSuccessors

This method returns an Enumeration that enumerates all of the successors (i.e., the children) of the given solution instance. It is assumed that the children of the given node are created dynamically.

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