In this chapter
- Understanding and designing heuristics for guided search
- Identifying problems that guided search approaches may solve
- Understanding and designing a guided search algorithm
- Designing a search algorithm to play a two-player game
Now that we have an idea of how uninformed search algorithms work (chapter 2), we can explore how to improve them by seeing more information about the problem. For this task, we use informed search. Informed search means that the algorithm has some context about the specific problem being solved; it doesn’t conduct a blind breadth-first or depth-first search.
Heuristics provide a way to represent this additional knowledge about the problem. Often called a rule of thumb, a heuristic is a rule or set of rules used to evaluate a state. It can define criteria that a state must satisfy or measure the performance of a specific state, for example. We use a heuristic when no clear method of finding an optimal solution is available. A heuristic can be interpreted as an educated guess; it’s more a guideline than a scientific truth with respect to the problem being solved.