DFS

Tree search incomplete (complete only if no cycles)

Graph Search complete but not optimal, measures paths in length instead of cost

BFS

Tree search complete

Graph Search complete, not guaranteed optimal unless all costs are uniform

UCS

Graph Search complete and optimal

Greedy

Graph Search is complete but not optimal

A*

Graph Search is complete and optimal with consistent heuristic

• not guaranteed to explore no more nodes than DFS graph search since DFS could explore directly to a suboptimal solution
• A*GS will not explore more nodes than UCS Graph Search with a consistent heuristic

Heuristics: Admissibility and Consistency

• Admissibility: 0 ≤ h(n) ≤ h*(n) (underestimate TC to goal)
  • With an admissible heuristic: Tree A* is optimal
• Consistency: h(A) ≤ cost(A to C) + h(C) (underestimate weight/cost of each edge)
  • With consistent: Graph A* is optimal
• F value along a path never decreases

Insert Discussion Sheet Diagram