Chapter 3: Constraint satisfaction problems presents about What is a CSP? Posing a CSP; Generate-and-test-algorithms; Standard backtracking algorithm; Consistency algorithm; Look-ahead Schemes and somethings else. | Chapter 3 CONSTRAINT SATISFACTION PROBLEMS Outline What is a CSP? Posing a CSP Generate-and-test-algorithms Standard backtracking algorithm Consistency algorithm Look-ahead Schemes What is a CSP? In constraint satisfaction problems (CSPs), we are given a set of variables, a domain for each variable, and a set of constraints. Each constraint is defined over some subset of the original set of variables and limits the combinations of values that the variables in this subset can take. The goal is to find one assignment to the variables such that the assignment satisfies all the constraints. CSPs can be divided into two main classes: Satisfiability problems, where the goal is to find an assignment of values to variables that satisfies some constraints. An assign-ment of values to variables either satisfies the constraints or not. Optimization problems, where each assignment of a value to each variable has a cost or an objective value associated with it. The goal is to find an . | Chapter 3 CONSTRAINT SATISFACTION PROBLEMS Outline What is a CSP? Posing a CSP Generate-and-test-algorithms Standard backtracking algorithm Consistency algorithm Look-ahead Schemes What is a CSP? In constraint satisfaction problems (CSPs), we are given a set of variables, a domain for each variable, and a set of constraints. Each constraint is defined over some subset of the original set of variables and limits the combinations of values that the variables in this subset can take. The goal is to find one assignment to the variables such that the assignment satisfies all the constraints. CSPs can be divided into two main classes: Satisfiability problems, where the goal is to find an assignment of values to variables that satisfies some constraints. An assign-ment of values to variables either satisfies the constraints or not. Optimization problems, where each assignment of a value to each variable has a cost or an objective value associated with it. The goal is to find an assignment with the least cost or with the highest objective value. This is called the optimal assignment. The constraints of satisfiability problems, which must be met, are called hard constraints. The costs in optimization problems, which specify preferences rather than what has to be met, are called soft constraints. 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 - scheduling - temporal reasoning - floor plan design. - diagnosis of analog circuit - financial planning - constraint-based engineering design POSING A CONSTRAINT SATISFACTION PROBLEM A CSP is characterized by a set of variables V1, V2, ,Vn. Each variable Vi has an associated domain Dvi of possible values. For satisfiability problems, there are constraint relations on various subsets of the variables which give legal combinations of values for these variables. These constraints can be .
