Skip to content

Search Algorithms

Search is the process of finding a sequence of actions that achieves a goal in a given environment. It's fundamental to intelligent-agent problem-solving.

Problem Formulation

Binary Tree Search Structure A tree structure showing how search algorithms explore the state space. Root is initial state, branches show possible actions, leaves are goal states.

Every search problem requires: - Initial state: Where the agent starts - Actions/Operators: Available moves in each state - Transition model: Result of applying an action - Goal test: Condition(ing that identifies goal states - Path cost: Cost of each action (usually 1, but can vary)

Search Space Concepts

  • State space: The set of all possible states reachable from initial state
  • Search tree: Tree representation of paths from initial state
  • Search graph: State space represented as a graph (with cycles/revisits handled)

Uninformed Search Strategies

Blind search with no domain knowledge. Characterized by: - Completeness: Does it find a solution if one exists? - Optimality: Does it find the minimum-cost solution? - Time complexity: Grows with branch factor $b$ and depth $d$ - Space complexity: Memory required

Key Uninformed Algorithms

Algorithm Complete? Optimal? Time Space Notes
BFS Yes Yes (if cost=1) $O(b^d)$ $O(b^d)$ Exponential memory
DFS No No $O(b^m)$ $O(bm)$ m=max depth
IDDFS Yes Yes $O(b^d)$ $O(bd)$ Best uninformed
Uniform-cost Yes Yes $O(b^{C*/\epsilon})$ Exponential Handles varying costs
  • Expand shallowest nodes first
  • Uses FIFO queue
  • Complete and optimal for unit-cost problems
  • Memory-intensive: stores all nodes at frontier
  • Expand deepest nodes first
  • Uses LIFO stack
  • Space-efficient but can get lost in infinite branches
  • Not guaranteed to find optimal solution
  • Combines DFS space-efficiency with BFS completeness
  • Repeats DFS with increasing depth limits
  • Asymptotically same complexity as BFS, better memory
  • Preferred uninformed strategy

Uses domain knowledge to guide search via heuristic function $h(n)$ = estimated cost to goal.

  • Most important algorithm in AI
  • Evaluation function: $f(n) = g(n) + h(n)$
  • $g(n)$ = actual cost from start to $n$
  • $h(n)$ = heuristic estimate from $n$ to goal
  • Optimal if heuristic is admissible
  • Most efficient if heuristic is consistent
  • Expands fewest nodes among optimal algorithms

Admissibility & Consistency

  • Admissible: $h(n) \leq h^*(n)$ for all $n$ (never overestimates)
  • Consistent: $h(n) \leq c(n,a,n') + h(n')$ (triangle inequality)
  • Consistency implies admissibility

Heuristic Generation

Sources of good heuristics: - Relaxed problems: Remove constraints - Pattern databases: Precomputed optimal solutions to subproblems - Learning: Machine learning from experience

For problems where path doesn't matter, only final solution:

  • Hill climbing: Greedy, get stuck in local maxima
  • Simulated annealing: Probabilistic, escape local optima
  • Genetic algorithms: Population-based evolution
  • Beam search: Keep k best nodes
  • Nondeterministic environments: AND-OR-Search
  • Partial observability: Belief states, sensorless problems
  • Online search: No model, learn environment online (LRTA*)

References

Russell & Norvig (2010): Chapters 3-4