A*: Costs, Heuristics and Paths

g(v) is the best currently known cost from the start to v. h(v) estimates the cost from v to the goal. A* prioritises the smallest f(v)=g(v)+h(v). When examining an edge, calculate a candidate new g and retain a better value and predecessor when one is found. The heuristic alone is not the complete priority.

In this lesson’s directed graph, S→A costs 4, S→B 1, B→A 2, B→C 5, A→G 4 and C→G 1. Use h(S)=5,h(A)=4,h(B)=4,h(C)=1,h(G)=0. Ties in f use alphabetical vertex order. These edge and heuristic conventions make the example’s trace reproducible.

Scroll the diagram to see the full view.

After expanding S, B has g=1,f=5 and A has g=4,f=8, so select B. B improves A to g=3,f=7 and discovers C with g=6,f=7. Select A alphabetically, discovering G at g=7,f=7. C is then selected before G under the tie rule; its route to G also costs 7, so no strict improvement is made.

When G is removed as the lowest-priority frontier item under the stated assumptions, its predecessor chain gives S→B→A→G, cost 7. The first discovery of G is not generally a sufficient termination condition. Old priority-queue entries can remain after a g update; the code skips entries whose priority no longer matches the best known value.

An admissible heuristic never overestimates the true remaining minimum cost. Consistency additionally requires h(u)≤cost(u,v)+h(v) for each edge and h(goal)=0. The displayed heuristic satisfies these conditions. A graph search that permanently closes vertices needs care with inconsistent heuristics; the example allows improved vertices to be queued again rather than assuming every heuristic is safe.

Costs are non-negative, and the function rejects negative edges. If h is zero everywhere, prioritising g reduces to Dijkstra-style search. A better informative heuristic can reduce explored work, but heuristic computation also has a cost. OCR requires understanding and tracing A*; this small implementation makes the state updates visible without making memorisation of its Python syntax a requirement.

from heapq import heappop, heappush

def a_star(graph, heuristic, start, goal):
    if any(cost < 0 for edges in graph.values() for cost in edges.values()):
        raise ValueError("non-negative edge costs required")
    best = {start: 0}
    previous = {}
    frontier = [(heuristic[start], start)]
    while frontier:
        priority, vertex = heappop(frontier)
        if priority != best[vertex] + heuristic[vertex]:
            continue
        if vertex == goal:
            path = [goal]
            while path[-1] != start:
                path.append(previous[path[-1]])
            return list(reversed(path)), best[goal]
        for neighbour, cost in graph.get(vertex, {}).items():
            candidate = best[vertex] + cost
            if candidate < best.get(neighbour, float("inf")):
                best[neighbour] = candidate
                previous[neighbour] = vertex
                heappush(frontier, (candidate + heuristic[neighbour], neighbour))
    return None

graph = {"S": {"A": 4, "B": 1}, "B": {"A": 2, "C": 5},
         "A": {"G": 4}, "C": {"G": 1}, "G": {}}
heuristic = {"S": 5, "A": 4, "B": 4, "C": 1, "G": 0}
print(a_star(graph, heuristic, "S", "G"))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.