State-Space Search

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)
Last modified: Tuesday, 3 June 2014, 10:49 AM