Guided Inquiry 4

Overview

The purpose of this guided inquiry is to go over the details of these informed search methods: Uniform Cost Search (UCS), greedy search, and A*.  You'll also learn about estimating the cost to get from a given state to the nearest goal state.

Learning Objectives

Basic learning objectives

You are responsible for learning and demonstrating proficiency in the following objectives prior to the next class meeting:

• describe the algorithm for Uniform Cost Search (UCS)
• describe the algorithms for informed search:
  • greedy search
  • A*
• define what it means for a heuristic to be admissible and consistent
• classify a heuristic as admissible, consistent, or neither
• create simple heuristics for a search problem

Advanced learning objectives

You should demonstrate mastery of the following objectives by the end of the next class meting through the in-class activities:

• develop and compare heuristics empirically
• compare search algorithms empirically

Resources

Watch these videos to help you understand the various algorithms. You might want to watch these at a faster speed.

• Uniform Cost Search
• Greedy search and heuristics
• A* part 1
• A* part 2