Brandeis CS 101A - Lecture for Chapter 5 (40 pages)

Previewing pages 1, 2, 3, 19, 20, 38, 39, 40 of 40 page document View the full content.
View Full Document

Lecture for Chapter 5



Previewing pages 1, 2, 3, 19, 20, 38, 39, 40 of actual document.

View the full content.
View Full Document
View Full Document

Lecture for Chapter 5

94 views

Lecture Notes


Pages:
40
School:
Brandeis University
Course:
Cs 101a - Artificial Intelligence

Unformatted text preview:

Constraint Satisfaction Problems CS101 FALL 2007 Lecture for Chapter 5 Constraint 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 Cryptography 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 So WA NT must be in red green red blue green red 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 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 programming Varieties of constraints Unary constraints involve a single variable e g SA green Binary



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?