|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
The usual way to implement a backtracking algorithm is to write a method 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 
defines the Solver class.
The abstract Solver class
extends the abstract Object class
introduced in Program .
The Solver class contains two instance attributes,
_bestSolution and _bestObjective,
two concrete methods,
updateBest and solve
and the abstract method search.
Since search is an abstract method,
its implementation must be given in a derived class.
Program: Abstract Solver class.
The purpose of the solve method is to solve the problem by conducting a search of the solution space. In addition to self, this method takes as its argument an instance of a class derived from Solution that is the node in the solution space from which to begin the search. The solve method returns the to the best solution found.
The solve method does not search the solution space itself--it merely sets things up for the search method. It is the search method, which is provided by a derived class, that does the actual searching. When search returns it is expected that the _bestSolution instance attribute will refer to the best solution and that _bestObjective will be the value of the objective function for the best solution.
The updateBest method is meant to be called by the search method as it explores the solution space. As each complete solution is encountered, the updateBest method is called to keep track of the solution which minimizes the objective function.
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.