Unit 6: Search Algorithms
Search algorithms play a huge role in AI. GPS, for example, is all about searching for some solution or optimal solutions in a large solution space, often described as a tree. This unit will discuss various search algorithms that can be utilized in many different situations.
Completing this unit should take you approximately 4 hours.
Upon successful completion of this unit, you will be able to:
- explain the concept of an "uninformed" search algorithm;
- apply various uninformed search algorithms and use them as appropriate for various search problems;
- describe the concept of a heuristic and how it can be used to improve search algorithms; and
- apply the concepts of the A* search algorithm when combined with admissible heuristics.
6.1: Uninformed Search Algorithms
The simplest search algorithms are "uniformed" or brute-force search. Different algorithms, such as depth-first, breadth-first, and uniform cost search, fall into the uninformed category because there is no knowledge, insight, or hint about where the right solution might lie.
6.2: Heuristic Search Algorithms
In contrast to uninformed search, informed search methods use insights or "heuristics" about where the optimal solution may lie in a complex solution space. Heuristics can be used to narrow the search. Examples of informed search algorithms include A*, also called Dijkstra's method. This section describes the key idea of the admissible heuristic that makes A* the optimal search algorithm, although still exponential. Many properties of admissible heuristics will be provided to guide you in finding these heuristics in other problems.