Constraint Satisfaction Problem

from Wikipedia, the free encyclopedia

A constraint satisfaction problem ( CSP ; German: Conditional fulfillment problem ) is a task from artificial intelligence and operations research . The task is to find a state (i.e. assignments of variables) that fulfills all the conditions ( constraints ) set up.

A constraint satisfaction problem consists of a set of variables, their ranges of values ​​and the conditions that create links between the variables and thereby determine which combinations of values ​​of the variable are permissible. In this way, a variety of problems from computer science, mathematics and other areas of application can be formulated. Simple examples of such problems are the queens problem , the four-color problem , Sudoku , Str8ts or the satisfiability problem of propositional logic . In elementary mathematics, this corresponds to solving an equation or a system of equations - constraint satisfaction problems are specifically those questions that cannot be solved analytically, or only at great expense.

A CSP is solved by finding an assignment of the variable that meets all conditions. In contrast to other optimization problems , in which the “best possible” solution is sought, constraint satisfaction problems require the complete fulfillment of every single precondition. If the established conditions are contradictory , there is no solution to the problem (or vice versa: if there is demonstrably no solution, the preconditions are proven to be incompatible). However, there can be several or many solutions. If there is only one, one speaks of a "clear solution", as with other optimization questions.

Constraint satisfaction problems are divided into different types of constraints or conditions:

  • unary conditions (conditions that control the value of a single variable)
  • binary conditions (links between two variables)
  • Higher-order conditions (links comprising three or more variables)

Various approaches are combined to solve constraint satisfaction problems:

  • From existing conditions, new conditions are calculated, which limit the range of values of variables in addition to or lead to a contradiction ( condition reproduction , Eng. Constraint propagation ).
  • A solution is systematically searched for in the solution space of the variables.

In principle, general search algorithms can be used to solve CSPs. However, the peculiarity of the problem class allows algorithms that work a lot more efficiently than general search algorithms.

  • States are defined by the values ​​of variables.
  • Operators assign a value to a variable.
  • The target test is specified by conditions that the variable assignments must meet.
  • A target state is an assignment of the variables with values ​​that meet all conditions.

Examples of algorithms that are particularly suitable for solving constraint satisfaction problems are the AC-3 algorithm , backtracking or the min-conflict heuristic .

literature

  • Krzysztof Apt; Principles of constraint programming. Cambridge University Press, 2003, ISBN 0-521-82583-0 .
  • Rina Dechter: Constraint processing. Morgan Kaufmann, 2003, ISBN 1-55860-890-7 .
  • Christophe Lecoutre: Constraint Networks: Techniques and Algorithms. ISTE / Wiley, 2009, ISBN 978-1-84821-106-3 .
  • David Poole, Alan Mackworth: Artificial Intelligence: Foundations of Computational Agents . Cambridge University Press, 2010; Chapter 4.2.2 Constraint Satisfaction Problems (online, artint.info).