## Definition **State space search** is the general framework for problem solving in Classical AI: a problem is defined as a set of *states*, *actions* that transition between states, an *initial state*, and a *goal test*. A solution is a sequence of actions reaching a goal state. ## Formal Components A search problem is the tuple $\langle S, s_0, A, T, G \rangle$: - $S$ — the set of all possible states. - $s_0 \in S$ — the initial state. - $A(s)$ — actions applicable in state $s$. - $T(s, a) \to s'$ — transition (often deterministic) producing the resulting state. - $G \subseteq S$ — goal states, or a predicate $\text{isGoal}(s)$. Optionally a **path cost** function $c(s, a, s')$ assigns numeric costs to action transitions. ## The Search Tree A search algorithm explores the state space by expanding nodes from a frontier. Each tree node tracks: the state, parent, action taken, path cost, depth. The same state can be reached by multiple paths — naive search creates duplicate work. A **closed list** (visited set) prunes already-explored states. ## Algorithmic Choices Two orthogonal axes: 1. **Order of expansion.** First-come-first-served (FIFO → BFS), last-in-first-out (LIFO → DFS), priority by cost (UCS) or heuristic (A*). 2. **Use of domain knowledge.** Uninformed search relies only on the problem definition; informed search uses a heuristic $h(s)$. ## Properties to Evaluate - **Completeness** — does the algorithm find a solution if one exists? - **Optimality** — does it find the *best* solution? - **Time complexity** — number of nodes generated. - **Space complexity** — maximum nodes stored at once. ## Related - [[Uninformed Search]] - [[Heuristic Search]] - [[A Star Algorithm]] - [[7 - Classical AI Notes Hub]]