Topic 11b
Agents that Reason/Search

Learning Outcomes

By the end of this topic students should be able to:

  • Define and provide examples for foundational vocabulary terms including:
    • Production System
    • Production (aka “actions”)
    • State
    • Children
    • State Space
    • Search Tree
    • breadth-first search
    • depth-first search
  • Given a simple search problem and a particular node in the search space for that problem, identify the children that can be generated.
  • Given a simple search problem, discuss the order that nodes are visited using:
    • breadth-first search
    • depth-first search

 

Learning Materials

Checking for Understanding

Consider the following problems

 

Further Information

In the main materials I introduced search using an example with Analysts and Hackers. If you want to see this again, with a different example, you might consider my "Travelling in Romania" example.

 

 

On page 583 your book talks about the A* algorithm. Of all of the search techniques, this is the only one guaranteed to find the optimal path. While the implementation of the A* isn't a part of the Learning Outcomes for this course (we do visit it in the last course in our program), in the end, the algorithm isn't that difficult to understand. If you would like to know more about A* you can use the materials below.

 

Also, in this topic we focus on traditional search. Game-Playing is often viewed as a modification of traditional search. This is not one of the Learning Outcomes for this course. But you might find it interesting: