Fail first principle

From Glossary

Jump to: navigation, search

The fail first principle is an idea of what a variable ordering heuristic should attempt to do in tree search. It suggests that the variable to be assigned next should be the one which is most likely to lead to a dead-end. The heuristic aims at proving that the search is in a sub-tree with no feasible solutions as soon as possible.

One way of operationalizing this principle, is to choose the next variable to assigned to be the variable which is the most constrained. The extent to which a variable is constrained can be measured in different ways. One simple measure being the current size of the domain. Under this measure, the variable which has the smallest domain should be assigned next. Another common measure is to select the variable that appears in the largest number of constraints. More sophisticated estimates exist.

variable ordering heuristicbutton.png

The variable ordering heuristic is part of the search strategy and specifies in what order variables are branched on during tree search. For instance, a popular, simple heuristic is to pick the variable with the smallest domain first following the fail first principle.

A variable ordering heuristic is more commonly called a branching rule in branch-and-bound search.

See also value ordering heuristic.

Personal tools