State-Space Search

Bart Massey

State Space Graph

• Vertices are some sort of combinatorial object representing a system state: number of vertices is exponential in vertex size

  • Consequence: Many "CS 100" graph algorithms are hopelessly inefficient in practice

• Edges connect "related" objects: neighbors have a single minor difference in state

  • Consequence: Usually low-degree graph
  • Usually free to pick a neighborhood: choice often has impact on simplicity and efficiency of solution

Search Problems

• Typical problems involve finding a vertex or path in state space that has some particular property:

  • Satisfying: Find vertex, path, etc that meets some criteria
  • Optimizing: Find a vertex, path, etc that best meets some criteria

• In particular: these are pretty common formulations:

  • Constraint Satisfaction / Optimization problems
  • Min-cost pathfinding problems
  • Scheduling and planning problems
  • One-player games
  • Two-player games (adversary search)

Most Search Problems Are NP-hard

• The generalizations of all the problems given earlier are NP-hard, and some of them are harder (e.g. planning is PSPACE-complete)

• Thus, improving on the "CS 100" algorithms is more a matter of the NP-solver tricks we talked about earlier

• Watch out, though: there are occasionally good polytime algorithms for specific cases (c.f. graph two-coloring decision problem)

• Phrasing the problem as an approximation problem sometimes helps, but not always by any means

• Ideally, a complete search is anytime: guaranteed to get better and better approximations to the solution

Complete Search

• A search algorithm is complete if it is guaranteed to terminate on any finite state-space graph with either a solution or failure

• The obvious complete algorithms are variants of depth-first, breadth-first and best-first search; state space is partial

  • Depth-first search for CSP satisfaction
  • Best-first A* search for optimal pathfinding
  • Iterative methods

• Heuristics play a huge role in reaching solution (or failure) sooner

Local Search

• Idea: give up completeness for performance; lean on heuristics more

• Implementation: * Make the state space total; move toward global optima by moving toward local optima

  • Satisfaction problems can usually be turned into optimization problems

  • CSPs (e.g. SAT)

  • Pathfinding (e.g. TSP)