Practice Exercise 3.C
Heuristic Search

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

  1. What is the distinction between informed and uninformed search? [solution]

  2. What is a heuristic? [solution]

  3. When is a heuristic admissible? [solution]

  4. A* can be seen as a combination of what two search strategies? [solution]

4: Exercise: Heuristic Search

  1. 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]

    graph
  2. Is the heuristic function h admissible? Explain why or why not. [solution]

  3. 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

Valid HTML 4.0 Transitional