6.034 Artificial Intelligence - Recitations, fall 2004 online slides on search

Next: Analysis Previous: Examples

Analysis

Assume the solution is at level $d$ and branching factor is $b$

Time complexity (number of nodes considered) is
1 (first level) + $b$ (second level) + $b^2$ (third level) + $\ldots$ + $b^d$ (solution level) + (\(b^{d+1}\) - $b$)= \(O(b^{d+1})\)

This assumes solution is on the far right of the solution level This also assumes a constant branching factor $b$

Space complexity (at most a majority of nodes at $d$ level + majority of nodes at $d+1$ level) = \(O(b^{d+1})\)

This means exponential time and space

Benefits

  • Simple to encode
  • Always find solution if one exists (reach any point in space in finite time)
  • Least-LENGTH solution
    Not necessarily least-cost solution, unless all operators (actions) have equal cost