Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Abstract Backtracking Solvers

The usual way to implement a backtracking algorithm is to write a function or procedure which traverses the solution space. This section presents an alternate, object-oriented approach that is based on the notion of an abstract solver  .

Think of a solver as an abstract machine, the sole purpose of which is to search a given solution space for the best possible solution. A machine is an object. Therefore, it makes sense that we represent it as an instance of some class.

Program gif declares the abstract class Solver. The public interface of this class consists of the single function Solve. This function takes as its lone argument a reference to a Solution instance that is the node in the solution space from which to begin the search. The Solve function returns a reference to the to the best solution found.

   program32665
Program: Solver Class Definition

Program gif also declares two protected member variables, bestSolution and bestObjective, and two protected member functions, UpdateBest and DoSolve. Since DoSolve is a pure virtual function, its implementation must be given in a derived class. Program gif gives the implementations for Solve and UpdateBest.

   program32687
Program: Solver Class Solve and UpdateBest Member Function Definitions

The Solve function does not search the solution space itself. It is the DoSolve routine, which is provided by a derived class, that does the actual searching. The Solve routine merely sets things up for DoSolve. When DoSolve returns it is expected that the bestSolution variable will point to the best solution and that bestObjective will be the value of the objective function for the best solution. In this case, it is assumed that the goal is to minimize the objective function.

The UpdateBest function is meant to be called by the DoSolve routine as it explores the solution space. As each complete solution is encountered, the UpdateBest routine is called to keep track of the solution which minimizes the objective function.




next up previous contents index

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