Depth‐First Search (DFS)
https://en.wikipedia.org/wiki/Depth‐first_search
Example: DFS
S
B
A BCC
A
CG
S
B
Nodes in circle mean those in the search tree, including the expanded ones (shaded) or to be expanded (i.e. in the frontier).
CGG G
Breadth‐First Search (BFS)
https://en.wikipedia.org/wiki/Breadth‐first_search
Example: BFS
S
B
A BCC
A
CG
S
B
Nodes in circle mean those in the search tree, including the expanded ones (shaded) or to be expanded (i.e. in the frontier).
CGG G
Search algorithm properties
Time complexity (worst case)
Space complexity (worst case)
A 1 2B1
Complete
Guaranteed to find a solution if
S
1
C1G
one exists
Optimal
Guaranteed to find the least
cost path
1
Preparation for Complexity analysis
b is the branching factor, i.e., number of successors a node has
1 node
b nodes b2 nodes
d is the depth of the shallowest goal
d layers
m is the maximum depth of the m layers entire tree
bd nodes
How many nodes in the entire tree: 1 ⋯
bm nodes
Goal state
DFS properties
1 node b nodes b2 nodes
Time complexity
d layers m layers
Space complexity
, since in every layer only b nodes in the memory (i.e. in frontier)
bd nodes
Is complete?
bm nodes
could be infinite, so complete only if you prevent cycle
S
B
Is optimal?
No, it finds the “leftmost”
A BCC C G G
solution, regardless of cost
G
BFS properties
1 node b nodes b2 nodes
Time complexity
⋯
d layers m layers
since nodes in the next layer need some operations (i.e. be put into frontier)
bd nodes
Space complexity
1
bm nodes
Is complete?
Yes, but must be finite if a
solution exists
Is optimal?
Only if costs are the same of
each action
Comparison between DFS and BFS
Algorithm
Time Space complexity complexity
Complete Yes* Yes**
Optimal No Yes***
Depth‐first search
Breadth‐ first search
d layers m layers
1 node
b nodes b2 nodes
*If m is finite. **if d is finite. ***if all actions have the same cost.
bd nodes
bm nodes