Algorithms for Constraint-Satisfaction Problems: A Survey

Vipin Kumar

Abstract


A large number of problems in AI and other areas of computer science can be viewed as special cases of the constraint-satisfaction problem. Some examples are machine vision, belief maintenance, scheduling, temporal reasoning, graph problems, floor plan design, the planning of genetic experiments, and the satisfiability problem. A number of different approaches have been developed for solving these problems. Some of them use constraint propagation to simplify the original problem. Others use backtracking to directly search for possible solutions. Some are a combination of these two techniques. This article overviews many of these approaches in a tutorial fashion.

Full Text:

PDF


DOI: http://dx.doi.org/10.1609/aimag.v13i1.976

Copyright © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.