|
|
Like all plans, this is just a plan that is most likely wrong!
Nevertheless, I like to be a man with a plan. Most likely, we will not cover
all of the topics below. We might find that we want to spend more time using
(and abusing) actual constraint programs to solve actual problems. That would be fine.
-
Introduction: what is a constraint satisfaction problem? How do we
solve it? Who cares? We will use a sample problem, or two, to demonstrate this.
-
Search Algorithms: we introduce good old fashioned chronological backtracking
(hey, good enough to escape the Minataur!), backward checking algorithms
(maybe not so good) such as backmarking, backjumping, and conflict-directed backjumping.
We then look forwards, with forward checking.
-
Arc-consistency: what's that then? We introduce arc-consistency, and the
earliest practical algorithm AC3. We then look (briefly) at support counting algorithms such as AC4.
Then the generic algorithm, AC5, with constraints as objects, leading to MAC.
-
The "All Different" Constraint
-
Feedback on Exercise 1
Heuristics: AR33 sections 5 and 8
- See Peter van Beek's slides (updated by Patrick) on heuristics
- See the n-queens problem as a study of heuristics
- See team building with budgets as a study of heuristics
- Two papers that may be of interest are
- An empirical study of dynamic variable ordering heuristics for the constraint satisfaction
problem, by Ian Gent, Ewan MacIntyre, Patrick Prosser, Barbara Smith, and Toby Walsh
(pdf)
- Trying harder to fail first, by Barbara Smith and Stuart Grant
(pdf)
- Failing First: an update, by Beck, Prosser, and Wallace
(pdf)
Search (again)
-
Where are the hard problems?
|
