Example:Map-Coloring CONSTRAINT SATISFACTION PROBLEMS CHAPTER 5 Variables WA.V7.Q.NsW.V.A.T Con must have diffe I.blue).(green,red).(green.blue).... Outline Example:Map-Coloring conto ◇CSP examples Problem structure and problem decompositior Local search for CSPs Constraint satisfaction problems(CSPs) Constraint graph Binary CSP: Constraint grap:nodes are variables.ars shoonrint CSP: (】 Simple example of formal representation language ⊙ Spp2SPETmnwipobal 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 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 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. 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 Constraint graph Binary CSP: each constraint relates at most two variables Constraint graph: nodes are variables, arcs show constraints Victoria WA NT SA Q NSW V T General-purpose CSP algorithms use the graph structure to speed up search. E.g., Tasmania is an independent subproblem! Chapter 5 6