Does search require a large language model?

No. Many search algorithms use graphs, constraints or numerical states directly.

Can search handle uncertain outcomes?

Yes, but the representation and solution may need to include probabilities, observations or contingent decisions.

Is exhaustive search always necessary for correctness?

No. Valid pruning, mathematical bounds and suitable algorithms can avoid examining every candidate explicitly, under their stated assumptions.

AI Glossary / Graphs and symbolic AI / Beginner

Search

Definition

Search in AI is the exploration of possible states, actions or candidate solutions to find an outcome satisfying a goal or selection criterion. In classical problem solving, it often means finding a sequence of actions from an initial state to a goal state.

What it means

An AI system may know the actions it can take without knowing which sequence will solve its problem. Search examines alternatives using a representation of the task. Examples include routes through a network, arrangements of a puzzle and assignments that satisfy requirements.

Here the focus is problem-solving search, rather than searching the web for documents. Both involve finding something useful, but the objects being examined and the evaluation criteria differ.

Search is also distinct from learning. A system can search using a fixed model without learning anything from data. Conversely, learned estimates can help guide a search. Neither the presence of search nor the use of a heuristic implies human-like understanding.

How it works

Define the initial situation, available actions, predicted action results and the goal test. If solutions differ in quality, define a cost or other objective as well. The representation should preserve the details needed to decide whether a proposed solution can actually be carried out.

A search procedure generates candidate continuations and decides which to examine next. A frontier stores possibilities awaiting examination in many systematic methods. Expanding a candidate produces its successors; reaching a goal can yield a solution path.

Different strategies choose different exploration orders. Some prioritize shallow paths, some follow one path deeply, and others compare path costs or estimates of remaining work. Repeated-state handling can prevent redundant exploration or endless cycling.

Search can also operate on complete candidate solutions, improving them locally rather than constructing an action path. Under uncertainty, the required output may be a policy that responds to observations rather than one fixed sequence. The problem formulation determines what a solution must contain.

Three practical examples

A route planner examines connected locations to find a path satisfying access restrictions and a travel-cost objective.
A configuration assistant explores combinations of components until it finds one meeting compatibility and capacity requirements.
A puzzle solver searches possible legal moves while avoiding repeated arrangements already considered under its chosen strategy.

Think of it this way

Think of working through a maze on paper before walking it. You can explore possible turns in a representation and retain a route that reaches the exit.

The analogy stops where the map is incomplete or the maze changes. Searching a model does not guarantee that the represented route remains available in the world, and some AI search problems have no spatial interpretation at all.

Worked example

Suppose a directed route model has four relevant connections: S to A costs 2, A to G costs 8, S to B costs 4, and B to G costs 1. The start is S and the goal is G.

The path through A has total cost 2+8=10. The path through B costs 4+1=5. Both contain two actions and reach the goal, so a rule that looks only at the number of steps cannot distinguish their travel costs.

A search seeking any solution may legitimately return either route. A search claiming minimum total cost must use the costs appropriately and establish that no cheaper eligible route has been overlooked. In this complete four-edge example, comparing the two possible routes establishes that the route through B is cheaper.

If a bridge represented by B to G is unavailable in reality, the model needs updating. Correct search over an outdated graph does not make that route executable.

Illustrative case study

In a fictional project, Cedar Configure builds an assistant for selecting compatible equipment. Its search returns a low-cost combination that satisfies the encoded connection rules, but a reviewer notices that the model omitted a required power limit.

The team adds the missing constraint and reruns the search. The explanation distinguishes “best within the model” from “suitable for the intended installation.”

The case shows that search quality depends on both the exploration procedure and the problem representation. It does not establish any real product's performance or savings.

Common misconceptions and mistakes

Search always means web retrieval. AI also searches action sequences, assignments and other possibilities.
Finding a goal proves the solution is best. Optimality requires additional conditions.
A heuristic is a guarantee. It is usually guidance, with guarantees depending on its properties and the algorithm.
More search repairs an incorrect model. Missing constraints can remain missing however long the search runs.
Search must enumerate every possibility. Some methods prune or guide exploration, although their validity depends on the rules used.
Search and learning are interchangeable. They serve different roles and can be combined.

Business use

Use search when alternatives can be represented and evaluated against a useful goal. Start by defining what counts as success and whether an acceptable solution is enough or a proven optimum is required.

Set practical resource limits and make the stopping status visible. A timeout with no solution found is different from proof that no solution exists. Likewise, a feasible result and a proven best result should not share an ambiguous success label.

For deployed systems, monitor whether action costs, availability and requirements have changed. A search engine for business decisions is only as current as the model and data it uses.

Check your understanding

In the worked route model, why is “both routes have two steps” insufficient to choose the cheaper route?

Answer: Step count and total travel cost are different measures. The routes cost 10 and 5 even though each contains two actions.

Related terms

Learn next

Represent a small decision as states and actions. Write the goal test separately from the cost measure. Find two successful paths with different costs and explain what evidence is needed to call one optimal.

Goal test

Sources

Russell and Norvig's problem-solving and search chapter slides, covering formulation, state spaces and search strategies: https://aima.cs.berkeley.edu/slides-pdf/chapter03.pdf

Relevant formulation and search descriptions were reviewed. The route calculation and Cedar Configure case are original examples. They do not report benchmark results.

Previous: Seam carving Next: Search algorithm