Use an informed search.

Compare complete trips

A delivery must travel from depot S to destination G. Each one-way road has a positive travel cost. The goal is the lowest total cost, not the smallest number of roads. A route with four inexpensive roads can beat one with three expensive roads.

The lab’s original map makes this concrete. S → A → C → G costs 2 + 2 + 2 = 6 units. S → B → D → C → G costs 1 + 2 + 0.5 + 2 = 5.5. Both routes are legal. An independent road checker can accept both while a cost comparison prefers the second. The positions in the drawing are for readability; they do not represent geographical distances or justify straight-line estimates.

If you enter here midway, recall three terms. A state is the current location. A successor is a location reached by one legal outgoing road. The frontier holds discovered locations whose next processing step is still pending. Search inspects alternatives before choosing a route; it is not the delivery itself driving down every inspected road.

Start with the cost you actually know

Uniform-cost search selects the frontier location with the smallest discovered cost from S. This accumulated cost is g(n), where n names a location. If g(B) = 1 and the road B → D costs 2, the candidate cost to D is 1 + 2 = 3.

This operation is called relaxing an edge: compare the candidate with the best cost stored for its destination. Store the candidate and its parent only when it is cheaper. If a location has not been discovered, any finite candidate is an improvement. Keeping one best record per location avoids storing every possible route in the frontier.

After expanding S, the uniform-cost frontier contains B at 1, X at 1 and A at 2. The fixed tie order chooses B before X. Predict this choice before pressing the step button. X is a dead end, but discovering that still requires selecting and expanding it. Inspecting no outgoing edges costs zero edge reads, yet it counts as an expansion.

Breadth-first search, introduced earlier, orders by the number of moves. It finds minimum-cost routes when each move has the same cost. Here the costs differ, so the number of moves and the total cost answer different questions.

Add an estimate of the remaining work

A heuristic h(n) estimates the cost still needed from n to G. A* orders the frontier by accumulated cost plus this estimate:

Read this as: the priority f at location n is the cost already discovered g plus the estimated remaining cost h. All three use the same travel-cost units. The estimate affects which location is considered next; it is never charged as an actual road cost.

For B under the consistent estimate, g = 1 and h = 4, giving f = 5. For A, g = 2 and h = 4, giving f = 6. A* examines B first. After B, D has g = 3 and h = 2, so f = 5. You can follow every addition in the frontier table. Uniform-cost search is the special case h = 0.

The lab supplies explicit lookup tables for h. They are teaching inputs, not learned predictions. More realistic heuristics can come from a simplified problem that removes constraints; a cheaper relaxed problem can provide a lower bound. Calculating an elaborate heuristic also has a cost. Fewer expanded locations alone does not prove a lower wall-clock time.

Two related checks on a heuristic

A heuristic is admissible when it never overestimates the true cheapest remaining cost. For this lesson all estimates are nonnegative and h(G) = 0. In the open map, the exact remaining cost from D is 0.5 + 2 = 2.5, so h(D) = 2 is admissible there. The unreachable X has no finite route cost; a finite estimate of 6 still does not overestimate infinity. Do not turn “unreachable” into zero.

Consistency is a local condition on every directed road:

Here u is the road’s starting location, v its destination, and c(u,v) its travel cost. Read it as: your remaining-cost estimate at u must not exceed the cost of that road plus your estimate at v. For D → C, the consistent table gives 2 ≤ 0.5 + 2. The audit lists any edge that violates this condition.

With h(G) = 0, applying these inequalities along a route makes consistency imply a lower bound on its cost. Admissibility alone does not require the estimates to fit smoothly together along every edge. The lab checks both properties against the entire tiny map instead of inferring them from one successful run.

The exact remaining costs come from a separate all-pairs dynamic-programming calculation. The search routine never reads those answers. They are affordable here because the graph has only seven locations; access to this teaching oracle is not an assumption that realistic search problems reveal their optimal solution in advance.

Why reopening matters

Choose the admissible-but-inconsistent table. Its estimate at A and C is zero, while B has h = 4.5 and D has h = 2.5. None exceeds the true remaining cost. However, D → C violates consistency because 2.5 is greater than 0.5 + 0.

Search first expands A at g = 2, then C at g = 4, discovering G at cost 6. Later it selects B and D. That route reaches C at g = 3.5. C has already been expanded, but its old route was more expensive. Reopening puts C back into the frontier with the improved cost, allowing G to improve from 6 to 5.5.

For finite graphs with nonnegative costs and an admissible heuristic with zero at the goal, A* can recover an optimal route by retaining best costs, reopening strict improvements, and stopping when the goal is selected. A graph-search variant that permanently ignores previously expanded locations needs a stronger condition such as consistency. The implementation choice is part of the guarantee; the name “A*” by itself does not tell you how repeat visits are handled.

A legal but more expensive answer

Now choose the overestimating table. It assigns B and D an estimate of 9. This makes the cheap branch look unattractive. A* selects A, C and then G, returning cost 6 before considering the cost-5.5 branch. The independent move checker accepts the returned route: all its roads exist.

The failure is about optimality, not feasibility. Overestimation removes this optimality guarantee; it does not imply every run must fail or every returned move is illegal. A learned heuristic would need the same distinction. Good predictions on a few maps do not establish a lower bound on all unseen maps.

The stopping rule matters too. G can be discovered through an expensive route before the frontier has ruled out cheaper ones. This lab stops when G is selected as the lowest-priority frontier entry, not when a road to G is first encountered. Even that stopping rule cannot repair an arbitrary overestimate.

Budget, evidence and a small project

An expansion selects a non-goal location and inspects its outgoing roads. The lab separately counts expansions, outgoing-edge records inspected, heuristic lookups, reopened locations and peak frontier size. Selecting the goal does not expand its successors, so it is allowed when the expansion budget has just been consumed. The route checker and exact oracle perform additional work outside the search counts. Sorting, rendering and other runtime overhead are also excluded.

At budget 1, the open map stops with alternatives still in the frontier. It has not established that G is unreachable. On the map with every incoming goal road closed, a sufficiently large budget lets the frontier empty. That establishes no route in this finite, completely specified graph. Neither result says anything about unmodelled real roads or a different environment.

For a guided comparison, capture the four priority rules on the same open map and explain two frontier selections. For an implementation project, reproduce the priority queue, improvement and reopening rules, then test a new weighted graph against a separately written exhaustive route enumerator. Include a legal but suboptimal result and a budget cutoff. For a decision brief, recommend a stopping rule and explain when you would return a route, request more computation or report uncertainty.

Exports contain up to four temporary runs and a bounded note. These are public practice experiments, not an independently assessed qualification. The lesson’s prediction and application questions provide feedback; human project review and learner pilots remain pending. Continue to the existing planning lessons through the course navigation, or return directly to any prerequisite without a completion lock.