Unit 3 Overview: Search Techniques for Problem Solving
Unit 3: Search Techniques for Problem Solving — Overview
Last week, you explored how AI systems are designed as intelligent agents that perceive their environment and take actions. This week answers a critical follow-up question: How do agents actually find solutions to complex problems?
Connection to Unit 2: You learned that agents have goals and take actions to achieve them. Search is the computational engine that powers goal-directed behavior — it is how an agent decides which actions to take when the path to a goal isn’t obvious.
What You’ll Learn
By the end of this unit, you will be able to:
-
Formulate problems as state-space search problems with clearly defined states, actions, transition models, goal tests, and path costs
-
Distinguish between search trees and search graphs and understand when each is appropriate
-
Implement and analyze uninformed search algorithms: BFS, DFS, uniform-cost search, depth-limited search, and iterative deepening
-
Apply informed search algorithms — greedy best-first and A* — using heuristic functions
-
Design and evaluate heuristic functions for admissibility and consistency
-
Compare search algorithms using four performance criteria: completeness, optimality, time complexity, and space complexity
Why Search Matters
Search algorithms are the backbone of countless real-world AI applications:
-
Navigation systems (GPS, mapping apps) find optimal routes through road networks
-
Game-playing AIs search through possible moves to find winning strategies
-
Robotics systems plan collision-free paths in physical environments
-
Puzzle solvers systematically explore configurations to find solutions
Understanding search teaches you to solve complex problems by structuring them as state-space explorations, choose the right algorithm for a given situation, and reason about trade-offs between solution quality, time, and memory.
Two Families of Search
This unit introduces two fundamental families:
Uninformed search (also called blind search) explores the state space systematically using only the problem definition — no guidance about which direction is better. These algorithms are guaranteed to work but can be slow on large problems.
Informed search (heuristic search) uses problem-specific estimates to guide exploration toward promising areas. These algorithms are often dramatically faster, but they depend on the quality of the heuristic.
The unit’s crown jewel is A\ search* — an informed algorithm that is both optimal and efficient when given a good admissible heuristic. It powers GPS routing, robotics, and puzzle solving around the world.
Reading Assignments
- UC Berkeley CS 188 — Search
-
Primary reading for this unit. Covers state-space formulation, uninformed strategies (BFS, DFS, UCS, IDS), and informed search (Greedy, A*). Read through the heuristics section.
- Berkeley CS 188 — Heuristics
-
Supplementary: admissibility, consistency, and relaxed problems.
Weekly Schedule
| Section | Topic | Type |
|---|---|---|
3.1 |
Problems as State-Space Search |
Reading (complete) |
3.2 |
Search Trees vs. Search Graphs |
Reading |
3.3 |
Uninformed Search Strategies |
Reading |
3.4 |
Informed (Heuristic) Search |
Reading |
3.5 |
Designing Good Heuristics |
Reading |
3.6 |
Comparing Algorithms |
Reading |
Lab |
BFS on a Graph + A* on a Grid |
Lab notebook |
Wrap-Up |
Self-assessment and glossary |
Review |
Get a preview of the search algorithms you’ll study this week.
Before you begin: think about finding your way through a maze. What information would you need to formulate this as a search problem? What is a "state"? What is an "action"? How do you know when you’ve reached the goal?
Hold on to your answers — by the end of Section 3.1, you’ll have the formal vocabulary to express exactly what you’re thinking.
Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.
This work is licensed under CC BY-SA 4.0.