CONSTRAINT SATISFACTION PROBLEMS CHAPTER 5 Chapter 5 1
Constraint Satisfaction Problems Chapter 5 Chapter 5 1
Outline ◇CSP examples Backtracking search for CSPs Problem structure and problem decomposition ◇Local search for CSPs Chapter 5 2
Outline ♦ CSP examples ♦ Backtracking search for CSPs ♦ Problem structure and problem decomposition ♦ Local search for CSPs Chapter 5 2
Constraint satisfaction problems (CSPs) Standard search problem: state is a "black box"-any old data structure that supports goal test,eval,successor 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 than standard search algorithms Chapter 5 3
Constraint satisfaction problems (CSPs) Standard search problem: state is a “black box”—any old data structure that supports goal test, eval, successor 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 than standard search algorithms Chapter 5 3
Example:Map-Coloring Northern Territory Western Queensland Australia South Australia New South Wales Victoria Variables WA,NT,Q,NSW,V,SA,T Tasmania Domains Di={red,green,blue} Constraints:adjacent regions must have different colors e.g.,WA NT (if the language allows this),or (WA,NT){(red,green),(red,blue),(green,red),(green,blue),...} Chapter 5 4
Example: Map-Coloring Western Australia Northern Territory South Australia Queensland New South Wales Victoria Tasmania Variables WA, NT, Q, NSW, V , SA, T Domains Di = {red, green, blue} Constraints: adjacent regions must have different colors e.g., WA 6= NT (if the language allows this), or (WA, NT) ∈ {(red, green),(red, blue),(green, red),(green, blue), . . .} Chapter 5 4
Example:Map-Coloring contd. Northern Territory Western Queensland Australia South Australia New South Wales /ictoria Tas Solutions are assignments satisfying all constraints,e.g., {WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green} Chapter 5 5
Example: Map-Coloring contd. Western Australia Northern Territory South Australia Queensland New South Wales Victoria Tasmania Solutions are assignments satisfying all constraints, e.g., {WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green} Chapter 5 5