Data Structures and Algorithms
with Object-Oriented Design Patterns in C#
     |
|
This section presents an interface for the nodes of a solution space.
By using an interface,
we 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 Solution interface.
Each instance of a class that implements the
Solution interface represents a single node
in the solution space.
Program: Solution interface.
The Solution interface comprises the following properties:
- IsFeasible
-
This get accessor 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 get accessor returns true if the solution instance
represents a complete solution.
A solution is complete when all possible decisions have been made.
- Objective
-
This get accessor returns the value of the objective function
for the given solution instance.
- Bound
-
This get accessor 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 to facilitate the implementation
of branch-and-bound backtracking which is described
in Section .
- Successors
-
This get accessor returns an IEnumerable
object that represents all of the successors (i.e., the children)
of the given solution instance.
It is assumed that the children of the given
node are created dynamically.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.