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:
- What are the five components of a problem defined as a state-space?
- What constitutes a solution to such a problem?
- Are multiple solutions possible, and if so how should one decide among them?
Section 3.3 formally defines the notion of trees and graphs.
- What does the frontier of a search correspond to?
- What does the explored set of a search correspond to?
- What is the essential difference between the tree-search algorithm and graph-search algorithm in Fig 3.7?
- 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.
- What specific kind of data structure is used to represent the frontier in breadth-first search?
- What specific kind of data structure is used to represent the frontier in uniform-cost search?
- What specific kind of data structure is used to represent the frontier in depth-first search?
- What is the limit parameter used for in the algorithm in Fig. 3.17?
- Why is iterative deepening not as wastefull as it first appears?
- When does a bidirectional search stop?
- What does the notation O mean in Fig. 3.21?
- What is the completeness criteria for a search?
- What is the optimality criteria for a search?
Links