Is heuristic search always faster than uninformed search?

No. Weak or expensive guidance can provide little benefit or add overhead.

Can heuristic search guarantee an optimal result?

Some algorithms can under stated conditions on costs, heuristics, state handling, and termination. The category name alone does not guarantee it.

What is the difference between a heuristic and heuristic search?

The heuristic supplies guidance, such as a remaining-cost estimate. The search algorithm decides how to use that guidance while exploring and maintaining candidates.

AI Glossary / Graphs and symbolic AI / Intermediate

Heuristic search

Definition

Heuristic search uses problem-specific estimates or evaluation rules to guide which candidates a search explores. Instead of relying only on the basic structure of the problem, it uses information about which states or paths appear promising. The resulting behavior and guarantees depend on both the heuristic and the search algorithm.

What it means

A search problem can contain many possible action sequences. A heuristic helps allocate effort toward candidates that seem closer to a goal or otherwise more useful. In pathfinding, the estimate often concerns remaining cost; in other settings, evaluation may express a different notion of promise.
Heuristic search is a broad category, not one fixed algorithm. Greedy best-first search, A*, and various local-search methods use guidance differently. This entry emphasizes informed state-space search, where a frontier stores candidates and a heuristic influences their priority. It distinguishes a strategy for using estimates from the estimate function itself.

How it works

Define the states, legal actions, goal test, and objective. Add a heuristic that can be evaluated for candidate states or search nodes. The algorithm combines this information with its own selection and bookkeeping rules to decide what to expand next.
For example, greedy best-first search orders by estimated remaining cost h, while A* orders by accumulated cost g plus h. Graph-search versions also handle repeated states and improved routes. Appropriate heuristic properties can support guarantees, but the surrounding assumptions matter. Even a useful heuristic cannot correct an incomplete state representation or an incorrect action model.

Three practical examples

A navigation exercise uses a distance lower bound to guide A* toward a destination while checking obstacles through legal moves.
A symbolic-planning experiment estimates remaining work from a relaxed problem and compares search effort with an uninformed baseline.
A puzzle solver evaluates candidate arrangements to prioritize exploration, reporting both whether it solved the puzzle and the cost of the returned solution.

Think of it this way

Think of a librarian using clues about a book's likely location to decide which shelves to inspect first. The clues guide effort but do not replace checking the shelves. The analogy is limited because a formal search algorithm maintains explicit candidates and may have provable properties; an intuitive clue alone does not confer those guarantees.

Worked example

Consider directed edges S-A costing 2, A-G costing 8, S-B costing 4, and B-G costing 1. Let h(A) = 3, h(B) = 1, and h(G) = 0. These estimates do not exceed the actual remaining costs: A truly needs 8, while B needs 1.
After expanding S, A* assigns A the value g + h = 2 + 3 = 5 and B the value 4 + 1 = 5. Suppose its tie rule chooses A first. Expanding A produces a goal candidate at cost 10, but the algorithm does not stop merely because that candidate has been generated. B remains on the frontier with value 5.
Expanding B produces a better goal route with total cost 4 + 1 = 5. The search can then select that least-cost goal under the usual assumptions. The example shows that heuristic guidance does not require choosing the eventual best branch immediately. Retaining alternatives, applying the stopping rule correctly, and updating improved routes are part of the method. A premature stop at the first generated goal would return cost 10 instead.

Illustrative case study

In a fictional course project, Moss Search Lab compares an uninformed search with a heuristic version on a set of small planning problems. The team records how many candidates each method expands, but a reviewer also asks for returned solution costs and total computation time.
One heuristic takes substantial time to evaluate, so fewer expansions alone do not settle the comparison. The team adds evaluation overhead to its report and labels which runs have a proven optimality guarantee. This invented case illustrates a balanced experiment, not a claim that heuristics always improve runtime.

Common misconceptions and mistakes

Heuristic search is not synonymous with approximate search. A* can return optimal solutions under suitable conditions, even though its heuristic is an estimate. Conversely, using a highly accurate heuristic does not make every search strategy optimal.
Another misconception is that the first goal generated must be the best one. The worked example shows why the algorithm's stopping condition matters. Also avoid treating fewer expanded nodes as the only performance measure: memory, heuristic computation, duplicate handling, and the quality of the final result can all affect practical usefulness.

Business use

The approach matters when a project must search a large space of possible plans, routes, or configurations. Domain knowledge can guide exploration toward relevant regions without specifying the whole solution in advance. It is often useful to compare several heuristics and selection strategies before committing to one.
State the objective and any required guarantee explicitly. Validate small examples with known answers, then assess performance across representative instances. Track failures and resource limits separately from proven impossibility. If a learned heuristic is used, test how it behaves beyond its training examples and whether its numerical properties satisfy the guarantees being claimed.

Check your understanding

Why should the worked A* search continue after generating the goal at cost 10?

Answer: B is still a frontier candidate with value 5 and leads to a goal at cost 5. Generating one goal does not establish that no cheaper solution remains.

Related terms

Heuristic function
Greedy best-first search
Frontier
Consistency
Goal test
informed search
A*
admissibility
search complexity

Learn next

Trace the worked example with different tie-breaking rules and confirm that correct A* handling still compares the cheaper alternative. Then test a zero heuristic and a more informative one, recording total time as well as expanded nodes and solution cost.

Sources

Sources: Russell and Norvig, Informed search algorithms lecture slides: https://aima.cs.berkeley.edu/slides-pdf/chapter04a.pdf Poole and Mackworth, informed search: https://www.cs.ubc.ca/~poole/aibook/3e/html/ArtInt3e.Ch3.S6.html

Previous: Heuristic function Next: Hidden algebra