Constraint satisfaction problems(CSPs) Standard search problem: state is a "black box"-any data structure that supports successor function,heuristic function,and goal test CSP: state is defined by variables X,with values from domain D goal test is a set of constraints specifying allowable combinations of values for subsets of variables Simple example of a formal representation language 4Feb2004 CS 3243-Constraint Satisfaction 3 4 Feb 2004 CS 3243 - Constraint Satisfaction 3 Constraint satisfaction problems (CSPs) ◼ Standard search problem: ◼ ◼ state is a "black box“ – any data structure that supports successor function, heuristic function, and goal test ◼ ◼ CSP: ◼ ◼ state is defined by variables Xi with values from domain Di ◼ ◼ goal test is a set of constraints specifying allowable combinations of values for subsets of variables ◼ ◼ Simple example of a formal representation language Allows useful general-purpose algorithms with more power