Search and state

Prerequisites: Variables, loops, sets, and the idea of a graph. The chapter introduces queues and path cost.

• Separate a state from the path used to reach it.
• Explain why the first discovered goal can be too expensive.
• Trace a priority queue and reconstruct a cheapest path.

A problem needs a representation

Suppose a robot must move a parcel from room S to room G. A useful model needs a set of states, an initial state, legal actions, a transition rule, a goal test, and a cost. A state might contain the robot’s room, whether it holds the parcel, and which doors are locked. Keeping only the room would be insufficient if carrying the parcel changes which moves are legal.

Two histories may be merged into one state only when the retained information is sufficient to determine future actions, transitions, and costs. If a discount depends on which rooms have already been visited, the visited set belongs in the state. Representation is a correctness decision before it is a performance decision.

A graph makes the model explicit: vertices represent states and directed edges represent actions. A path is a sequence of edges. Its cost is the sum of their costs. Finding any goal and finding a cheapest goal are different tasks. This chapter assumes a finite graph with nonnegative edge costs and a reachable goal.

The frontier is unfinished work

Breadth-first search stores newly discovered states in a FIFO queue. With equal-cost edges, exploring by depth finds a path with the fewest edges. Uniform-cost search instead removes the frontier entry with the smallest accumulated cost, g. A priority queue implements this choice. With nonnegative costs, a cheapest current entry can be finalized when it is removed, provided stale entries are skipped.

A* adds a heuristic h, an estimate of remaining cost, and prioritizes f=g+h. A consistent heuristic satisfies h(u)≤cost(u,v)+h(v) for every edge, with h(goal)=0. This condition supports finalizing a state on expansion. An admissible heuristic never overestimates remaining cost; if it is inconsistent, a graph implementation may need to reopen states. See Berkeley CS 188’s informed-search notes for the distinction and proof.

Trace before you code

Use these directed edges: S→A costs 5, S→B costs 2, B→A costs 1, A→G costs 2, and B→G costs 8. At S, the frontier contains B:2 and A:5. Removing B discovers a cheaper route to A, with cost 3, and a route to G, with cost 10. Removing A:3 improves G to 5. The old A:5 entry remains in the heap but is stale. The cheapest goal path is S→B→A→G, costing 2+1+2=5.

Notice the two meanings of “visited.” A state can be discovered and placed on the frontier before its cheapest route is known. Marking it permanently closed at first discovery would suppress the improvement to A. The following implementation keeps the best discovered cost separately from queued work.

from heapq import heappush, heappop

def cheapest_path(graph, start, goal):
    frontier = [(0, start)]
    best = {start: 0}
    parent = {start: None}
    while frontier:
        cost, state = heappop(frontier)
        if cost != best[state]:
            continue
        if state == goal:
            path = []
            while state is not None:
                path.append(state)
                state = parent[state]
            return cost, path[::-1]
        for neighbor, edge_cost in graph.get(state, []):
            if edge_cost < 0:
                raise ValueError('Nonnegative costs required')
            candidate = cost + edge_cost
            if candidate < best.get(neighbor, float('inf')):
                best[neighbor] = candidate
                parent[neighbor] = state
                heappush(frontier, (candidate, neighbor))
    return None

graph = {'S': [('A', 5), ('B', 2)],
         'B': [('A', 1), ('G', 8)], 'A': [('G', 2)]}
assert cheapest_path(graph, 'S', 'G') == (5, ['S', 'B', 'A', 'G'])

The heap breaks equal-cost ties using the state string. Arbitrary state objects would need a separate numeric tie breaker. This is plain Python 3 code to run locally; the page does not execute it.

What the guarantee does and does not cover

On a finite graph, the heap implementation has a conventional bound of O((V+E) log(V+E)), with O(V+E) worst-case auxiliary storage including stale entries. An implicit state graph can itself be exponential in the number of problem variables. A better heuristic may reduce exploration without changing that worst-case difficulty.

The returned path is optimal for the supplied graph and costs. If a doorway is missing from the model, or travel time changes while the robot moves, that proof does not establish an optimal real journey. Separate an algorithm’s theorem from the fidelity of its input model. Then complete the exercise below with a different graph, without running the code first.

Practice exercise

Use the directed edges S→A:4, S→B:1, B→A:1, A→G:3, B→G:7. Trace uniform-cost search from S to G. Record each popped state, best cost, and predecessor. Then use h(S)=4, h(A)=3, h(B)=4, h(G)=0. Check consistency on all five edges and trace A*.

Compare with the worked solution

Uniform-cost search pops S:0, B:1, A:2, then skips the stale A:4 entry, and pops G:5. The path is S→B→A→G. A* priorities begin S:4, then B:5 and A:7. Expanding B improves A to g=2, f=5 and discovers G with g=8. Expanding A improves G to g=5, f=5. Pop G and stop. The consistency inequalities are 4≤4+3, 4≤1+4, 4≤1+3, 3≤3+0, and 4≤7+0. All hold. The first generated G had cost 8; stopping at generation would return the wrong answer.

Check your understanding

In the exercise, what is the cheapest cost from S to G?

• 4
• 5
• 7
• 8

Check the reasoning

S→B→A→G costs 1+1+3=5. The direct discovery through B costs 8.

Why does the algorithm skip the old A:4 queue entry?

• A is a goal.
• Its heuristic is zero.
• A cheaper route to A has already been recorded.
• A has no outgoing edges.

Check the reasoning

The queue can contain several entries for a state. Compare a popped cost with the best recorded cost before expanding it.

Learn AI curriculum · Next: Probability and evidence