Forward checking

From Glossary

Jump to: navigation, search

Forward checking is a propagation procedure that guarantees that at each step of the search, all the constraints between already assigned variables and not yet assigned variables are arc consistent.

Formally, let LaTeX:  N = (X, D, C) be a binary constraint network and LaTeX:  Y \subseteq X such that LaTeX:  |D(x_i)| = 1 for all LaTeX:  x_i \in Y. LaTeX: N is forward checking consistent according to the instantiation LaTeX: I on LaTeX: Y iff LaTeX: I is locally consistent and for all LaTeX: x_i \in Y, for all LaTeX: x_j \in X \setminus Y, for all LaTeX: c(x_i, x_j) \in C, LaTeX: c(x_i, x_j) is arc consistent.

Personal tools