Module 2: Idealized Searches


Executive Summary

  • Topics: This module will cover the following topics.
    • Problem formulation (how to formulate a problem for search)
    • Uninformed search methods (how to search when you have minimal information to guide you)
    • Informed search techniques (how to search with some guidance)
  • Length: The content of this module will take one and a half weeks to complete.  
  • Assigned chapters: Chapter 3
  • Projects: This module is associated with Project 1 and 2 but only Project 1 is assigned during the module.   You can find your project assignments in the schedule and projects page.

Problem Solving & Search

Much of the press coverage on AI focuses on machine learning.  While we will cover machine learning this semester, this is a lot of AI that is driven by intelligent search!  Think about how many times you have used Google search or another search method to get directions.  Did you stop to think about how many choices it has to sift through to get you directions that are nearly optimal and arrive nearly as soon as you ask?  

In this module, we will cover intelligent search methods starting with ones that require minimal knowledge about the problem being solved (e.g., breadth first search and depth first search) and moving to methods that can provide optimal solutions but which require background knowledge about the solution (e.g. A*).   

Before discussing the search methods, we will discuss how to formulate a search problem precisely so that a solution is possible.  This involves understanding the characteristics of the environment as we discussed in the previous module.  Knowing what information is available to you and what environment your search is operating in is critical to choosing the right search method.  Just because A* is optimal in some situations does not make it the best search method for every problem domain.

Intelligent Search

walking path results from google on OU main campus

Example of a Google search from Devon to Dale

Next topic

Jump to topic 1: Problem formulation