Does uninformed search require a known goal location?

It requires a way to recognize a goal; the goal need not be named as one explicit state in advance.

Can it solve a problem optimally?

Yes. For example, breadth-first search is optimal for equal positive step costs under its usual conditions.

Generally it is informed because it uses a remaining-cost heuristic. With that heuristic set to zero, its priority reduces to uniform-cost search.

AI Glossary / Graphs and symbolic AI / Beginner

Uninformed search

Definition

Uninformed search explores a problem using its defined states, actions, goal test and, when relevant, action costs, without an additional heuristic estimating how close a state is to a goal. Breadth-first, depth-first and uniform-cost search are familiar examples.

What it means

A search problem tells the system where it starts, which moves are allowed and how to recognize success. An uninformed method uses that information but has no extra domain-specific guide such as a straight-line distance estimate or a learned prediction of remaining work.

Uninformed does not mean random or careless. These algorithms can follow precise, systematic rules. Nor does it mean that the system knows nothing: without an action model or a way to recognize a goal, there would be no defined search problem to solve.

Different uninformed methods prioritize different properties of the paths already generated. Their guarantees and resource demands differ, so the category does not imply that every member is complete, optimal or equally efficient.

How it works

A search maintains a frontier of candidates that have been discovered but not fully explored. Expanding a candidate generates possible successors. The frontier-selection rule defines much of the algorithm's behavior.

Breadth-first search explores shallow paths before deeper ones. Depth-first search follows a branch deeply before returning to alternatives. Uniform-cost search explores paths with smaller accumulated cost first. Iterative deepening repeats depth-limited searches with increasing limits, trading repeated work for reduced memory use compared with breadth-first search.

Repeated states need careful treatment. Graph-search methods can store reached states; tree-like methods may revisit the same state through different paths. Completeness and optimality depend on assumptions such as finite branching, step costs, depth limits and cycle handling. None of these methods receives a heuristic estimate of the remaining distance to the goal.

Three practical examples

A puzzle program uses breadth-first search to find a minimum-move solution when every move counts equally.
A workflow explorer uses depth-first search to inspect reachable configurations while managing cycles appropriately.
A route tool uses uniform-cost search to find a least-cost path without relying on a geographical distance heuristic.

Think of it this way

Think of exploring a well-defined maze using a fixed visiting rule but no clue about which corridor points toward the exit. You can still record junctions, avoid repeated work and recognize the exit when you reach it.

The analogy does not imply that every search physically walks through the environment. Many algorithms explore a stored or simulated model, where generating a distant alternative is a computation rather than a real journey.

Worked example

The visiting rule changes what is found first

Consider an invented tree. S has children A then B. A has child C, and C has goal child G1. B has goal child G2. Every edge has cost one, and successors are considered left to right.

With the goal tested when a node is removed from the frontier, breadth-first search examines S, A, B, C and G2. It returns S - B - G2, a two-edge solution. It discovers G1 while expanding C but still processes the shallower G2 first.

Depth-first search following A first examines S, A, C and G1. It returns a three-edge solution before reaching B. Both methods use only the tree and goal test. In this example, depth-first finds a goal after fewer examined nodes, while breadth-first returns the shorter solution. Neither outcome establishes a universal speed comparison.

Illustrative case study

The fictional CedarPuzzles team builds a small educational game. It begins with breadth-first search because each legal move counts equally and shortest solutions help generate useful hints. As puzzle sizes grow, the frontier consumes more memory.

The team compares iterative deepening on representative puzzles and considers whether a valid domain heuristic is available. It keeps the original small cases as references for checking solution length and handles repeated states explicitly.

The case illustrates a progression driven by requirements and scale. It does not claim that uninformed search is obsolete or that adding any heuristic automatically improves correctness or performance.

Common misconceptions and mistakes

Uninformed search ignores action costs. Uniform-cost search uses accumulated costs while remaining uninformed about future cost.
Every uninformed algorithm finds the shortest solution. Depth-first search generally does not provide that guarantee.
Blind search is the same as random search. Uninformed methods can be deterministic and systematic.

Business use

Uninformed search is useful for small problems, transparent baselines and situations where reliable heuristics are unavailable. Its explicit rules make it easier to explain which alternatives were considered and why.

Choose a method according to the required answer and available resources. Minimum-step, minimum-cost and any-valid-solution tasks are different. Monitor frontier size and repeated-state work as problems grow. A state description should retain the information needed to determine legal successors; merging states that only look similar can remove valid distinctions. When using a heuristic later, compare it against the baseline under the same task definition and stopping conditions.

Check your understanding

A search chooses the path with the smallest cost paid so far but has no estimate of the remaining cost. Is it necessarily informed search?

Answer: No. That is the priority used by uniform-cost search, an uninformed method. Known accumulated cost is not a remaining-cost heuristic.

Related terms

Learn next

Read breadth-first and depth-first search side by side. Trace the same small problem with both methods, recording frontier contents, stopping rules, path length and the number of examined nodes.

Sources

Stuart Russell and Peter Norvig, author-hosted chapter on solving problems by searching, uninformed strategies and repeated states: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf

The relevant primary descriptions and assumptions were reviewed. The six-node worked tree and fictional puzzle case are original. Its stated removal-time goal test is part of the example, because different stopping conventions can change the count of examined nodes.

Previous: Uninformative prior Next: Unintended side-effects