Cost-Aware Search

1Path cost is the objective

A search problem so far scored a plan by its length — the number of edges. Real problems price each edge: a weight is minutes of driving, joules of battery, rupees of toll, or any other quantity that adds along a route. The path cost g(n) is that running sum from the start to n, and the object of cost-aware search is the plan whose total is smallest, not the plan with the fewest moves.

The two objectives disagree the moment weights are unequal. On the lesson graph the direct edge from S to G is the shortest plan by hops — one move — and not the cheapest by cost; the two-edge route through B doubles the moves and still undercuts it at 8 against 10. Hop count is just path cost with every edge priced 1, which is why breadth-first search is the special case and uniform-cost search the general one.

Figure. Three complete routes to the same goal. The route via A opens with the cheapest edge on the graph (2) and still totals dearest at 11; the winner is the route whose completed total is smallest — 8 via B. Only completed totals compare.

2Uniform-cost search

Uniform-cost search keeps a frontier of partial paths and always expands the one with the smallest path cost g so far. Cheapest-first is not an optimisation of the algorithm; it is the algorithm: pop anything else and the first path found to a node stops being its cheapest.

Two details carry the correctness. The frontier is a priority queue ordered by g, so a cheap first edge cannot commit the search to a dear route — the route through A opens promisingly at 2 and is quietly overtaken once its total passes 8. And the goal test happens when a node is popped, not when it is first generated: G is generated at cost 10 through the direct edge, but stopping there would lock in the wrong answer while the total of 8 was still in the queue.

Under one assumption — no edge cost is negative — the first time any node pops, its recorded g is the cheapest possible, so the search may settle it permanently and stop the moment the goal pops. That assumption gets its own scrutiny in the negative-costs lesson.

Coding lab. Uniform-cost search on the lesson graph runs in the app, with checks on your output.

3Dijkstra on an implicit graph

Uniform-cost search is Dijkstra's algorithm — the same priority queue, the same settle-on-pop — with one change of setting. Dijkstra as taught in an algorithms course walks a graph handed to it as an adjacency list. An AI planner cannot be handed the graph: the states of a puzzle, a logistics problem or a configuration space number beyond storage, so the graph exists only as a successor function that, shown a state, returns its neighbours and their costs on demand.

That changes what governs the running time. On an explicit graph the cost is about (V + E) \log V with a binary heap. On an implicit graph the search only ever materialises the ball of states cheaper than the optimum C^*, and with branching factor b and minimum edge cost \varepsilon that ball holds on the order of b^{1 + \lfloor C^*/\varepsilon \rfloor} nodes. The exponent is a budget: it counts how many cheapest edges fit under the optimum, so fine-grained costs — a small \varepsilon — inflate the space even when the graph and the answer are unchanged.

Figure. The same planner and the same optimal cost: halving the minimum edge cost from 1 to 0.5 deepens the cost ball from 10⁵ to 10⁹ nodes. The bars are on a log scale — each rung of the ladder is a factor of ten.

4Why settled-when-popped is safe

Uniform-cost search makes a strong claim: the first time a node pops, its g is final — no reopening, no second thoughts. The proof is a cut argument, and it is worth holding in full because every variant question you will meet later (negative edges here, inconsistent heuristics in A*) is answered by asking which line of it broke.

Suppose node n pops with cost g(n), and some cheaper path to n exists. That path starts inside the settled set and ends outside it, so somewhere it crosses the boundary at a frontier node f. The queue popped n rather than f, so g(f) \ge g(n). The rest of the rival path runs from f to n through edges that are each non-negative, so it can only add: the rival totals at least g(f), which is at least g(n). The rival is no cheaper — contradiction, and the pop is safe.

Read the chain once more, slowly: it uses non-negative edges exactly once. That single use is the hinge the negative-costs lesson swings on.

Figure. n has just popped. Any rival route to n must leave the settled set through some frontier node f; the queue preferred n, so g(f) ≥ g(n), and the dashed remainder only adds. No rival can be cheaper — settling n is safe.

The cut argument

1. Cross the boundaryAny rival path to n starts in the settled set and must exit it through some frontier node f.
2. Pop order bounds fn popped first, and the queue is ordered by g, so g(f) ≥ g(n).
3. Edges only addFrom f onward every edge is ≥ 0, so the rival totals ≥ g(f) ≥ g(n): never cheaper.

5Cost models: what the weights mean

The algorithm never asks what a cost is; the engineer must. A weight is a claim that the quantity adds along a route and that smaller is better — time, energy, money and risk all qualify once they share a unit. Mixing units without conversion, or folding two objectives into one number without deciding the exchange rate, produces plans that are optimal for a question nobody asked.

One conversion is used everywhere in production systems: probabilities multiply along a route, and −log turns multiplication into addition. Price each edge at −log p and the cheapest path is the most probable one — this is how speech decoders, spell correctors and translation lattices run Viterbi-style decoding as plain shortest-path search.

Keep the cost model separate from the heuristic in your head: the cost is the terrain, part of the problem's definition; a heuristic — the informed-search lesson's subject — is advice about the terrain, and only the advice is allowed to be wrong.

6The frontier in practice

Between the textbook and a working planner sits one data-structure decision. The classic presentation of Dijkstra assumes a priority queue with decrease-key: when a cheaper path to a queued state appears, reach in and lower its key. Binary heaps — including Python's heapq — do not support that operation, and the production idiom is not to want it: push a duplicate entry with the better cost and let the stale one surface later.

The guard that makes duplicates safe is one comparison at pop time: if the popped g is worse than the best g recorded for that state, the entry is stale — skip it. Every skipped pop costs one heap operation; in exchange the code needs no handles into the middle of the heap, and the whole queue stays a few lines of standard library.

The other half of the frontier is the explored set, keyed by the state itself — which quietly assumes states are hashable and canonical. That assumption is load-bearing enough to get its own lesson: two encodings of the same situation that hash differently will both be expanded, and the search does every piece of work as many times as you failed to canonicalise.

Figure. A cheaper path to a queued state is pushed as a new heap entry; nothing reaches in to decrease-key. At pop, if that g exceeds the best recorded g for the state, the entry is stale — skip it. Stale pops change no answer.

Lazy deletion

1. Push duplicatesA cheaper path to a queued state is pushed as a new entry; nothing reaches into the heap.
2. Guard at popIf the popped g exceeds the best recorded g for that state, the entry is stale.
3. Skip and continueStale pops cost one heap operation each and change no answer.

UCS with lazy deletion (heapq)

import heapq

def ucs(start, goal, successors):
    frontier = [(0, start)]          # (g, state); duplicates allowed
    best = {start: 0}                # cheapest g seen per state
    while frontier:
        g, s = heapq.heappop(frontier)
        if g > best.get(s, float('inf')):
            continue                 # stale entry - lazy deletion
        if s == goal:
            return g
        for nxt, w in successors(s):
            g2 = g + w
            if g2 < best.get(nxt, float('inf')):
                best[nxt] = g2
                heapq.heappush(frontier, (g2, nxt))

7When search beats learning

Cost-aware search assumes you hold the problem exactly: the states, the successor function and every edge cost are known and trusted. Where that holds — puzzles, routing on a mapped warehouse, dependency resolution, configuration — search computes the optimum directly, with a proof, and a learned policy could only approximate the same answer while adding data needs, training cost and failure modes.

Learning earns its cost precisely where the givens fail: the transition model is unknown (what does this action actually do?), the costs must be estimated (how long does this road take at 6 pm?), or the state is only partially observed. There, estimation is not overhead — it is the task.

The frontier of the field is mostly the hybrid strip between the two: a learned model predicts costs or ranks successors, and classical search runs on top of the predictions — traffic-trained travel times feeding an exact shortest-path engine, or game-tree search guided by a learned evaluation, which is the AlphaGo shape. The search half keeps the guarantees; the learned half keeps the model honest about the world.