---
# System prepended metadata

title: CS188 - Lec. 3 - Informed Search
tags: [CS188]

---

---
tags: CS188
---
# CS188 - Lec. 3 - Informed Search

heuristic - a function that esimates how close a state is to a goal
- designed for a particular search problem

greedy search - expand the node that seems closest

A* search - dijkstra's with a heuristic added to the cumulative cost
- cannot terminate when we enqueue a goal
- must continue exploring until goal is removed from the queue
- optimal - the heuristic must be admissible and consistent for A* to return the optimal path
    - can be proved via induction, if admissible then ancestor node N will be expanded first

admissibility - optimistic heuristics slow down bad plans but never outweight true costs
- heuristic must return a lower cost than the actual cost
- 0 <= h(n) <= h\*(n) where h\*(n) is the true cost to a nearest goal
- purpose is so that optimal path never has a more expensive cost causing it to be skipped

properties of A* search
- searches things that are cheap and tries to look in the direction of the goal

creating heuristics
- admissible heuristics are solutions to relaxed problems where new actions are available
- easier problem will likely be more optimisic and thus admissible because it has less restrictions
