Search
Introduced
Vocabulary
| English | Meaning |
|---|---|
| search tree | search tree |
| heuristic/hjuːˈrɪstɪk/ | heuristic |
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
Cost so far plus admissible estimate to go.
The course route, exactly
- 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
Pops D, B, C, then G at cost 8 - four expansions.
When the heuristic lies
- 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
C carries f=15 vs Goal 11: pops Goal early - trusts a lie.