- Search Example (RN p62)
*Romanian Travel* - breadth first
- depth first without recurrence check
- depth first with full recurrence check and backtracking
- depth limited
- iteratively increasing depth

- we have a
*path cost* - assumed that only know true cost
*after expansion* - heuristics
- from Greek word for discovery
- h(n) such that h(n)=0 iff goal, h smaller for better nodes
- examples - straight line distance, 8-puzzle
- how to find heuristic ?
- optimistic heuristics (less costly than actual)
- always underestimate cost
- triangle inequality heuristics
- best first search
- minimal accumulative cost on fringe g(n) (complete, optimal, but slow)
- special case - breadth first
- optimal if monotonic increasing cost (eg. additive)
- greedy heuristics (neither complete nor optimal, but often fast)
- A* (RN pp96-101)
- combination of best of above two f(n) = g(n) + h(n)
- optimal for optimistic heuristics
- optimally efficient - no other optimal algorithm always expands fewer nodes
- but still exponential for additive costs
- why does it work? equicost contours
- Examples - Romanian cities, 8-puzzle (cost >= h2 >= h1)
- A* variants
- Philosophical restrictions of search techniques
- search wasteful since doesn’t reason
- what's missing ?
- there is a mathematically developed theory of logic - basis of all math!