Now that we have covered the three most popular uninformed search algorithms, let's look at how they compare against each other when it comes to complexity. The decision to pick one algorithm over another is dependent on whether you care more about time or space.
First, let's get a few terminologies out of the way:
Completeness: Will the algorithm eventually reach the goal node?
Space: How much space cost does the algorithm incur? Maximum number of nodes in memory
Optimality: Will it find the optimal solution (the shortest path to the goal node)?
Time: Number of nodes generated
Step Cost: The distance between two consecutive nodes explored by an algorithm
Now, let's look at each algorithm individually:
1. Breadth First Search
Space is a bigger problem for BFS. Just take a look at the table below where both time and space costs are shown for a tree with branching factor (b) = 10.
2. Depth First Search
3. Uniform Cost Search (Cheapest First)
First, let's get a few terminologies out of the way:
Completeness: Will the algorithm eventually reach the goal node?
Space: How much space cost does the algorithm incur? Maximum number of nodes in memory
Optimality: Will it find the optimal solution (the shortest path to the goal node)?
Time: Number of nodes generated
Step Cost: The distance between two consecutive nodes explored by an algorithm
Now, let's look at each algorithm individually:
1. Breadth First Search
- Completeness: Yes. If the number of nodes is finite, the algorithm will eventually reach the goal as it traverses every node in all levels/depth of the graph until the goal node is reached
- Time: O(bd) here b is the branching factor (the number of children each node generates) and d is the depth of the goal node from the source node
- Space: O(bd) because every node in the graph is kept in memory
- Optimality: No. BFS traverses nodes in increasing depth so unless the cost is a non-decreasing function of depth, BFS does not find the shortest path to the goal node.
Space is a bigger problem for BFS. Just take a look at the table below where both time and space costs are shown for a tree with branching factor (b) = 10.
2. Depth First Search
- Completeness: Not in infinite space where a graph has infinite depth or in cases where the search space has a loop. The algorithm could be modified to record repeated graph states to avoid getting stuck in a loop.
- Time: O(bm) where m is the maximum depth of any node. b is the branching factor (number of children generated by each node)
- Space: O(b*m). The space complexity is linear and hence DFS is space friendly. This is because the only nodes kept in memory are the nodes in a vertical path. In the image below, each shade of blue represents one path/iteration. Only nodes in the particular iteration is kept in memory.
- Optimality: No.
3. Uniform Cost Search (Cheapest First)
- Completeness: Yes, if step cost >= e >= 0
- Time: O(b(c*/e)) where c* is the optimal cost and e is the minimum step cost
- Space: O(b(c*/e))
- Optimality: UCS does find the shortest path to goal node as it expands nodes in the order of increasing distance from the root node.
