Back to course 'CS205: Building with Artificial Intelligence'

Topic outline

  • Unit 6: Search Algorithms

    Collapse all Expand all

    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:

      [1] explain the concept of an 'uninformed' search algorithm; [1] apply various uninformed search algorithms and use them as appropriate for various search problems; [1] describe the concept of a heuristic and how it can be used to improve search algorithms; [1] 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.

    • Unit 6 Assessment