Search & A*

Formulating the problem

Our course uses one teaching map for every algorithm (costs are invented classroom values, not real distances):

• States: cities. A search state keeps only the details needed for planning. That simplification is called abstraction; weather and population are dropped.
• Successor function: drive along a road to a connected city, with cost = road weight.
• Start state: Astana. Goal test: state == Almaty.
• Solution: a sequence of actions from START to GOAL. The optimal solution has the lowest total path cost.

State-space graph vs search tree

In the state-space graph each state appears once. A search tree is a "what-if" tree of plans: the root is the start, children are successors, and each tree node stands for a whole path. The same city can appear many times in the tree. Neither is usually built in full; we grow the tree only as needed.

The frontier (or fringe) holds the partial plans waiting to be explored. Every algorithm in this chapter follows the same loop, and they differ in exactly one thing: which frontier node to expand next.

function SEARCH(problem, strategy):
    frontier ← { path containing only START }
    loop:
        if frontier is empty: return failure
        path ← strategy.choose(frontier)        # ← the only difference!
        if GOAL-TEST(last state of path): return path
        for each successor s: add path + [s] to frontier

Worked example: A* by hand

Heuristic values from the practical: h(Astana)=10, h(Karaganda)=9, h(Pavlodar)=9, h(Balkhash)=5, h(Shymkent)=3, h(Semey)=6, h(Taldykorgan)=2, h(Almaty)=0.

Notice the goal test happens when a node is expanded, not when it is generated. If A* stopped as soon as it saw Almaty, a cheaper route still waiting in the frontier could be missed.

Heuristics: admissible and consistent

A heuristic h(n) estimates the remaining cost from n to the goal. It is extra problem knowledge, like a straight-line distance on a map.

An admissible heuristic is optimistic: it never overestimates. Every consistent heuristic is also admissible. Check our table against the true remaining costs:

It is also consistent: e.g. Karaganda → Balkhash: 9 ≤ 5 + 5 ✓, and Astana → Karaganda: 10 ≤ 2 + 9 ✓ (all 9 edges pass).

Why A* is optimal (proof sketch from the lecture)

Let A be an optimal goal and B a suboptimal goal, both reachable, and h admissible. Some ancestor n of A is in the frontier while B waits there.

1. f(n) = g(n) + h(n) ≤ g(A) = f(A), because h never overestimates the remaining cost.
2. f(A) = g(A) < g(B) = f(B), because h = 0 at goals and B is suboptimal.
3. So f(n) < f(B): every ancestor of A, and then A itself, is expanded before B. A* returns A.

Special cases: if h(n) = 0 everywhere, f = g and A* becomes UCS. If we use only h (ignore g), we get greedy best-first search, which can be fast but is not optimal. An overestimating heuristic may speed things up but loses the guarantee.

Comparing the strategies

b = branching factor, d = depth of the shallowest goal, m = maximum depth, C* = optimal cost, ε = smallest step cost.

Iterative deepening runs depth-limited DFS with limit 1, then 2, then 3… It combines DFS's small memory with BFS's preference for shallow solutions. The repeated work is cheap, because most nodes live at the deepest level anyway.

The code (Python, as in the practical)

import heapq
def astar(graph, h, start, goal):
    frontier = [(h[start], 0, start, [start])]      # (f, g, state, path)
    best_g = {start: 0}
    while frontier:
        f, g, node, path = heapq.heappop(frontier)  # smallest f first
        if g != best_g.get(node): continue          # stale entry
        if node == goal: return path, g               # goal test on EXPANSION
        for nxt, step in graph[node]:
            new_g = g + step
            if new_g < best_g.get(nxt, float("inf")):
                best_g[nxt] = new_g
                heapq.heappush(frontier, (new_g + h[nxt], new_g, nxt, path + [nxt]))
    return None, float("inf")

Delete + h[nxt] (use g only) and you have UCS. The search visualiser above runs this same logic in JavaScript.