# UI CS 4420 - Constraint Satisfaction (11 pages)

Previewing pages*1, 2, 3, 4*of 11 page document

**View the full content.**# Constraint Satisfaction

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

**View the full content.**View Full Document

## Constraint Satisfaction

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