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

Breadth-First Solver

If we can find the optimal solution by doing a depth-first traversal of the solution space, then we can find the solution with a breadth-first traversal too. As defined in Section gif, a breadth-first traversal of a tree visits the nodes in the order of their depth in the tree. That is, first the root is visited, then the children of the root are visited, then the grandchildren are visited, and so on.

The BreadthFirstSolver class is defined in Program gif. The BreadthFirstSolver class extends the AbstractSolver class defined in Program gif. It simply provides an implementation for the search method.

   program32309
Program: BreadthFirstSolver class.

The search method implements a non-recursive, breadth-first traversal algorithm that uses a queue to keep track of nodes to be visited. The initial solution is enqueued first. Then the following steps are repeated until the queue is empty:

  1. Dequeue the first solution in the queue.
  2. If the solution is complete, call the updateBest method to keep track of the solution which minimizes the objective function.
  3. Otherwise the solution is not complete. Enqueue all its successors.
Clearly, this algorithm does a complete traversal of the solution space.gif


next up previous contents index

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