Search

A*
- Admissibility: \( \forall n, 0 \leq h(n) \leq h^*(n)\) where \(h^*(n)\) is the true forward cost
  i.e. underestimates forward cost
- Consistency: \( \forall A, C; h(A) - h(C) \leq cost(A, C)\)
  i.e. underestimates all arc costs
- Consistency implies Admissibility
- Tree search requires admissibility, Graph search requires consistency
- The max of two admissible/consistent heuristics will also be admissible/consistent
Search Properties
- Completeness: the ability to always find a goal (any goal)
- DFS is not complete! (can be stuck in a loop)