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)).

3 comments:

  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)?

    ReplyDelete
  2. What is a free slot machine? - Dr. Maryland
    There are 서귀포 출장샵 two 서귀포 출장샵 popular slot machines with different payouts. Both 구리 출장안마 these machines have a 진주 출장마사지 return 영천 출장안마 to player percentage. The free-slots machines are not

    ReplyDelete