Does state-space search require a neural network?

No. It can operate entirely from explicit states, actions, and rules.

Must the full graph exist in memory?

No. Successor states can be generated during exploration.

Is the first solution always best?

No. That depends on the strategy, objective, and applicable correctness conditions.

AI Glossary / Graphs and symbolic AI / Intermediate

State-space search

Definition

State-space search is the process of exploring possible states and transitions to find a solution to a modeled problem. It starts from an initial state, considers available actions, and seeks a state that meets a goal condition. Different search strategies decide which candidate to examine next, how to handle repeated states, and when a solution can be accepted.

What it means

The method turns a question such as “How can we complete this workflow?” into a structured problem: what situations can occur, what actions are permitted, and what counts as success? A solution is usually an action sequence that connects the initial situation to a goal.
Search is distinct from defining the model. A sophisticated algorithm cannot repair an omitted prerequisite simply by exploring more carefully. It is also distinct from learning: a search procedure can work with rules supplied directly by a designer, although learned information can help guide the exploration.

How it works

Represent the initial state and place it on a frontier of candidates. Repeatedly select a candidate according to the search strategy, check its goal status at the appropriate stage, and generate permitted successors. Store enough parent information to reconstruct the selected action sequence.
Breadth-first search prioritizes shallow paths; uniform-cost search prioritizes accumulated cost; informed methods can also use estimates of remaining work. Graph-search implementations record relevant information about encountered states to manage duplicates. Their guarantees depend on details such as costs, state-space size, heuristic properties, and stopping rules. There is no single guarantee that applies to every method called state-space search.

Three practical examples

A puzzle application searches legal moves from a scrambled configuration to a target arrangement.
A workflow prototype searches valid task orders while respecting prerequisites.
A robot planner searches modeled movements and resource changes to reach a destination under stated constraints.

Think of it this way

Think of exploring alternative routes through a decision map while keeping notes on unfinished possibilities. The next route examined depends on your exploration rule. The analogy is limited because states may encode complex configurations, and the map may be generated as needed rather than supplied as a complete drawing.

Worked example

Consider an original document-preparation workflow with three tasks: draft D, review R, and format F. Each task can be completed at most once. Review requires the draft; formatting can happen at any time. The goal is to complete all three tasks.
Represent a state by the set of completed tasks. The start is the empty set. Although three Boolean completion variables have eight possible combinations, states containing R without D are unreachable under the prerequisite. Six reachable states remain: empty, D, F, DF, DR, and DRF.
From empty, the legal actions are draft and format. Choosing draft reaches D, where either review or format is legal. Choosing format first reaches F, where drafting is the only next task. Search therefore finds three valid complete orders: D - R - F, D - F - R, and F - D - R.
Assign costs of two to drafting, three to review, and one to formatting. Every valid order costs 2 + 3 + 1 = 6. In this small model, both the action count and total cost are identical across complete orders, although the intermediate states differ.
Now add a bundled action available only at the start that completes all three tasks for cost eight. Breadth-first search can prefer this one-action solution because it is shallowest. Uniform-cost search should return a cost-six solution when implemented with nonnegative costs and a goal test on removal of the cheapest frontier candidate.
This also explains why stopping as soon as any goal is generated can be wrong for cost optimization. The cost-eight goal is visible immediately, while cheaper routes are still unfinished. Searching further is necessary to establish the lower-cost result.
Finally, the state DF can be reached by D - F or F - D. These are different paths to the same completed-task set. A graph-search implementation can use that fact to avoid repeating identical future work, provided the state representation really contains all information affecting future actions and costs.

Illustrative case study

In a fictional publishing-tool project, a team builds a workflow assistant using state-space search. During review, it discovers that formatting before review sometimes creates additional revision work. The original completed-task set does not represent that distinction.
The team updates its cost model or state representation before comparing search algorithms. It then tests returned plans against the workflow rules. This fictional case illustrates why model adequacy must be checked alongside search performance; it does not describe a deployed system or a measured productivity gain.

Common misconceptions and mistakes

State-space search is not always exhaustive enumeration. Some methods explore only part of the space before finding an answer. Equally, finding an answer does not prove it is cheapest unless the method's conditions support that conclusion.
Do not equate a state with the entire path taken to reach it unless history matters to the problem. Do not discard every repeated state blindly when a newly found path has a better cost. Finally, a plan valid in a simplified model may still fail when real-world conditions differ from its assumptions.

Business use

The approach helps teams make planning rules explicit and inspect why a proposed action sequence is permitted. It is useful for explaining dependencies, alternative routes, and tradeoffs between finding any feasible solution and proving a cost-optimal one.
For a practical evaluation, record solution validity, total modeled cost, runtime, and memory use. Separate failures caused by an incomplete model from failures caused by resource limits or search strategy. A small representative problem with a known answer is particularly useful for checking basic behavior before scaling up.

Check your understanding

Why can the one-action bundled workflow be worse than a three-action workflow?

Answer: It costs eight instead of six. Minimizing action count and minimizing total cost are different objectives.

Related terms

Learn next

Next, change the bundled action's cost from eight to five. Trace the uniform-cost frontier until a goal is selected. Explain why the bundle now wins on both total cost and action count, without changing the definition of the search problem's goal.

Frontier

Sources

Primary sources: Berkeley CS188, State Spaces and Search Problems: https://inst.eecs.berkeley.edu/~cs188/textbook/search/state.html ; and Uninformed Search: https://inst.eecs.berkeley.edu/~cs188/textbook/search/uninformed.html . The task-set workflow, bundle comparison, and modeling caveat are original examples.

Previous: State space modeling Next: State-value function