AI AI-01.03
Uninformed search: BFS, DFS, uniform cost
Frontiers and explored sets, how breadth-first, depth-first and uniform-cost search behave, completeness, optimality, and iterative deepening.
The big idea
Once a problem is a state space, solving it means exploring that space until you reach a goal. Uninformed searchSearch that uses only the problem definition, with no estimate of how close a state is to the goal. does this with no sense of direction: it does not know whether the goal is near or far, left or right. All it can choose is the order in which to explore. That one choice, which state to look at next, produces algorithms with very different behavior.
Breadth-first search explores in rings around the start, like ripples on a pond. Depth-first search follows one path as far as it goes before backing up, like walking a maze with one hand on the wall. Uniform-cost search always extends the cheapest route found so far, like water flowing downhill along the easiest channels. Watch them on the same map and the differences are obvious.
How it works
Step 1: The frontier
Every search algorithm in this module shares one loop. Keep a frontierThe set of discovered states waiting to be expanded. Which one is taken next defines the search algorithm. of states that have been discovered but not yet expanded, starting with the initial state. Then repeat:
- Take a state off the frontier. If it passes the goal test, stop: you have a solution.
- Otherwise expand it: generate the states its actions lead to.
- Add new ones to the frontier, and remember the expanded state in the explored set so it is not expanded again.
The only difference between the algorithms is which state step 1 takes:
- Breadth-first search (BFS): the oldest one. The frontier is a first-in, first-out queue.
- Depth-first search (DFS): the newest one. The frontier is a last-in, first-out stack.
- Uniform-cost search (UCS): the one with the cheapest path so far. The frontier is a priority queue ordered by path cost. On graphs this is Dijkstra's algorithm.
Step 2: Same tree, different order
The difference looks small on seven nodes and becomes enormous on large spaces. Watch it on a grid:
Try it
Try this:
- Run BFS. The glowing frontier grows in rings (diamonds, since moves are up, down, left and right) until it touches the goal. Note the path cost.
- Run DFS. It snakes along one direction, hugging walls, and its path is long and strange. It found a path, not a good one.
- Run UCS. It spreads like BFS on open ground, but flows around the brown mud because entering mud costs 5. Compare its path cost with BFS: BFS walked straight through the mud.
- Draw a wall that completely separates S from G and run any algorithm: each reports that no path exists after exploring everything reachable.
Step 3: The same idea in code
The road map from the last lesson, searched with BFS and UCS:
from collections import deque
import heapq
# A small road map: town -> {neighbour: km}
ROADS = {
"Ashford": {"Bexley": 75, "Crane": 140, "Dunmore": 118},
"Bexley": {"Ashford": 75, "Elmwood": 71},
"Crane": {"Ashford": 140, "Elmwood": 151, "Fairview": 99, "Glenn": 80},
"Dunmore": {"Ashford": 118, "Hollis": 111},
"Elmwood": {"Bexley": 71, "Crane": 151},
"Fairview": {"Crane": 99, "Kingsport": 211},
"Glenn": {"Crane": 80, "Juniper": 97, "Ivy": 146},
"Hollis": {"Dunmore": 111, "Ivy": 160},
"Ivy": {"Hollis": 160, "Glenn": 146, "Juniper": 138},
"Juniper": {"Glenn": 97, "Ivy": 138, "Kingsport": 101},
"Kingsport": {"Fairview": 211, "Juniper": 101},
}
def cost(path):
return sum(ROADS[a][b] for a, b in zip(path, path[1:]))
def bfs(start, goal):
frontier, seen, expanded = deque([[start]]), {start}, 0
while frontier:
path = frontier.popleft() # oldest path first
expanded += 1
if path[-1] == goal:
return path, expanded
for nxt in ROADS[path[-1]]:
if nxt not in seen:
seen.add(nxt)
frontier.append(path + [nxt])
def ucs(start, goal):
frontier, done, expanded = [(0, [start])], set(), 0
while frontier:
g, path = heapq.heappop(frontier) # cheapest path first
if path[-1] in done:
continue
done.add(path[-1])
expanded += 1
if path[-1] == goal:
return path, expanded
for nxt, km in ROADS[path[-1]].items():
heapq.heappush(frontier, (g + km, path + [nxt]))
for name, fn in [("BFS", bfs), ("UCS", ucs)]:
path, n = fn("Ashford", "Kingsport")
print(f"{name}: {' -> '.join(path)}")
print(f" {len(path) - 1} roads, {cost(path)} km, expanded {n} towns")Output
BFS: Ashford -> Crane -> Fairview -> Kingsport
3 roads, 450 km, expanded 9 towns
UCS: Ashford -> Crane -> Glenn -> Juniper -> Kingsport
4 roads, 418 km, expanded 11 towns BFS finds the route with the fewest roads, 3, but it is 450 km long. UCS expands a couple more towns and finds a 4-road route of 418 km: the cheapest. BFS minimizes the number of steps; UCS minimizes cost. They agree only when every step costs the same.
Step 4: How to compare search algorithms
Four questions decide whether an algorithm fits a problem:
- Complete: is it guaranteed to find a solution if one exists?
- Optimal: is the solution it finds the cheapest?
- Time: how many states does it expand?
- Space: how many states must it hold in memory at once?
With the branching factorThe number of successors each state has on average. A grid with four moves has a branching factor of about 4. and the depth of the shallowest goal, BFS is complete and finds the fewest-step path, but it stores the whole frontier, about states. At and that is ten billion. DFS stores just one path plus siblings, about for maximum depth , but it can wander down an endless branch and is not optimal. UCS is complete and optimal for positive costs, and costs about the same as BFS or more.
Going deeper
Iterative deepening: the best of both
Iterative deepeningRepeated depth-first searches with a depth limit of 0, 1, 2 and so on, combining DFS's small memory with BFS's completeness and shortest-step solutions. runs depth-first search with a depth limit of 0, then 1, then 2, and so on until it finds the goal. It looks wasteful, since shallow levels are re-explored each time, but most states in a tree are at the deepest level, so the repeated work is small: with it does about 11 percent more work than BFS. In return it needs only DFS's tiny memory and still finds the shallowest goal. For large state spaces of unknown depth, it is the preferred uninformed search.
Bidirectional search
Searching forward from the start and backward from the goal at the same time, and stopping when the two frontiers meet, cuts the work from about to about , a huge saving. It needs actions that can be reversed and a single, known goal state.
Uninformed search is blind
All three algorithms in this lesson expand cells away from the goal just as eagerly as toward it. In the lab, BFS explores most of the grid even though the goal is straight ahead. The next lesson, Informed search and A* , adds a sense of direction.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Breadth-first search | Small state spaces where you want the fewest steps and all steps cost the same | Memory: the frontier grows exponentially with depth |
| Depth-first search | Huge or deep spaces where any solution will do and memory is tight | Optimality, and completeness on infinite or cyclic spaces without checks |
| Uniform-cost search | Steps with different costs, when you need the cheapest solution | Speed: it explores in all directions, like BFS |
Common mistakes
- Using BFS when step costs differ and calling the answer optimal. BFS minimizes steps, not cost.
- Running tree search on a graph with cycles. Without an explored set, the search can loop forever.
- Checking the goal when a state is generated instead of when it is expanded, in uniform-cost search. A cheaper path may still be on the frontier.
- Underestimating BFS's memory. It usually runs out of memory long before it runs out of time.
Check yourself
-
Which data structure makes a search breadth-first?
Show answer
B. A queue (first in, first out) BFS always expands the oldest discovered state, which a first-in, first-out queue provides.
-
Roads have different lengths. Which search is guaranteed to find the shortest route in km?
Show answer
C. Uniform-cost UCS expands the cheapest path first, so the first time it expands the goal, that path is cheapest.
-
Why is depth-first search attractive for very large spaces?
Show answer
B. It needs very little memory DFS holds only the current path and its siblings, so memory grows with depth, not with the width of the space.
-
What does iterative deepening combine?
Show answer
B. DFS's small memory with BFS's completeness and shortest-step solutions Repeated depth-limited DFS gives BFS-like guarantees with DFS-like memory, at a small cost in repeated work.
Recap
- Search keeps a frontier of discovered states; the order it expands them defines the algorithm.
- BFS (queue) explores in rings and finds the fewest-step path but uses lots of memory.
- DFS (stack) dives deep with little memory but is neither optimal nor always complete.
- UCS (priority queue by cost) finds the cheapest path when step costs differ.
- Iterative deepening combines DFS's memory with BFS's guarantees.