Meeting 04: Heuristic Search

Reading: AIAMA 3.5-3.6

This section of the text introduces a classic set of algorithms from AI, informed or heuristic search. The idea is to extend uniform-cost search to an arbitrary evaluation function representing the priority in the frontier. Section 3.5.1 describes greedy (best-first) search where this function is the heuristic value for the node. Section 3.5.2 extends this to a function that is the sum of the cost to reach the node from the root plus the heuristic. This is the classic A-star search algorithm. Section 3.5.3 addresses some limitations of A-star search and describes some variations.

Questions you should be able to answer after reading are:

  1. What is the difference between uninformed and informed search?
  2. What is a heuristic function?
  3. How is uniform-cost search adapted to create greedy best-first search?
  4. How is uniform-cost search adapted to create A-star search?
  5. What are the conditions on the heuristic function so that A-star search is optimal?
  6. What is the main limitation of A-star search?

Section 3.6 provides more details and examples of heuristic functions and how to create them. The main questions you should be able to answer after reading this section is how does one determine if one heuristic is better than another?