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.


domainbutton.png

The domain of a variable is a set of all possible values that can be assigned to the variable. When the domain contains numbers only, the variables are called numerical variables. The domain of a numerical variable may be further restricted to integers, rational numbers or real numbers. When the domain contains boolean values only, the variables are called boolean variables. When the domain contains an enumerated type of objects, the variables are called symbolic variables (e.g. a variable that represents a day of the week).

A common propagation technique in constraint programming is to dynamically remove values from the domain of a variable when it can be inferred that the value does not belong to any solution given the set of variable assignments that have already been made. See


Views
Personal tools