Uninformed Search
Exploring a problem blind, with no clue which way the goal is. BFS, DFS, iterative deepening and uniform cost search, and how to tell them apart.
In week 1 you learned to turn a problem into a search: states, actions, and a goal test. Now we actually explore that space. Uninformed search, also called blind search, means the algorithm has no hint about which direction the goal lies in. It can only expand states in a fixed order and check each one. That sounds limited, but these five algorithms are the foundation everything else builds on, and the differences between them are a favourite exam topic.
The search framework
Every search algorithm on this page follows the same skeleton, so learn it once. The algorithm keeps a collection of nodes it has discovered but not yet explored, called the frontier. It repeatedly takes one node from the frontier, checks if it is the goal, and if not, expands it: generates its successor states and adds them to the frontier. It also remembers which states it has already visited so it does not loop forever.
The only thing that separates these algorithms is one decision: which node do you take from the frontier next? Change that single rule and you get a completely different search behaviour. That is the whole secret of this topic.
Four ways to judge an algorithm
Before comparing algorithms we need a scorecard. Every search algorithm is judged on the same four properties, and exams expect you to state all four.
- Complete: is it guaranteed to find a solution if one exists?
- Optimal: is it guaranteed to find the best (lowest-cost) solution?
- Time complexity: how many nodes does it generate?
- Space complexity: how many nodes must it hold in memory at once?
Time and space are written using three letters you will see constantly:
| Symbol | Meaning |
|---|---|
b | Branching factor: the most successors any node has |
d | Depth of the shallowest solution |
m | Maximum depth of the whole tree (can be infinite) |
Breadth-first search (BFS)
BFS explores the tree level by level: it checks everything one step from the start, then everything two steps away, and so on. It never goes deeper until the current level is fully explored. To do this it always takes the shallowest node from the frontier, which means the frontier behaves as a queue, first in, first out.
| Property | BFS | Why |
|---|---|---|
| Complete | Yes | If a solution exists at any finite depth, BFS reaches it |
| Optimal | Yes, if all step costs are equal | It finds the shallowest goal, which is cheapest only when every step costs the same |
| Time | O(b^d) | It may expand every node down to the solution depth |
| Space | O(b^d) | It must store the entire frontier, which grows exponentially |
Depth-first search (DFS)
DFS is the opposite instinct: pick a path and follow it as deep as possible, only backtracking when it hits a dead end. It always takes the deepest node from the frontier, so the frontier behaves as a stack, last in, first out.
The trade-off flips completely. DFS only needs to remember the single path it is currently on, so its memory use is tiny. But it can charge down a wrong or infinite branch forever, which costs it both completeness and optimality.
| Property | DFS | Why |
|---|---|---|
| Complete | No, unless you track visited states | It can loop forever down an infinite branch |
| Optimal | No | It returns the first solution found, not the shallowest or cheapest |
| Time | O(b^m) | In the worst case it explores the whole tree to depth m |
| Space | O(b·m) | Only one path plus its siblings is held. This is the big win |
See them side by side
Reading about queues and stacks is one thing, watching them is another. Below is the same tree searched by both algorithms. Switch between BFS and DFS, then step through and watch the order nodes are expanded and how the frontier fills. The goal is node J.
Amber nodes are on the frontier, indigo nodes have been expanded, green is the goal once found.
Depth-limited and iterative deepening
DFS has a fatal flaw: it can fall down an infinite branch. The fix is depth-limited search, which is just DFS with a hard cutoff: never go deeper than a limit L. That stops the infinite fall, but introduces a new problem. If the solution is deeper than L, you miss it entirely.
Iterative deepening search (IDS) solves this with a clever trick: run depth-limited search with L equal to 0, then 1, then 2, and so on, until the goal is found. It sounds wasteful to keep restarting, but it gives you the best of both worlds.
- It is complete and optimal (for equal step costs), like BFS.
- It uses only O(b·m) memory, like DFS.
The apparent waste barely matters. The deepest level holds the vast majority of nodes and is generated only once, so re-expanding the tiny shallow levels a few extra times adds only a constant factor. That is why IDS is often the go-to uninformed algorithm.
Uniform cost search (UCS)
Everything so far assumed every step costs the same. Reality is messier: a short road and a long motorway are both one step, but they are not equally cheap. BFS would pick the route with fewer steps even if it is longer in distance. Uniform cost search fixes this by always expanding the node with the lowest total cost so far, not the shallowest one. The frontier becomes a priority queue ordered by cost.
Two routes from Start to Goal:
UCS is complete and optimal whenever step costs are positive. The price is that, like BFS, it can hold a large frontier in memory. It also has no sense of direction, it expands outward in every direction in order of cost, which is exactly the gap that informed search fills next week.
The comparison table
This table is the single most exam-relevant thing on the page. If you memorise one thing, memorise this.
| Algorithm | Complete | Optimal | Time | Space | Frontier |
|---|---|---|---|---|---|
| BFS | Yes | Yes, equal costs | O(b^d) | O(b^d) | Queue |
| DFS | No | No | O(b^m) | O(b·m) | Stack |
| Depth-limited | No | No | O(b^L) | O(b·L) | Stack |
| Iterative deepening | Yes | Yes, equal costs | O(b^d) | O(b·d) | Stack |
| Uniform cost | Yes | Yes | Cost-based | Cost-based | Priority queue |
Now feel the numbers behind those formulas. Drag the branching factor and depth and compare what BFS must store against what DFS must store.
BFS stores the whole frontier, roughly b^d nodes. DFS stores one path, roughly b × d nodes.
Key points and practice
- All these algorithms share one skeleton and differ only in which node they expand next.
- BFS (queue): complete and optimal for equal costs, but eats memory.
- DFS (stack): tiny memory, but not complete or optimal.
- IDS: BFS's guarantees at DFS's memory cost, the practical default.
- UCS (priority queue): optimal even with different step costs.
- None of them use any knowledge of where the goal is. That is next week's upgrade.
BFS is complete and is optimal when step costs are equal, because it finds the shallowest goal, but it uses O(b^d) memory since it stores the whole frontier. DFS is not complete (it can loop down an infinite branch) and not optimal (it returns the first solution found), but it uses only O(b·m) memory because it stores just the current path.
IDS keeps BFS's completeness and optimality for equal step costs, but uses only linear O(b·d) memory instead of BFS's exponential memory. The repeated work of restarting is only a constant factor, because the deepest level holds most of the nodes and is generated once, so IDS gets BFS's guarantees at DFS's memory cost.
BFS is not optimal when step costs differ, because it finds the path with the fewest steps rather than the lowest total cost. Uniform cost search fixes this by expanding the node with the lowest cumulative cost first, which guarantees the cheapest path whenever costs are positive.
