State space search involves finding a path from the initial state of a search problem to a goal state.

To do this, we build a search graph, starting from the initial state (or the goal state), and we expand a state by applying the search operators to that state, generating ALL of its successor states. These successors are in the next level down of the search graph.

The order in which we choose states for expansion is determined by the search strategy. Different strategies result in (sometimes masively) different behaviour.

Can be represented by Graphs, search trees or tree.
It can use differentsearchalgorithmsthat canbe informedor notinformed.

Not Informed: Systematic exploration of whole tree until the goal is found.

• Depth- first
• Breadth-First,
• and Iterative-Deepening depth-first.

Informed: Uses heuristic measure of goodness of a node, e.g. estimated distance remaining to the goal from node.

• Hill-Climbing
• Best-First
• Beam
• Branch&Bound
• A* search algorithm

A heuristic that never overestimates the cost to the goal are said to be admissible.
Using a more informed heuristic is guaranteed to expand fewer nodes of the search space (ie. be more computationally efficient).