Search
We can categorize search problems into to distinct areas...
- Constraint Satisfaction Problems
- Path-Search Problems.
The distinction comes from the fact that in CSPs, we have no care in the path taken to take us to the final goal state, rather the state itself is all that we are interested in. In contrast, the final state is not the problem faced in Path-Search Problems and in many cases, it is already known - what defines the problem is the path that should be taken to take us there.
For these reasons, search algorithms adopted for solving CSPs take a different approach to solving problems than those used to solve path-search problems.
In either case, the search algorithms themselves can be classified as either informed, or uninformed. An uninformed search has no concept of a goal, it just knows how to recognize one when found, hence it is often referred to as a blind search.
On the other hand, an informed search adopts a heuristic, which is provides the search algorithm a means of selecting the next best node to search, that is the node that it thinks is more likely to take it closer to the goal.
Constraint Satisfaction Problems
CSPs are a special kind of problems where...
- Knowing the path to get to the final state is simple
- Knowing the final state defines the problem
Search Algorithms
Uninformed (Blind) Search
- BTS (DFS for CSPs)
Informed (Heuristic) Search
Path Search Problems
- Knowing the final state is simple
- Knowing how to get there defines the problem
Search Algorithms
Uninformed (Blind) Search
- Breadth-First Search & Variances
- Depth-First Search & Variances
- Bi-Directional Search
Informed (Heuristic) Search
Games
Games are a great area to put research into practice, and search algorithms are present in more games than you'd imagine...
For two-player games, adversarial search algorithms can be used to look ahead and allow the agent (computer player) to make intelligent decisions.
Adversarial Search Algorithms
External Online Games, Puzzles & Animations
References
Russell, S. and Norvig, P. (2003). Artificial Intelligence, A Modern Approach (2nd ed.). New Jersey, Pearson Education International
