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 ◼
Constraint graph Binary CSP:each constraint relates two variables Constraint gra :s are constraints NT WA SA NS W 4Feb2004 CS 3243-Constraint Satisfaction 6
4 Feb 2004 CS 3243 - Constraint Satisfaction 6 Constraint graph ◼ Binary CSP: each constraint relates two variables ◼ ◼ Constraint graph: nodes are variables, arcs are constraints ◼
Varieties of CSPs Discrete variables finite domains: n variables,domain size d)complete assignments e.g.,Boolean CSPs,incl.~Boolean satisfiability (NP-complete) infinite domains: integers,strings,etc. e.g.job scheduling,variables are start/end days for each job need a constraint language,e.g.,Startob,+5s StartJoba Continuous variables ■ e.g.,start/end times for Hubble Space Telescope observations linear constraints solvable in polynomial time by linear programming 4Feb2004 CS 3243-Constraint Satisfaction 7
4 Feb 2004 CS 3243 - Constraint Satisfaction 7 Varieties of CSPs ◼ Discrete variables ◼ ◼ finite domains: ◼ n variables, domain size d → O(d n ) complete assignments ◼ e.g., Boolean CSPs, incl.~Boolean satisfiability (NP-complete) ◼ infinite domains: ◼ integers, strings, etc. ◼ e.g., job scheduling, variables are start/end days for each job ◼ need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3 ◼ Continuous variables ◼ ◼ e.g., start/end times for Hubble Space Telescope observations ◼ linear constraints solvable in polynomial time by linear programming
Varieties of constraints Unary constraints involve a single variable, ■e.g,SA+green Binary constraints involve pairs of variables, ▣e.g,SA+WA Higher-order constraints involve 3 or more variables, 4Feb2g,cryptarithretis olmssonsraints P
4 Feb 2004 CS 3243 - Constraint Satisfaction 8 Varieties of constraints ◼ Unary constraints involve a single variable, ◼ e.g., SA ≠ green ◼ ◼ Binary constraints involve pairs of variables, ◼ e.g., SA ≠ WA ◼ ◼ Higher-order constraints involve 3 or more variables, ◼ e.g., cryptarithmetic column constraints ◼
Example:Cryptarithmetic T WO +T WO FOUR o Variables:FTUW ROXXX3 ■Domains:{01,2,3,456☑8，y Constraints:Alldiff (FTU,WR,O) ◆ 0+0=R+10·X ■X+W+W=U+10:X2 4 Feb 2002=24Constraint Satisfaction 9 FT0厂0
4 Feb 2004 CS 3243 - Constraint Satisfaction 9 Example: Cryptarithmetic ◼ Variables: F T U W R O X1 X2 X3 ◼ Domains: {0,1,2,3,4,5,6,7,8,9} ◼ Constraints: Alldiff (F,T,U,W,R,O) ◼ ◼ O + O = R + 10 ·X1 ◼ ◼ X1 + W + W = U + 10 ·X2 ◼ ◼ X2 + T + T = O + 10 ·X3 ◼ X3 = F, T ≠ 0, F ≠ 0
Real-world CSPs Assignment problems e.g.,who teaches what class Timetabling problems ◆ e.g.,which class is offered when and where? Transportation scheduling o Factory scheduling FeNetice that mamy sreafowerletiproblems involve real-10
4 Feb 2004 CS 3243 - Constraint Satisfaction 10 Real-world CSPs ◼ Assignment problems ◼ e.g., who teaches what class ◼ ◼ Timetabling problems ◼ ◼ e.g., which class is offered when and where? ◼ ◼ Transportation scheduling ◼ ◼ Factory scheduling ◼ ◼ Notice that many real-world problems involve realvalued variables