The Brelaz Heuristic and Optimal Static Orderings
Research Report 1999.13, School of Computer Studies, University of Leeds,
June 1999.
Barbara M Smith
Abstract
The order in which the variables are assigned can have an enormous impact on
the time taken by a backtracking search algorithm to solve a constraint
satisfaction problem (CSP). The Brelaz heuristic is a dynamic variable
ordering heuristic which has been shown to give good results for some
classes of binary CSPs when the constraint graph is not complete.
Its advantage over the simpler smallest-domain
heuristic is that it uses information about the constraint
graph. This paper uses theoretical work by Nudel to assess the performance
of the Brelaz heuristic.
Nudel's work gives the expected number of nodes at each level of the
search tree when using the forward checking algorithm to find all
solutions to a CSP, given a specified order of the variables.
From this, optimal static orderings are found
for a sample of small binary CSPs. The optimal orderings are used to learn
rules for a static ordering heuristic, which are converted into
modifications to the Brelaz heuristic. The improved heuristic is shown
to halve the mean search cost of solving sparse random binary CSPs with 50
variables, at the phase transition. However, our modifications, and the
Brelaz heuristic itself, are mainly in the form of improved
tie-breakers for the smallest-domain heuristic, which the results suggest is
still the basis of good heuristics for this class of problem.
Back to "Barbara Smith
- Papers on Constraint Programming"