University of Cambridge > Talks.cam > Churchill CompSci Talks > Constraint Satisfaction Problems

Constraint Satisfaction Problems

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

Constraint satisfaction problems (CSPs) involve finding an assignment of discrete values to variables under the presence of constraints which limit what combinations of assignments are allowed. An example would be colouring a graph with a limited number of colours, such that no two adjacent nodes have the same colour, or solving a Sudoku puzzle. These both involve potentially searching a combinatorially large space of candidate solutions for a feasible assignment.

The talk will begin with an introduction to CSPs and some examples, and point out the specific deficiencies of naive approaches such as basic backtracking (as in Prolog), and how constraint propagation and specialised algorithms for global constraints improve on this. We’ll then see how a sequence of successively more sophisticated approaches and heuristics reduce graph colouring and Sudoku from requiring intractable amounts of time to being solvable within seconds.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity