3 Intelligent search
This chapter covers
- Understanding and designing heuristics for guided search
- Identifying problems suited to being solved with guided search approaches
- Understanding and designing a guided search algorithm
- Designing a search algorithm to play a two-player game
Defining heuristics: Designing educated guesses
Now that we have an idea of how uninformed search algorithms work from chapter 2, we can explore how they can be improved by seeing more information about the problem. For this purpose, we use informed search. Informed search means that the algorithm has some context of the specific problem being solved. Heuristics are a way to represent this context. Often described as a rule of thumb, a heuristic is a rule or set of rules used to evaluate a state. It can be used to define criteria that a state must satisfy or measure the performance of a specific state. A heuristic is used when a clear method of finding an optimal solution is not possible. A heuristic can be interpreted as an educated guess in social terms and should be seen more as a guideline than as a scientific truth with respect to the problem that is being solved.