Are a state and a search node the same thing?

No. A node usually includes path-related information in addition to its represented state.

Can repeated states occur without loops?

Yes. Different branches can converge on the same state.

Should a repeated state always be discarded?

No. A better path, a different task objective, or missing state information can make that action incorrect.

AI Glossary / Graphs and symbolic AI / Intermediate

Repeated state

Definition

A repeated state is a state that a search procedure encounters more than once, usually through different paths or by returning through a cycle. The state describes the problem situation, while a search node also records information about how that situation was reached. Several different search nodes can therefore represent the same state.

What it means

Imagine navigating a building and arriving at the same intersection after taking two different corridors. If everything relevant to future travel is identical, both arrivals represent the same navigation state. Searching all possible continuations separately can repeat substantial work.

However, being in the same place is not always being in the same state. One arrival might include a collected key, a different battery level, or a later time. A search system can recognize repeated states correctly only when its state representation includes the information needed to determine future actions, outcomes, and costs.

How it works

When generating a successor, compare its state with states already on the current path or in a broader record of discovered states. A current-path check detects cycles. A global record can also detect different paths that converge on the same state without forming a cycle.

What happens next depends on the search algorithm and objective. For shortest-path search, a newly found route may have a lower accumulated cost, so the existing cost and predecessor information may need updating. Some algorithms may need to reopen a state previously expanded.

Avoid treating “seen before” as sufficient justification for discarding a node. The required pruning rule depends on which route has been retained and what the algorithm guarantees about it.

Three practical examples

Route planning: avoid repeatedly exploring the roads leaving a junction reached through several earlier routes, while retaining a cheaper newly discovered approach when necessary.
Puzzle solving: recognize a board arrangement reached by different move sequences instead of generating the same future moves from every copy.
Workflow planning: identify when different action orders produce the same relevant configuration, allowing later planning work to be shared where the model permits it.

Think of it this way

Think of keeping a notebook of intersections already explored. The notebook saves repeated visits, but only if it records the details that matter. If one visit occurred before collecting a key and another after, an entry containing only the intersection name would hide a meaningful difference. The notebook also needs more than a tick mark when route cost matters.

Worked example

Consider a directed graph with edges S to A costing 4, S to B costing 1, B to A costing 1, and A to G costing 2. All costs are positive, and the goal is the cheapest path from S to G.

Generating S's successors discovers A with accumulated cost 4 and B with cost 1. Expanding B subsequently discovers A again, this time with cost 1 + 1 = 2. The second occurrence is a repeated state, but it improves the known path to that state.

The direct route S to A to G costs 6. The route S to B to A to G costs 4. A procedure that permanently rejects every occurrence of a state after its first generation can lose the cheaper solution. A suitable cost-aware search updates A's recorded cost from 4 to 2 and its predecessor from S to B.

Now add an edge A to S costing 1. The path S to A to S returns to a state already on its own path and forms a cycle. With these positive costs and unchanged future possibilities, following that cycle adds cost without improving the route.

Finally, if visiting B also grants a permit required for entering G, state identity must include permit possession. “At A without permit” and “At A with permit” are different states, even though the map location is identical.

Illustrative case study

Fictional case: Rowan Puzzle Workshop compares two search implementations on a small rearrangement puzzle. One implementation stores every move sequence separately. The other records complete board configurations and the information its search algorithm needs about paths.

Students initially use a partial board description as the lookup key. Two configurations with different blank positions are incorrectly merged, changing which moves are possible. They correct the key before comparing search effort.

The case demonstrates that repeated-state handling requires a faithful representation. It reports no measured speedups; a global state table may be unaffordable for large searches.

Common misconceptions and mistakes

A repeated state is not necessarily a cycle. Two independent branches can meet at a state even when neither path repeats itself.

Do not confuse first discovery with cheapest arrival. The distinction is especially important when edge costs vary or a heuristic changes expansion order.

Another mistake is applying duplicate removal unchanged to a task that asks for every distinct path rather than one solution. Different paths to the same state may be part of the requested output. Pruning must preserve the information the task actually requires.

Business use

Repeated-state detection can reduce duplicated planning work in routing, configuration, and symbolic problem solving. Its value depends on how frequently paths converge and how much memory the retained state information consumes.

Teams should specify the state key, equality rules, cost-update behavior, and the conditions under which an expanded state may be revisited. Test a small example where a cheaper route arrives later, plus examples where superficially similar situations differ in a resource or permission. These checks reveal errors that a simple successful route demonstration may miss.

Check your understanding

In the example, A is first discovered at cost 4 and later at cost 2. Why must a shortest-path implementation consider the second arrival?

Answer: It improves the path to A and can improve every route extended from it. Rejecting it merely because A was already generated can preserve the more expensive solution.

Related terms

State space
Graph search
Uniform-cost search
Search node
cycle detection
duplicate detection
A*
path cost

Learn next

Draw a graph containing both a cycle and two branches that merge. Trace the difference between a current-path cycle check and a global discovered-state record. Then add unequal edge costs and study when the chosen search algorithm finalizes a state's best cost.

Search algorithm

Sources

Russell and Norvig, Solving Problems by Searching: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf Poole and Mackworth, Pruning the Search Space: https://www.cs.ubc.ca/~poole/aibook/3e/html/ArtInt3e.Ch3.S7.html Primary search material was read. Graph costs, permit variation, and fictional case are original examples.

Previous: Repeated measures design Next: Repeated survey