Meeting 03: Tree and Graph Search

Reading: AIAMA 3.1-3.4

Section 3.1 of the text describes in general how to formulate problems as state-spaces and how to use search to solve them. We will be using this approach throughout the course. Section 3.2 gives a few examples of problems formulated as state-spaces.

Questions you should be able to answer after reading are:

  1. What are the five components of a problem defined as a state-space?
  2. What constitutes a solution to such a problem?
  3. Are multiple solutions possible, and if so how should one decide among them?

Section 3.3 formally defines the notion of trees and graphs.

  1. What does the frontier of a search correspond to?
  2. What does the explored set of a search correspond to?
  3. What is the essential difference between the tree-search algorithm and graph-search algorithm in Fig 3.7?
  4. What data structure (in general) is used to represent the frontier?

Section 3.4 goes on to describe six basic algorithms for performing search on a graph.

  1. What specific kind of data structure is used to represent the frontier in breadth-first search?
  2. What specific kind of data structure is used to represent the frontier in uniform-cost search?
  3. What specific kind of data structure is used to represent the frontier in depth-first search?
  4. What is the limit parameter used for in the algorithm in Fig. 3.17?
  5. Why is iterative deepening not as wastefull as it first appears?
  6. When does a bidirectional search stop?
  7. What does the notation O mean in Fig. 3.21?
  8. What is the completeness criteria for a search?
  9. What is the optimality criteria for a search?