Breadth First Search
Chapter Twelve
Syllabus topic Module 1, "BFS"
Pages 57 to 61 of 591
In one line
Breadth first search looks at everything one step away, then everything two steps away, and so on, so the first goal it meets is the one with the fewest steps.
In the wording a student can write in an examination: breadth first search expands the shallowest unexpanded node. The frontier is a first in, first out queue, so nodes are expanded in the order they were generated. It is complete whenever the branching factor is finite, and optimal when every step has the same cost. Its time and space complexity are both O(b**d).
Why a queue gives you level order
The general algorithm removes a path from the frontier. Breadth first search removes the oldest one. That single choice has a consequence worth stating carefully, because it is the whole proof of the algorithm's behaviour.
A node's children are generated when it is expanded, so they are always newer than every node already on the frontier. A queue serves the oldest first. Therefore every node at depth k is expanded before any node at depth k plus 1. The search sweeps the tree level by level, and the first goal it finds is at the smallest depth at which any goal exists.
The algorithm
frontier = a QUEUE holding the path [start]; reached = {start}
loop:
if frontier is empty: return failure
path = frontier.popleft() <- the OLDEST path: the whole difference
for each child of path's last state:
if child is a goal: return path + [child] the EARLY test
if child not in reached: add it, and append path + [child]Two details in that skeleton decide whether an examiner's version matches yours.
The goal test is applied to a child as it is generated, not when the child is taken off the frontier. This is the early goal test, and it saves a whole level of expansion. It is safe for breadth first search because the first goal generated is already at minimum depth.
It would not be safe for uniform cost search, and two chapters from now that is exactly the bug the late goal test prevents. Do not carry the early test across.
A state is added to reached when it is generated, not when it is expanded. If it is only added on expansion, the same state can sit on the frontier several times and the memory doubles for nothing.
It running on the district map
from collections import deque
ROAD = {
"Amba": {"Bori": 8, "Chinch": 7, "Erandol": 33},
"Bori": {"Amba": 8, "Chinch": 12, "Devi": 5},
"Chinch": {"Amba": 7, "Bori": 12, "Erandol": 7, "Gokul": 13},
"Devi": {"Bori": 5, "Fanas": 7, "Hivra": 9},
"Erandol": {"Amba": 33, "Chinch": 7, "Fanas": 9, "Gokul": 6},
"Fanas": {"Devi": 7, "Erandol": 9, "Hivra": 2, "Jalna": 5},
"Gokul": {"Chinch": 13, "Erandol": 6, "Jalna": 6},
"Hivra": {"Devi": 9, "Fanas": 2, "Jalna": 16},
"Jalna": {"Fanas": 5, "Gokul": 6, "Hivra": 16},
}
def km(path):
return sum(ROAD[path[i]][path[i + 1]] for i in range(len(path) - 1))
def breadth_first_search(start, goal):
if start == goal:
return [start]
frontier = deque([[start]]) # a QUEUE of paths
reached = {start} # states already reached
step = 0
while frontier:
path = frontier.popleft() # oldest first: that is the queue
node = path[-1]
step += 1
print("%2d expand %-8s frontier now %-38s reached %d"
% (step, node, " ".join(p[-1] for p in frontier), len(reached)))
for child in sorted(ROAD[node]):
if child in reached:
continue
if child == goal: # the early goal test
return path + [child]
reached.add(child)
frontier.append(path + [child])
return None
route = breadth_first_search("Amba", "Jalna")
print()
print("route found:", " > ".join(route))
print("hops:", len(route) - 1, " cost:", km(route), "km")Breadth First Search
1 expand Amba frontier now reached 1
2 expand Bori frontier now Chinch Erandol reached 4
3 expand Chinch frontier now Erandol Devi reached 5
4 expand Erandol frontier now Devi Gokul reached 6
5 expand Devi frontier now Gokul Fanas reached 7
6 expand Gokul frontier now Fanas Hivra reached 8
route found: Amba > Chinch > Gokul > Jalna
hops: 3 cost: 26 kmFollow it as levels, because that is the behaviour to be able to describe.
- Step 1, depth 0. Amba is expanded and its three neighbours Bori, Chinch and Erandol go on the queue.
reachedbecomes 4. - Steps 2 to 4, depth 1. Bori, Chinch and Erandol are expanded, in the order they were queued. Their new neighbours Devi and Gokul are added behind them.
- Steps 5 and 6, depth 2. Devi and Gokul. When Gokul is expanded, one of its neighbours is Jalna, the early goal test fires, and the search stops.
Six expansions, and Hivra was never expanded at all. The route returned has three hops, which is the fewest possible, and costs 26 km.
The 1 km that matters
The cheapest route on this map is Amba, Bori, Devi, Fanas, Jalna at 25 km, and breadth first search did not find it. It has four hops, and breadth first search stopped as soon as it found a three-hop route.
That is not a defect. Breadth first search promises the fewest steps and delivered it. It promises least COST only when every step costs the same, and on this map they do not: roads are 2 km to 33 km. When a paper asks "is breadth first search optimal", the full-mark answer is: yes in the number of steps, and in cost only if all step costs are equal.
Breadth First Search
The 1 km gap looks small and the general case is not small. Change Amba to Chinch to 100 km and breadth first search still returns the same three-hop route, now at 119 km against an unchanged 25 km. The size of the error is unbounded; only the number of steps is controlled.
Memory is the real problem
The frontier at depth k holds up to bk nodes, so the peak is O(bd). The time is the same order, and those two facts are not equally bad.
Take the figures from The Search Tree, and How an Algorithm Is Judged at a branching factor of 10 and a depth of 12: about 1.1 million million nodes. At a hundred thousand nodes a second that is 128 days, which is merely annoying. Holding a thousand million million nodes in memory is impossible.
So breadth first search is beaten by memory long before it is beaten by time, and that is the single most useful thing to say about it. It is the reason Iterative Deepening Search exists: the same time complexity, O(b*d) space instead of O(b**d).
Where it is the right choice
- The state space is small enough to fit, which includes most examination questions.
- Every step costs the same, so it is genuinely optimal. This is common: the 8-puzzle, a word ladder, the fewest-moves version of any puzzle.
- You want the shallowest solution specifically, for instance the smallest number of moves rather than the lowest total cost.
- The branching factor is small.
Distinctions
| Breadth first search | Depth first search | |
|---|---|---|
| Frontier is a | queue, oldest first | stack, newest first |
| Order | level by level | one branch to the bottom |
| Complete | yes, if b is finite | no on an infinite space |
| Optimal | in steps | no |
| Time | O(b**d) | O(b**m) |
| Space | O(b**d), the killer | O(b*m) |
| On the district map | 26 km in 6 expansions | 68 km in 8 expansions |
| Breadth first search | Uniform cost search | |
|---|---|---|
| Orders the frontier on | depth | path cost g |
| Optimal in | number of steps | total cost |
| Goal test | early, on generation | late, on expansion |
| The same algorithm when | every step costs the same | |
| On the district map | 26 km | 25 km |
What it does not mean
Breadth first search is not optimal in general. It is optimal in the number of steps, and in cost only when every step costs the same. Saying "BFS is optimal" without that condition is a lost mark.
It does not use less memory than depth first search. It uses vastly more: exponential in the depth against linear.
The queue does not hold states. It holds paths, or nodes carrying a parent pointer. A frontier of bare states cannot return the route.
Breadth First Search
It does not stop at the first node it generates that happens to be a goal in some other branch. It stops at the first goal generated at all, and because it works level by level, that goal is at minimum depth.
Reaching a state is not the same as expanding it. In the run above Hivra was reached but never expanded, and the distinction is what reached counts.
Quick revision
- Breadth first search: expand the shallowest unexpanded node. Frontier is a FIFO queue.
- Level order follows from the queue: children are newer than everything on the frontier, so depth k is finished before depth k plus 1 begins.
- Early goal test, applied when a child is generated. Safe here; not safe for uniform cost search.
- Add a state to
reachedwhen it is generated, not when it is expanded. - Complete if b is finite. Optimal in the number of steps, and in cost only if every step cost is equal.
- Time
O(bd), spaceO(bd). Memory is what defeats it, not time. - On the standing map: 6 expansions, route Amba, Chinch, Gokul, Jalna, 3 hops, 26 km, against a cheapest route of 25 km in 4 hops.
- Right choice when the space is small, the step costs are uniform, or the shallowest solution is what is wanted.
Test yourself
1. Define breadth first search and name its frontier data structure. It expands the shallowest unexpanded node. The frontier is a first in, first out queue, so nodes are expanded in the order they were generated.
2. Prove that breadth first search expands nodes in order of depth. A node's children are generated when it is expanded, so they are newer than everything already on the frontier. A queue serves the oldest first, so no node at depth k plus 1 is served while any node at depth k remains. Hence all of depth k is expanded before any of depth k plus 1.
3. Is breadth first search optimal? State the condition exactly. It is optimal in the number of steps, always. It is optimal in path cost only when every step has the same cost.
4. On the standing district map breadth first search returns a 26 km route while a 25 km route exists. Explain. It returns the route with fewest hops, which is Amba, Chinch, Gokul, Jalna at three hops and 26 km. The cheaper route, Amba, Bori, Devi, Fanas, Jalna, costs 25 km but takes four hops, so the search finished before reaching it. The road costs on this map are unequal, so the optimality condition does not hold.
Breadth First Search
5. What are its time and space complexities, and which one rules it out in practice? Both are O(b**d). Space rules it out: at a branching factor of 10 and depth 12 the time is months, which is tolerable, while the memory required is far beyond any machine.
6. What is the early goal test and why is it safe here but not for uniform cost search? The early test checks each child for being a goal as it is generated, saving a level of expansion. It is safe here because the first goal generated is at minimum depth. In uniform cost search the first goal generated need not be the cheapest, so the test must wait until the node is selected for expansion.
7. In this chapter's run, reached ends at 8 but only 6 nodes were expanded. What is the difference? A state is reached when a path to it has been generated and put on the frontier. It is expanded when it is taken off the frontier and its own children are generated. Fanas and Hivra were reached and never expanded, because the search stopped first.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.