Must the graph already be stored?

No. Successor rules can generate the relevant parts of an implicit state space during exploration.

Is an explored-state set enough for every search?

No. Some strategies need costs, frontier updates, or reopening rules to handle improved paths correctly.

Does graph search always find the best solution?

No. Optimality depends on the strategy, the meaning of cost, and conditions such as those required by uniform-cost search or a particular heuristic algorithm.

AI Glossary / Graphs and symbolic AI / Intermediate

Graph search

Definition

Graph search is a family of problem-solving procedures that explore states and transitions while accounting for states reached more than once. A search maintains candidate paths and records relevant information about previously encountered states, helping avoid unnecessary repeated work. The order in which candidates are explored depends on the chosen search strategy.

What it means

Many different action sequences can lead to the same situation. In a route problem, two routes may reach the same junction; in a puzzle, different moves may return to a previous arrangement. Treating every path as wholly unrelated can multiply the work and allow cycles to dominate exploration.
Graph search recognizes these shared states. It distinguishes a state, representing a situation, from a search node, which may also store the path, parent, and cost used to reach that situation. The state space can be implicit: the algorithm can generate successors as needed without receiving a complete graph in advance.

How it works

Start with the initial state on a frontier of candidates. Repeatedly choose a candidate, apply the goal test at the appropriate point for the algorithm, and generate legal successor states. Use a reached-state table or related bookkeeping to decide whether a successor is new, redundant, or a better route to a known state.
Breadth-first search chooses shallow candidates, while uniform-cost search prioritizes accumulated path cost. Heuristic searches use additional estimates. Duplicate handling must match the strategy: a newly discovered cheaper path may require updating a frontier entry or reopening a state. Simply discarding every previously seen state is not a universal recipe for correct cost-sensitive search.

Three practical examples

A route planner explores road junctions while retaining the best known travel cost to each junction.
A puzzle solver recognizes arrangements it has already reached, reducing repeated exploration of reversible moves.
A workflow planner represents each relevant task configuration as a state and searches for a legal sequence reaching a completion condition.

Think of it this way

Think of exploring a building while keeping a notebook of rooms already reached and the routes used to reach them. Recognizing the same room prevents treating every entrance as a new destination. The analogy is limited because the correct state may include more than location: keys held, time, permissions, or unfinished tasks can make two visits different search situations.

Worked example

Consider directed edges S to A with cost 5, S to B with cost 1, B to A with cost 1, and A to G with cost 1. The initial state is S and the goal is G. All edge costs are positive.
After expanding S, uniform-cost search has candidates A at cost 5 and B at cost 1. It expands B first. The new route S-B-A reaches A at cost 2, which is better than the earlier cost 5. The search must retain that improvement rather than reject A merely because A was encountered already.
Next it expands A using cost 2 and reaches G at cost 3. The route S-A-G would cost 6. With appropriate goal handling and the usual nonnegative-cost assumptions, uniform-cost search returns the cheaper route S-B-A-G. A faulty implementation that permanently marks A on first discovery and refuses its improvement could return the more expensive route. The example separates recognizing a duplicate state from deciding what to do with a better path to that state.

Illustrative case study

In a fictional simulation, Harbor Lab models a robot that must collect a key before entering a locked room. The first search implementation stores only the robot's location as the state. It mistakenly treats a visit with the key as equivalent to an earlier visit without it.
The team adds key possession to the state representation and reruns small, manually checked examples. Duplicate detection then compares the situations that actually determine available moves. The invented case illustrates state-design correctness; it does not claim a particular runtime improvement or deployable robot capability.

Common misconceptions and mistakes

Graph search is not synonymous with shortest-path search. Its behavior depends on frontier ordering, duplicate policy, goal handling, and problem assumptions. Depth-first graph search and uniform-cost graph search do not offer identical guarantees.
A repeated location is not necessarily a repeated state. If future actions depend on fuel, inventory, or time, those facts may need representation. Conversely, including irrelevant history can prevent equivalent states from being recognized. Bookkeeping also consumes memory, so avoiding repeated computation does not make graph search free of resource limits.

Business use

Graph search supports planning, navigation, scheduling, puzzle solving, and dependency exploration when situations and transitions can be modeled explicitly enough. Its business value often comes from systematically finding a valid sequence and explaining that sequence through the recorded path.
Define what counts as the same state, what makes an action legal, and what cost or success condition matters. Validate small examples with known answers before scaling. If a search runs out of time or memory, distinguish that outcome from proof that no solution exists. Any completeness or optimality claim should state the algorithm and assumptions that support it.

Check your understanding

Why must the route through B update A's recorded cost in the worked example?

Answer: A was first reached at cost 5, but S-B-A reaches the same state at cost 2. Rejecting that improvement would discard the route that leads to the goal at total cost 3.

Related terms

State space
Frontier
Breadth First Search
Uniform-cost search
Heuristic search
search node
reached set
cycle detection
path cost

Learn next

Trace breadth-first and uniform-cost search on a small graph with unequal edge costs. Record the frontier and best known cost after each expansion. Then add a state variable such as key possession to see why duplicate detection depends on a correct representation.

Sources

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach, problem-solving and search chapter: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf AIMA search lecture slides: https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter03.pdf

Previous: Graph representation Next: Graph semantics