Search

Vocabulary

English	Meaning
search tree	A tree of states and possible moves explored when solving a search problem.
heuristic/hjuːˈrɪstɪk/	An estimate used to guide search, such as an estimate of the remaining path cost.

The tree and the estimate

A search tree: nodes are states, edges are moves. Uninformed search expands blindly — breadth-first (BFS, shortest when steps equal), depth-first (DFS, frugal memory). Informed search uses a heuristic $h(n)$: A* search picks the node minimising $f = g + h$.

{exercise:uni-cs1301-astar}

Practice

A* chooses the node minimising —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Course graph: D→A (4), D→B (2), A→C (3), B→C (1), C→G (5), B→G (9); $h = \{A{:}8, B{:}6, C{:}5, G{:}0\}$. A* pops D (0), B (8), C (8), G (8): optimal cost 8 via D→B→C→G, four expansions — BFS visits every node.
Admissibility is the contract: $h(n) \le h^*(n)$ guarantees the first goal pop is optimal, because $f$ at that pop is a lower bound no open node can beat.

{exercise:uni-cs1301-trace}

Practice

On the course graph, A* expands — nodes before the goal

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Overestimate $h(C) = 12$: C carries $f = 3 + 12 = 15$ while Goal-through-B carries $11$ — A* pops the Goal at cost 11 and stops: suboptimal ($11 > 8$).
Complete (finds a solution) is not optimal (finds the best); BFS's frontier costs $O(b^d)$ memory.

{exercise:uni-cs1301-lies}

Practice

Overestimating h(C) to 12 makes A* return cost —

Difficulty 1/5 · 100 coins + a small bonus on first completion today