Evaluation
Search strategies are evaluated along the following dimensions:
- completeness: does it always find a solution if one exists?
- time complexity: number of nodes generated/expanded
- 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:
- : maximum branching factor of the search tree
- : depth of the least-cost solution
- : maximum depth of the state space (may be )