Problem Solving By Search
Problem-Solving Agents & State Spaces
Module 1, Chapter 4 introduced the general agent loop. A problem-solving agent is a specific kind of agent that decides on actions by first formulating a goal,
Jr Codex AI Notes
Level: Beginner–Intermediate Prerequisites: Module 1: Foundations of AI Time to complete: ~25 minutes
Table of Contents
- Problem-Solving as a Special Kind of Agent
- Defining a Search Problem Formally
- The State Space as a Graph
- A Worked Example: The Route-Finding Problem
- Representing a Search Problem in Code
- The General Search Algorithm Template
- Summary & Next Steps
1. Problem-Solving as a Special Kind of Agent
Module 1, Chapter 4 introduced the general agent loop. A problem-solving agent is a specific kind of agent that decides on actions by first formulating a goal, then searching for a sequence of actions that reaches it — rather than reacting to each percept in isolation.
Problem-Solving Agent's Process
─────────────────────────────────────────
1. GOAL FORMULATION — what do we want to achieve?
2. PROBLEM FORMULATION — what states/actions matter for this goal?
3. SEARCH — find a sequence of actions reaching the goal
4. EXECUTION — carry out the found action sequence
─────────────────────────────────────────
This works best in environments that are episodic, static, and largely observable/deterministic (Module 1, Chapter 4's environment classification) — search assumes you can reasonably predict the outcome of actions in advance, which breaks down in highly dynamic or stochastic settings (a limitation revisited when Module 5 covers reinforcement learning for exactly those trickier environments).
2. Defining a Search Problem Formally
Every search problem, regardless of domain, can be defined with five components:
The Five Components of a Search Problem
─────────────────────────────────────────
1. Initial State → where the agent starts
2. Actions → what moves are available from any given state
3. Transition Model → what state results from an action
4. Goal Test → how to check if a state is the goal
5. Path Cost → a number assigned to each path (to compare solutions)
─────────────────────────────────────────
Example: An 8-Puzzle (sliding tile puzzle)
─────────────────────────────────────────
Initial State: the puzzle's starting tile arrangement
Actions: move blank tile UP / DOWN / LEFT / RIGHT
Transition Model: swapping the blank with an adjacent tile
Goal Test: does the arrangement match the solved state?
Path Cost: 1 per move (fewer moves = better solution)
─────────────────────────────────────────
A solution is a sequence of actions from the initial state to a goal state; an optimal solution is the one with the lowest path cost among all solutions — the entire rest of this module is about algorithms for finding solutions (and, for some algorithms, guaranteeing optimality).
3. The State Space as a Graph
Every search problem can be visualized as a graph: nodes are states, edges are actions connecting one state to another.
State Space as a Graph
─────────────────────────────────────────
[Start]
/ \
action_A action_B
/ \
[State 1] [State 2]
/ \ \
action_C action_D action_E
/ \ \
[State 3] [Goal!] [State 4]
─────────────────────────────────────────
Searching means exploring this graph to find a path from the start node to a goal node — the algorithms in Chapters 2-3 differ entirely in which order they explore nodes, which determines their speed, memory use, and whether they're guaranteed to find the best path.
A critical distinction: the state space graph is usually not built and stored in memory upfront (for real problems it's often astronomically large, or even infinite) — instead, it's generated on the fly as the search explores, one state at a time, using the transition model from Section 2.
4. A Worked Example: The Route-Finding Problem
The classic, intuitive example — navigating between cities:
# A simplified map: which cities connect directly, and at what cost (distance)
romania_map = {
"Arad": {"Zerind": 75, "Sibiu": 140, "Timisoara": 118},
"Zerind": {"Arad": 75, "Oradea": 71},
"Oradea": {"Zerind": 71, "Sibiu": 151},
"Sibiu": {"Arad": 140, "Oradea": 151, "Fagaras": 99, "Rimnicu": 80},
"Timisoara":{"Arad": 118, "Lugoj": 111},
"Lugoj": {"Timisoara": 111, "Mehadia": 70},
"Mehadia": {"Lugoj": 70, "Drobeta": 75},
"Drobeta": {"Mehadia": 75, "Craiova": 120},
"Craiova": {"Drobeta": 120, "Rimnicu": 146, "Pitesti": 138},
"Rimnicu": {"Sibiu": 80, "Craiova": 146, "Pitesti": 97},
"Fagaras": {"Sibiu": 99, "Bucharest": 211},
"Pitesti": {"Rimnicu": 97, "Craiova": 138, "Bucharest": 101},
"Bucharest":{"Fagaras": 211, "Pitesti": 101},
}Mapping This onto the Five Components (Section 2)
─────────────────────────────────────────
Initial State: "Arad"
Actions: drive to any DIRECTLY connected city
Transition Model: romania_map[city] gives the reachable cities
Goal Test: current_city == "Bucharest"
Path Cost: sum of distances traveled
─────────────────────────────────────────
This exact map is the standard textbook example used throughout the rest of this module — every search algorithm in Chapters 2-3 will be demonstrated finding a route from Arad to Bucharest, so their behavior can be directly compared on identical ground.
5. Representing a Search Problem in Code
A reusable, general Problem structure — directly applying object-oriented design (Python Notes, Module 4) — that every algorithm in this module can work against:
class SearchProblem:
"""A generic search problem, following the 5-component formal definition."""
def __init__(self, initial_state, goal_state, graph):
self.initial_state = initial_state
self.goal_state = goal_state
self.graph = graph # adjacency structure, like romania_map above
def actions(self, state):
"""What actions (here: neighboring cities) are available from this state?"""
return list(self.graph.get(state, {}).keys())
def result(self, state, action):
"""The transition model — taking `action` from `state` leads here."""
return action # in this graph representation, the action IS the destination
def goal_test(self, state):
return state == self.goal_state
def step_cost(self, state, action):
"""The cost of moving from `state` via `action`."""
return self.graph[state][action]
problem = SearchProblem(initial_state="Arad", goal_state="Bucharest", graph=romania_map)
print(problem.actions("Arad")) # ['Zerind', 'Sibiu', 'Timisoara']
print(problem.result("Arad", "Sibiu")) # 'Sibiu'
print(problem.goal_test("Bucharest")) # True
print(problem.step_cost("Arad", "Sibiu")) # 140Every search algorithm from here forward operates purely against this SearchProblem interface — it never needs to know it's specifically about Romanian cities, which is exactly why the same BFS/DFS/A* code works unchanged for an 8-puzzle, a maze, or any other search problem fitting the five-component definition.
6. The General Search Algorithm Template
Nearly every algorithm in Chapters 2-4 is a variation on one core idea — maintaining a frontier (states discovered but not yet explored) and repeatedly expanding it:
def generic_search(problem, frontier):
"""
A template shared by BFS, DFS, UCS, Greedy, and A* — they differ ONLY
in how `frontier` is structured (a queue, stack, or priority queue) and
what order items are added.
"""
frontier.add((problem.initial_state, [])) # (state, path_so_far)
visited = set()
while not frontier.is_empty():
state, path = frontier.pop()
if problem.goal_test(state):
return path # SUCCESS — return the sequence of actions found
if state in visited:
continue
visited.add(state)
for action in problem.actions(state):
next_state = problem.result(state, action)
if next_state not in visited:
frontier.add((next_state, path + [action]))
return None # FAILURE — no solution foundWhat Changes Between Algorithms
─────────────────────────────────────────
BFS (Ch.2): frontier = a QUEUE (first-in-first-out)
DFS (Ch.2): frontier = a STACK (last-in-first-out)
Uniform-Cost (Ch.2): frontier = a PRIORITY QUEUE, ordered by path cost
Greedy (Ch.3): frontier = a PRIORITY QUEUE, ordered by heuristic estimate
A* (Ch.3): frontier = a PRIORITY QUEUE, ordered by cost + heuristic
─────────────────────────────────────────
Recognizing this shared skeleton is the single most useful mental model for this entire module — Chapters 2-3 are really just "which data structure backs the frontier, and how do we order it?"
7. Summary & Next Steps
Key Takeaways
- A problem-solving agent formulates a goal, then searches for an action sequence achieving it — well-suited to episodic, largely observable, deterministic environments.
- Every search problem is defined by five components: initial state, actions, transition model, goal test, and path cost.
- The state space is a graph of states connected by actions — usually generated on the fly during search, not built upfront.
- Nearly every search algorithm (BFS, DFS, UCS, Greedy, A*) shares the same frontier-expansion template, differing only in the frontier's data structure and ordering.
Concept Check
- What are the five formal components of a search problem?
- Why is the state space graph usually generated on the fly rather than built entirely in advance?
- What's the key structural difference between BFS and DFS, in terms of the generic search template from Section 6?
Next Chapter
→ Chapter 2: Uninformed Search
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index