Slide Set 2: State-Space Search 46

ICS 271, Fall 2007: Professor Padhraic Smyth

# Search Strategies

•

A search strategy is defined by picking the order of node expansion

•

Strategies are evaluated along the following dimensions:

–

completeness: does it always find a solution if one exists?

–

time complexity: number of nodes generated

–

space complexity: maximum number of nodes in memory

–

optimality: does it always find a least-cost solution?

•

Time and space complexity are measured in terms of

–

b: maximum branching factor of the search tree

–

d: depth of the least-cost solution

–

m: maximum depth of the state space (may be ∞)