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?
- What is a heuristic?
- When is a heuristic admissible?
- A* can be seen as a combination of what two search strategies?
4: 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.
- Is the heuristic function h admissible? Explain why or why not.
- Trace A* on this problem. Show what paths are in the frontier at each step.
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
|