--- 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