Constraint-Satisfaction-Problem

A Constraint Satisfaction Problem (CSP; German: Constraint Satisfaction Problem ) is a task of artificial intelligence and from the Operations Research. Task is to find a state ( ie assignments of variables ) that meets all the established conditions ( constraints ). Examples of such problems are the queens problem, the four- color problem, Sudoku, Str8ts or the satisfiability of propositional logic.

A Constraint Satisfaction Problem consists of a set of variables, their value ranges and the conditions that create links between the variables and thereby determine which combinations of values ​​of the variables are allowed. In this way, a variety of problems in computer science, mathematics and other areas of application can be formulated. A CSP is solved by an assignment of the variables is found which satisfies all conditions. Are the conditions set contradictory, so there is no solution to the problem.

Constraint Satisfaction Problems are divided into various restriction or condition types:

  • Unary conditions ( conditions that control the value of a single variable)
  • Binary conditions (relationships between two variables )
  • Higher order terms ( links that include three or more variables )

To solve Constraint Satisfaction Problems, various approaches are combined:

  • New terms from existing conditions calculated that restrict the range of values ​​of variables in addition to or lead to a contradiction ( reproductive condition, engl. Constraint propagation).
  • The solution space of the variables is systematically searched for a solution.

Basically, general search algorithms can be used for solving CSPs. However, the specificity of the problem class algorithms allows to operate more efficiently by some as a general search algorithms.

  • States are defined by values ​​of variables.
  • Operators occupy a variable with a value.
  • The goal test is specified by conditions which must satisfy the variable assignments.
  • A goal state is an assignment of the variables with values ​​that satisfy 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.

  • Artificial intelligence
  • Optimization
Constraint (mathematics)
111610
de