Search
- Definition
- In a search space, find a path from intial state to goal state.
Search space is any type of problem that can be modelled as a directed graph.
Many problems can be modelled as a graph. In chess, for example, the first line-up of pieces can be seens as the start node, each possible move from there as a node that is linked to the start node, and so on. Search starts with the start node. It finds its neighboring nodes and checks if one of them is the goal. If so, the path to the goal is returned. If not, the new path is added to the todo list of paths: the fronteer.
Examples
- Shortest path algorithm
- Chess
When should you use it?
- If there's no known algorithm to solve the problem more efficiently
Problems
- Search can be slow, hence it can be useful to add known shortcuts in the form of heuristics.