# 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

### 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)