Constraint Satisfaction Problems

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

• Diptarko Roy, Churchill College
• Wednesday 29 November 2017, 19:30-20:00
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.