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

Depth-First Solver

This section presents a backtracking solver that finds the best solution to a given problem by performing depth-first traversal of the solution space. Program gif defines the DepthFirstSolver class. The DepthFirstSolver class extends the AbstractSolver class defined in Program gif. It provides an implementation for the search method.

   program32283
Program: DepthFirstSolver class.

The search method does a complete, depth-first traversal of the solution space.gif Note that the implementation does not depend upon the characteristics of the problem being solved. In this sense the solver is a generic, abstract solver and can be used to solve any problem that has a tree-structured solution space!

Since the search method in Program gif visits all the nodes in the solution space, it is essentially a brute-force algorithm. And because the recursive method backs up and then tries different alternatives, it is called a backtracking algorithm.


next up previous contents index

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