Section 2 : Backtracking and intelligent backtracking search for CSPs

Commentary

Section Goals

• To discuss the backtracking search for constraint satisfaction problems.
• To describe several techniques used in search algorithms, such as forward checking and constraint propagation.
• To introduce some advanced techniques in backtracking search, such as intelligent backtracking.

Learning Objectives

Learning Objective 1

• Explain the principle behind backtracking search.
• Design a backtracking search algorithm.
• Name the heuristics for selecting unassigned variables.
• Summarize forward checking and constraint propagation methods.
• In general terms, explain how to handle special constraints.
• Exemplify the idea of intelligent backtracking search through the map-colouring problems in Section
• Define the following concepts or terms:
  • Minimum remaining values heuristic
  • Degree heuristic
  • Least-constraining-value heuristic
  • Forward checking
  • Constraint propagation
  • Arc consistency
  • K-consistency
  • Conflict set
  • Conflict-directed backjumping
  • Constraint learning

Objective Readings

Required Readings

Reading topics:

Backtracking Search for CSPs (see Section 6.2 - 6.3 of AIMA3ed).

Kondrak, G., and van Beek, P. (1997). A theoretical evaluation of selected backtracking algorithms. Artificial Intelligence, 89, 365-387.

Objective Questions

• What techniques are used to improve the backtracking search for CSPs?
• Explain how knowing the features of constraints is important in CSPs.
• What is the main function of the arc consistency algorithm?

Objective Activities

• Summarize any additional heuristics for the backtracking search for CSPs that are mentioned in the supplemental readings and other CSP-related papers.
• Explore the following backtracking search-related programs from the textbook's website.
  • Backtracking-Search
  • AC-3
• Complete Exercise 6.11 of AIMA3ed.