Constraint Satisfaction Problems Chapter 5 Section 1 -3 4Feb2004 CS 3243-Constraint Satisfaction 1
4 Feb 2004 CS 3243 - Constraint Satisfaction 1 Constraint Satisfaction Problems Chapter 5 Section 1 – 3
Outline Constraint Satisfaction Problems(CSP) Backtracking search for CSPs Local search for CSPs 4Feb2004 CS 3243-Constraint Satisfaction 2
4 Feb 2004 CS 3243 - Constraint Satisfaction 2 Outline ◼ Constraint Satisfaction Problems (CSP) ◼ Backtracking search for CSPs ◼ Local search for CSPs
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
Example:Map-Coloring Queensland South Australia New South Wale Victoria Variables WA,NT Q NSW V SA,T Tasmania Domains D={red,green,blue} Constraints:adjacent regions must have different colors e.g.,WA NT or (WA NT)in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green) 4Feb2004 CS 3243-Constraint Satisfaction 4
4 Feb 2004 CS 3243 - Constraint Satisfaction 4 Example: Map-Coloring ◼ Variables WA, NT, Q, NSW, V, SA, T ◼ Domains Di = {red,green,blue} ◼ Constraints: adjacent regions must have different colors ◼ ◼ e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)} ◼
Example:Map-Coloring Northern Territory Queenslan New South Wa Tasmani Solutions are complete and consistent assignments, e.g.,WA red,NT green,Q red,NSW green,V red,SA blue,T green 口 4Feb2004 CS 3243-Constraint Satisfaction 5
4 Feb 2004 CS 3243 - Constraint Satisfaction 5 Example: Map-Coloring ◼ Solutions are complete and consistent assignments, e.g., WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green ◼