Varieties of CSPs Real-world CSPs Hardware configuration Spreadsheets Continuous variables 8n Transportation schedulng Factory scheduling Floorplanning Notice that Varieties of constraints Standard search formulation(incremental) SA≠rem Let'sththeddumbp thenxi States are defined by the values assigned so far olve pairs of variable Initial state:the empty asigment. Goal test:the currentassignment is complete 男 with n variables Example:Cryptarithmetic Backtracking search T WO T WO FOUR Can solve n-queens forVarieties of CSPs Discrete variables finite domains; 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 ♦ linear constraints solvable, nonlinear undecidable Continuous variables ♦ e.g., start/end times for Hubble Telescope observations ♦ linear constraints solvable in poly time by LP methods Chapter 5 7 Varieties of constraints Unary constraints involve a single variable, e.g., SA 6= green Binary constraints involve pairs of variables, e.g., SA 6= WA Higher-order constraints involve 3 or more variables, e.g., cryptarithmetic column constraints Preferences (soft constraints), e.g., red is better than green often representable by a cost for each variable assignment → constrained optimization problems Chapter 5 8 Example: Cryptarithmetic F T U W R O + T W O T W O F O U R X3 X2 X1 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, etc. Chapter 5 9 Real-world CSPs Assignment problems e.g., who teaches what class Timetabling problems e.g., which class is offered when and where? Hardware configuration Spreadsheets Transportation scheduling Factory scheduling Floorplanning Notice that many real-world problems involve real-valued variables Chapter 5 10 Standard search formulation (incremental) Let’s start with the straightforward, dumb approach, then fix it States are defined by the values assigned so far ♦ Initial state: the empty assignment, { } ♦ Successor function: assign a value to an unassigned variable that does not conflict with current assignment. ⇒ fail if no legal assignments (not fixable!) ♦ Goal test: the current assignment is complete 1) This is the same for all CSPs! 2) Every solution appears at depth n with n variables ⇒ use depth-first search 3) Path is irrelevant, so can also use complete-state formulation 4) b = (n − `)d at depth `, hence n!d n leaves!!!! Chapter 5 11 Backtracking search Variable assignments are commutative, i.e., [WA = red then NT = green] same as [NT = green then WA = red] Only need to consider assignments to a single variable at each node ⇒ b = d and there are d n leaves Depth-first search for CSPs with single-variable assignments is called backtracking search Backtracking search is the basic uninformed algorithm for CSPs Can solve n-queens for n ≈ 25 Chapter 5 12