UI CS 4420 - Constraint Satisfaction (11 pages)

Previewing pages 1, 2, 3, 4 of 11 page document View the full content.
View Full Document

Constraint Satisfaction



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Constraint Satisfaction

15 views


Pages:
11
School:
University of Iowa
Course:
Cs 4420 - Artificial Intelligence

Unformatted text preview:

SEND MORE MONEY Constraint Satisfaction constraints c1 S E N D M O R Y c2 S E N D M O R Y 1000 S 1000 M 10000 M 1000 O holds Reading Russell Norvig Chapter 5 Kumar Algorithms for constraint satisfaction problems A survey 1 View a problem as a set of variables to which we have to assign values that satisfy a number of problem specific constraints Constraint programming CSPs constraint logic programming Assign distinct digits to the letters S E N D M O R Y such that S E N D M O R E Solution 9 5 6 7 1 0 8 5 M O N E Y 1 0 6 5 2 Algorithms for CSPs Backtracking systematic search Constraint propagation k consistency Variable ordering heuristics Backjumping and dependency directed backtracking 0 100 E 100 O 100 N S Y 9 10 N D 10 R E 10 E Y 7 A Model for MONEY continued SEND MORE MONEY Constraint Processing offers a powerful problem solving paradigm 8 8 4 Overview A Model for MONEY number of variables 8 Assign distinct digits to the letters S E N D M O R Y such that S E N D M O R E M O N E Y more constraints c3 S E N D M O R Y 8 S 0 c4 S E N D M O R Y 8 M 0 c5 S E N D M O R Y 8 S Y all different holds 2 Informal Definition of CSP 5 Solution for MONEY Modeling CSP Constraint Satisfaction Problem Given 1 a finite set of variables 2 each with a domain of possible values often finite 3 a set of constraints that limit the values the variables can take on A solution is an assignment of a value to each variable such that the constraints are all satisfied Tasks might be to decide if a solution exists to find a solution to find all solutions or to find the best solution according to some metric 8 c1 S E N D M O R Y 8 0 S Y 9 c2 S E N D M O R Y 8 1000 S 100 E 10 N D 1000 M 100 O 10 R E 10000 M 1000 O 100 N 10 E Y c3 S E N D M O R Y 8 S 0 c4 S E N D M O R Y 8 M 0 c5 S E N D M O R Y 8 S Y all different Formalize the problem as a constraint problem number of variables n constraints c1 cm n problem Find a v1 vn n such that a ci for all 1 i m Solution 9 5 6 7 1 0 8 2 8 3 6 9 1 Informal



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Constraint Satisfaction 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 Constraint Satisfaction 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?