Back to practice exercises.
1: Background Reading
2: Learning Goals
 Define what a heuristic is. Define an admissible heuristic.
 Construct admissible heuristics for appropriate problems. Verify heuristic dominance. Combine admissible heuristics.
 Define/read/write/trace/debug different search algorithms:
 With / Without Costs
 Informed / Uninformed
3: Directed Questions
 What is the distinction between informed and uninformed search? [solution]
 What is a heuristic? [solution]
 When is a heuristic admissible? [solution]
 A* can be seen as a combination of what two search strategies? [solution]
4: Exercise: Heuristic Search
 Consider the search problem represented in the following figure, where a is the start node and e is the
goal node. The pair [f, h] at each node indicates the value of the f and h functions for the path
ending at that node. Given this information, what is the cost of each arc? The cost <a,c> = 2
is given as a hint. [solution]
 Is the heuristic function h admissible? Explain why or why not. [solution]
 Trace A* on this problem. Show what paths are in the frontier at each step. [solution]
5: Learning Goals Revisited
 Define what a heuristic is. Define an admissible heuristic.
 Construct admissible heuristics for appropriate problems. Verify heuristic dominance. Combine admissible heuristics.
 Define/read/write/trace/debug different search algorithms:
 With / Without Costs
 Informed / Uninformed
