Section 3 : Local search and problem structures of CSPs

Commentary

Section Goals

• To describe local search algorithms for constraint satisfaction problems.
• To examine ways to use the structure of the problems to quickly find solutions.

Learning Objectives

Learning Objective 1

• Explain how to use local search to solve CSPs.
• Discuss min-conflict heuristics and related algorithms.
• Summarize the techniques and categories of problem structures in the context of the constraint graph.
• Define the following concepts or terms:
  • Independent sub-problems
  • Tree-structured CSP
  • Tree decomposition

Objective Readings

Required Readings

Reading topics:

Local Search for Constraint Satisfaction Problems, The Structure of Problems (see Sections 6.4 - 6.5 of AIMA3ed).

Objective Questions

• How can local search be used to solve both CSPs and general search problems?
• What is the time complexity of finding the smallest cycle cutset in CSP?

Objective Activities

• Explore the following min-conflicts heuristic-related problem from the textbook's website.
  • Min-Conflicts
• Complete Exercise 6.17 of AIMA3ed.