Representing the Solution Space

This section presents an abstract base class for representing the nodes of a solution space. By defining an abstract interface, it is possible to 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 abstract class called Solution. The Solution class is intended to serve as the base class from which problem-specific classes are derived. Each Solution instance represents a single node in the solution space.

  
Program: Solution Class Definition

The Solution class is derived from the Object base class. Consequently, instances of the Solution class can be inserted in the various containers discussed in the preceding chapters. The Solution class adds the following functions to the inherited interface:

IsFeasible

This function 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 function returns true if the solution instance represents a complete solution. A solution is complete when all possible decisions have been made.

Objective

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

Bound

This function 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 for to facilitate the implementation of branch-and-bound backtracking which is described in Section .

Clone

This function is used to clone the given solution instance. It returns a reference to another, dynamically allocated solution that is identical to the given solution instance.

Successors

This function returns an iterator that enumerates all of the successors (i.e., the children) of the given solution instance. It is assumed that this iterator creates the children of the given node dynamically.

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