Topic 6B - Reasoning and Search

Learning Objectives

By the end of this topic, you should be able to:

Define and provide examples for: production system, state, children, state space, search tree, breadth-first search, depth-first search.
Given a simple search problem, describe the order that nodes are visited using breadth-first search and depth-first search.
Explain what a heuristic is and how it guides search more efficiently than uninformed search.

To help you meet the learning objectives, we have prepared three readings. Please complete them in order — each one builds directly on the last.

Reading 1 - Problems as State Spaces — production systems, states, productions, and the key insight that an enormous range of problems all reduce to finding a path
Reading 2 - Search Trees and Breadth-First Search — how a control system builds and searches a tree level by level, with a fully traced worked example
Reading 3 - Smarter Search — why BFS gets overwhelmed, depth-first search as an alternative, and how heuristics guide search toward the goal more efficiently

These readings intentionally build on each other, so please complete them in order.

Review the Learning Objectives at the top of this page. The questions below will help you check your understanding before moving on to Topic 6C.

A librarian is trying to find a misfiled book. She starts in one section of the stacks, checks each shelf, and moves to an adjacent section if the book is not there. Describe this situation as a production system: what are the states? What are the productions? What is the start state? What is the goal state?
GPS navigation, chess, email spam filtering, and solving a jigsaw puzzle can all be framed as production systems. For one of them, identify the states, productions, start state, and goal state.
Why is it impractical to represent the entire state space for chess explicitly? What does this tell us about how AI systems must approach complex problems?

Draw the first two levels of a BFS search tree for the following small problem: you are at city A, which connects directly to cities B and C. City B connects to D and E. City C connects to F and G. The goal is city F. Show each node, label the levels, and indicate where BFS would find the goal.
What does it mean for BFS to be "complete"? What property of BFS guarantees that it will always find the shortest path to the goal?
BFS found the goal in the previous question by checking cities in what order? List them. Explain why BFS checks them in that order rather than pursuing one path all the way to a dead end first.

Using the same city map from question 4, trace how DFS would search for city F, assuming it always explores the leftmost branch first. In what order does it visit nodes? How does this compare to BFS?
Give an example of a heuristic that you might use in everyday life when making a decision under uncertainty. What makes it a heuristic rather than a guaranteed correct answer?
Your GPS estimates remaining travel time to your destination as you drive. How is this similar to a heuristic in a search algorithm? What could cause the estimate to be wrong — and how does the system recover when it is?

It is completely fine to revisit the readings as you work through these questions.

These optional topics go beyond the core learning goals but are rich avenues for deeper understanding.

The A* algorithm
- A* combines a heuristic estimate of remaining cost with the actual cost already incurred to reach a node — making it more reliable than best-first search while remaining efficient. It is the algorithm behind most GPS routing systems.
Minimax search in game-playing AI
- Chess and other two-player games require a search strategy that accounts for an opponent who is actively trying to minimize your score. Minimax search and alpha-beta pruning are the foundational techniques.
The traveling salesman problem
- A classic optimization problem — find the shortest route visiting a set of cities exactly once — that is simple to state but computationally explosive. It is a landmark example of a problem where exhaustive search is impossible and heuristics are essential.