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