Does a search algorithm need to learn from examples?

No. Many operate entirely from fixed rules and a supplied problem model.

Can two algorithms return different correct answers?

Yes. A problem may have several valid solutions, and algorithms can use different selection criteria.

What does completeness mean?

Under the stated assumptions, a complete method finds a solution when one exists; this does not imply that it is fast or cost-optimal.

AI Glossary / Graphs and symbolic AI / Beginner

Search algorithm

Definition

A search algorithm is a specified procedure for examining alternatives to find a target, a solution or a preferred candidate. In AI problem solving, it defines how possible states or action sequences are explored and when the search returns a result.

What it means

The problem description says what the system is trying to achieve and which possibilities exist. The search algorithm says how to explore those possibilities. Several algorithms can solve the same represented problem while using different amounts of time and memory or returning different solutions.

Breadth-first search explores by depth, depth-first search follows a branch before backtracking, and uniform-cost search prioritizes accumulated path cost. These are examples of distinct exploration rules, not interchangeable names for a single technique.

The wider term also covers methods for finding values in data structures and other search tasks. Here the emphasis is state-space search in AI. Choosing a method requires matching its assumptions to the problem rather than assuming that a familiar algorithm is universally best.

How it works

A typical state-space procedure begins with a search node representing the initial state. The node may also store a parent link, an action, a depth and an accumulated cost. These are properties of the search record, not necessarily of the underlying world state.

The algorithm selects a frontier node, tests or processes it according to its rules, and generates successors when expansion is required. It may use a queue, stack or priority queue to control selection. Repeated-state handling determines whether and when alternative paths to the same state need attention.

Stopping rules matter. An algorithm might stop at the first goal, continue until optimality is established, or return the best candidate found before a limit. These outcomes provide different assurances.

Evaluate completeness, solution quality, running time and memory use under stated conditions. For example, breadth-first search finds a shallowest solution with finite branching, but unequal action costs mean that shallowest need not mean cheapest.

Three practical examples

A maze solver uses breadth-first search when every legal move has the same cost and the aim is a fewest-move route.
A network planner uses a cost-based procedure when different links carry different nonnegative traversal costs.
A configuration tool uses a depth-oriented search with backtracking to explore assignments and reject incompatible partial choices.

Think of it this way

Think of inspecting a filing cabinet. One procedure checks the first page in every folder before looking deeper; another finishes one folder before moving to the next. The cabinet and target can remain the same while the inspection order changes.

The analogy illustrates exploration order only. Real search algorithms also need precise bookkeeping, duplicate handling and stopping conditions, which casual inspection may omit.

Worked example

Consider a directed graph with S to G costing 9, S to A costing 2, and A to G costing 2. Start at S and seek G.

Breadth-first search prefers a one-edge route to a two-edge route, so it can return S to G with cost 9. That is a shallowest solution but not the least-cost solution.

A standard uniform-cost procedure selects frontier nodes by their accumulated cost and checks for a goal when the lowest-cost node is removed. After expanding S, it has A at cost 2 and G at cost 9. It selects A and discovers G through A at cost 4. With appropriate handling of the improved route, it then selects that cost-4 goal and returns S to A to G.

Stopping immediately when G was first generated from S would produce the wrong cost-optimal conclusion. The example shows why the stopping rule is part of the algorithm, not a minor interface detail.

Illustrative case study

In a fictional project, Maple Paths changes its route model from equal-length links to measured travel costs. The existing breadth-first implementation continues returning routes with the fewest links, while the interface describes them as cheapest.

The team identifies the mismatch between objective and search strategy. It adopts an appropriate cost-based method and adds small examples with unequal link costs to its review set.

The case illustrates a modeling and algorithm-selection error, not a failure of breadth-first search to perform its actual task. No real travel-time improvement is claimed.

Common misconceptions and mistakes

Every search algorithm returns an optimal solution. Guarantees depend on the method, objective and assumptions.
Breadth-first search minimizes arbitrary path cost. It prioritizes depth, which matches cost only under suitable conditions.
A node and a state are identical concepts. Different search paths can create distinct nodes representing the same state.
The first generated goal is always safe to return. Some algorithms require a different stopping condition.
Using less memory always means faster search. Repeated exploration can exchange memory savings for extra work.
A timeout proves failure is unavoidable. It may only show that the allotted computation was insufficient.

Business use

For a business system, specify whether the required output is any feasible result, a good result within a deadline or a proven best result. That requirement should guide algorithm selection and user-facing status labels.

Measure both result quality and resource use on representative problems. Include difficult cases, duplicate paths and situations with no solution. Average response time alone can conceal important failures.

When adding heuristic estimates or changing pruning rules, revisit the guarantees. An implementation that resembles a named algorithm may no longer inherit its theoretical properties if key conditions have been altered.

Check your understanding

Why does breadth-first search return a cost-9 route in the example even though a cost-4 route exists?

Answer: The cost-9 route has one edge, while the cheaper route has two. Breadth-first search orders exploration by depth rather than by the unequal edge costs.

Related terms

Learn next

Run two exploration orders by hand on a five-node graph. Record the frontier after each expansion and state exactly when the goal test occurs. Compare the returned paths, total costs and number of stored nodes.

Sources

Russell and Norvig's search chapter slides, including node records, expansion order and algorithm properties: https://aima.cs.berkeley.edu/slides-pdf/chapter03.pdf

Relevant algorithm descriptions were reviewed. The three-edge example and Maple Paths case are original illustrations, not performance benchmarks.

Previous: Search Next: Search as a service