Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Constraint Networks

Keywords: Adaptive Consistency, Cycle Cutset, Tree Clustering, backjumping, backtracking

Categories: Knowledge Representation

Author(s): Rina Dechter

Constraint networks offer a graphical representation of Constraint Satisfaction problems that can be used to control search efficiently. A constraint network is a graph (or hypergraph) in which nodes represent variables and arcs represent pairs (or sets) of variables which are included in a common constraint. The topology of this network uncovers opportunities for problem decomposition techniques and provides estimates of the problem complexity prior to actually performing the search. The following are typical network-based techniques.

Other graph-based techniques include backjumping, an improvement on backtracking where, at a dead-end situation, the algorithm retracts to the most recent node connected to the dead-end variable (also see Dependency Directed Backtracking), and decomposition to a tree of connected components where the connected components in the constraint graph are solved first and an overall solution is assembled using a linear tree algorithm.



Add Comment

No comments.