Thursday, October 8, 2009

Q: Is BFS really O(b^[d+1])?

In the book (Russel & Norvig) it is argued that the time and space complexity of BFS (breadth first search) is O(b^[d+1]) where b is the maximal branching factor and d the depth of the solution. The reason for this is that when searching at level d, so generate all the successors into the fringe. There are b successors for O(b^d) nodes at level d, so if we are unlucky and the last of those O(b^d) nodes is the goal state, we generate a total of O(b^[d+1]) states in total.

However,...., this is easily avoided, by first checking all the nodes in each layer for whether they are a goal state, and if we didn't find the goal state at that layer, we go back and generate all successors. So we delay the generation of the successors. This BFS* algorithm is O(b^d). So we shouldn't make a big fuss about BFS having an even worse time and space complexity than IDS (which also has O(b^d)).


  1. Is there a good reason not to simply perform the goal test on each node before adding it to the frontier (instead of waiting until expansion)?