DOC PREVIEW
Brandeis CS 101A - Lecture for Chapter 5

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Constraint Satisfaction ProblemsConstraint satisfaction problemsSlide 3Example: Map-ColoringSlide 5Constraint graphVarieties of CSPsVarieties of constraintsExample: CryptarithmeticCSP as a standard search problemCSP as a standard search problem IIBacktracking searchSlide 13Backtracking exampleSlide 15Slide 16Slide 17Improving backtracking efficiencyMost constrained variableMost constraining variableLeast constraining valueForward checking (“edge consistency” is a variant)Forward checkingSlide 24Slide 25Example: 4-Queens ProblemSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37PowerPoint PresentationExample: n-queens and AC-3Real-world CSPsConstraint Satisfaction ProblemsCS101FALL 2007Lecture for Chapter 5Constraint satisfaction problems•What is a CSP?–Finite set of variables V1, V2, …, Vn–Finite set of constraints C1, C2, …, Cm–Nonempty domain of possible values for each variable DV1, DV2, … DVn–Each constraint Ci limits the values that variables can take, e.g., V1 ≠ V2•A state is defined as an assignment of values to some or all variables.•Consistent assignment: assignment does not violate the constraints.Constraint satisfaction problems•An assignment is complete when every value is mentioned. •A solution to a CSP is a complete assignment that satisfies all constraints.•Some CSPs require a solution that maximizes an objective function. •Applications: –Scheduling the Hubble Space Telescope, –Floor planning for VLSI, –Map coloring, –CryptographyExample: 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•So (WA,NT) must be in {(red,green),(red,blue),(green,red), …}Example: Map-ColoringSolutions 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 graph: –nodes are variables–arcs are constraints•CSP benefits–Standard representation pattern–Generic goal and successor functions–Generic heuristics (no domain specific expertise).•Graph can be used to simplify search.•e.g. Tasmania is an independent subproblem.Varieties of CSPs•Discrete variables–finite domains:•n variables, domain size d  O(dn) complete assignments•e.g., Boolean CSPs, includes 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 programmingVarieties 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•Preference (soft constraints) e.g. red is better than green can be represented by a cost for each variable assignment –Constrained optimization problems.Example: Cryptarithmetic•Variables: F T U W R O X1 X2 X3•Domain: {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 ≠ 0CSP as a standard search problem•A CSP can be easily expressed as a standard search problem.–Initial State: the empty assignment {}.–Successor function: Assign value to unassigned variable provided that there is not conflict.–Goal test: the current assignment is complete.–Path cost: as constant cost for every step.CSP as a standard search problem II•This is the same for all CSP’s !!!•Solution is found at depth n , for n variables–Hence depth first search can be used•Path is irrelevant, so complete state representation can also be used•Branching factor b at the top level is nd•b=(n-l)d at depth l, hence n!dn leaves (only dn complete assignments)Backtracking search•Variable assignments are commutative, –Eg [ WA = red then NT = green ] equivalent to [ NT = green then WA = red ]•Only need to consider assignments to a single variable at each node b = d and there are dn 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–Backtracking searchfunction BACKTRACKING-SEARCH(csp) return a solution or failurereturn RECURSIVE-BACKTRACKING({} , csp)function RECURSIVE-BACKTRACKING(assignment, csp) return a solution or failureif assignment is complete then return assignmentvar  SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) doif value is consistent with assignment according to CONSTRAINTS[csp] thenadd {var=value} to assignment result  RECURSIVE-BACTRACKING(assignment, csp)if result  failure then return resultremove {var=value} from assignmentreturn failureBacktracking exampleBacktracking exampleBacktracking exampleBacktracking exampleImproving backtracking efficiency•General-purpose methods can give huge gains in speed:–Which variable should be assigned next?–In what order should its values be tried?–Can we detect inevitable failure early?Most constrained variable•Most constrained variable:choose the variable with the fewest legal values•a.k.a. minimum remaining values (MRV) heuristicMost constraining variable•Tie-breaker among most constrained variables•Most constraining variable:–choose the variable with the most constraints on remaining variablesLeast constraining value•Given a variable, choose the least constraining value:–the one that rules out the fewest values in the remaining variables•Combining these heuristics makes 1000 queens feasibleForward checking (“edge consistency” is a variant)•Idea: –Keep track of remaining legal values for unassigned variables–Terminate search when any variable has no legal valuesForward checking•Idea: –Keep track of remaining legal values for unassigned variables–Terminate search when any variable has no legal valuesForward checking•Idea: –Keep track of remaining legal values for unassigned variables–Terminate search when any variable has no legal


View Full Document

Brandeis CS 101A - Lecture for Chapter 5

Download Lecture for Chapter 5
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture for Chapter 5 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture for Chapter 5 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?