Summary and Next Lecture
Summary
- Best first tries to explore most promising node first
- In 8s puzzle, Manhattan distance is one heuristic
- Total distance is much better and has guarantees
- Best First + Guarantees = A*
- Branch and Bound also uses guaranteed bounds
Next Lecture: Heuristics in decision problems
- so far looked at heuristics for optimisation
- what about when just want any old solution, e.g. SAT
- Look at heuristics in these situations