Back to practice exercises.
1: Background Reading
2: Learning Goals
- Build a constraint network for a set of constraints.
- Verify whether a network is arc consistent.
- Define/read/write/trace/debug the arc consistency algorithm. Compute its complexity and assess its possible outcomes.
- Define/read/write/trace/debug domain splitting and its integration with arc consistency.
3: Directed Questions
- What does it mean for an arc to be consistent?
- How can we enforce consistency of an arc <X,r(X,Y)>?
- What does it mean for a network to be arc consistent?
- What are the possible outcomes of the arc consistency algorithm?
4: Arc Consistency
- Consider the case where the arc consistency algorithm terminates and some domains have multiple values. Is there guaranteed to be a solution? To think about this issue, consider the CSP problem with three binary variables A, B, and C; with the three constraints A != B, B != C and A != C. Draw the corresponding constraint network, trace arc consistency and look at the outcome.
5: Learning Goals Revisited
- Build a constraint network for a set of constraints.
- Verify whether a network is arc consistent.
- Define/read/write/trace/debug the arc consistency algorithm. Compute its complexity and assess its possible outcomes.
- Define/read/write/trace/debug domain splitting and its integration with arc consistency.
|