Search and pathfinding

Choose your learning level

BeginnerIntermediateAdvanced

Start with plain-language explanations. Switch levels at any time.

Beginner explanation

Search explores possible states to find a solution. A route planner, for example, compares paths between locations. The shortest path by distance may not be the fastest or safest, so first define what the search is minimizing.

Intermediate explanation

Breadth-first search finds a fewest-edge path in an unweighted graph. Uniform-cost search handles differing nonnegative edge costs. A* uses f(n) = g(n) + h(n), combining cost so far with an estimate of remaining cost.

Advanced explanation

An admissible heuristic never overestimates true remaining cost. With appropriate duplicate handling, A* can return an optimal path; graph-search implementations commonly require consistency or reopening improved nodes. Guarantees depend on assumptions, not the algorithm’s name alone.

PUT IT IN CONTEXT

A worked example

Route A–B–D costs 2 + 8 = 10; A–C–D costs 4 + 3 = 7. Both have two edges, so a fewest-edge search alone does not distinguish their costs. A cost-aware search prefers the route through C.

TRY IT YOURSELF

Practice the idea

Add a direct A–D edge costing 9. Which path wins by fewest edges, and which wins by lowest total cost?

Your working notes (not saved or sent)

Reveal the answer guide

Fewest edges chooses direct A–D with one edge. Lowest cost still chooses A–C–D at 7. This demonstrates why the objective and edge weights matter.

Go further: advanced challenge

Explain how a heuristic that overestimates the remaining cost could invalidate an optimality guarantee. Distinguish speed from correctness.

An open-ended discussion task. Explain your assumptions and evidence; there may be more than one defensible answer.

Continue the conversation

What part of this idea would you like to test or question? Compare your reasoning with the community.

Find related forum discussions ↗

Opens a topic search in the existing AstraCruz forum. Results depend on available posts; signing in may be required. No discussion or activity is fabricated.

Browse all forums