Search algorithms · Part 2
Use estimates to guide exploration, then examine when the resulting search is complete or finds a cheapest route.
Estimate what remains → choose a frontier rule → check guarantees → prune safely.
Carry over from Part 1: the frontier holds paths; g is cost already paid; goal testing and duplicates matter.
The frontier still holds possible paths.
A heuristic changes which one looks promising.
G is the graph, V its states, and E its legal directed edges.
In G = (V, E, ωV, ωE), ωV = h assigns estimates to states; ωE assigns actual costs to edges. Unit edge costs use ωE = 1.
Straight-line distance is a lower bound for route distance, using the same units.
g is cost already paid; h estimates cost still ahead. Distance, time and money are different objectives.
Straight-line distance to the nearest valid goal is a lower bound on route distance.
Kilometres are not minutes.
Convert using a valid bound on travel speed.
Use the same units in g + h. The assumptions behind the conversion are part of the guarantee.
Grid: horizontal or vertical unit-cost moves. Δx and Δy are horizontal and vertical displacement in grid squares; |…| takes the absolute value.
Avoid the blocked square.
Best legal route: 4 moves.
Ignore obstacles.
Manhattan distance: |Δx| + |Δy| = 2.
h = 2 is the relaxed estimate; h* = 4 is the true least remaining cost. Removing constraints while preserving costs gives h ≤ h*.
A tiny remaining estimate says nothing about how much the route has already cost.
Greedy search has no general optimality guarantee.
A, B, C and G label states; G is the goal. h estimates remaining cost. B looks closer than C, but its complete route costs more.
Choose B (h = 0), then G (h = 0).
Returned cost: 1 + 9 = 10.
A → C → G costs 4 + 1 = 5.
Both h(B) = 0 and h(C) = 1 are admissible.
Admissibility does not make greedy optimal. Its selection rule still ignores the cost already paid.
After E: F has h = 2; its new rivals K and L have h = 8 and 7. Which waiting path is selected?
h estimates remaining cost; returned solution costs sum the supplied edge weights.
Greedy: choose the best endpoint across the entire frontier.
Heuristic DFS: order the newest siblings, then follow the stack.
It retains DFS’s memory advantage and its lack of a general optimality guarantee.
Suppose one older path is waiting (h = 2). Expanding the current path adds two new child paths (h = 7 and h = 8).
h estimates remaining cost: smaller looks better.
Whole frontier, shown from smallest h to largest
Next: the older path (h = 2).
It has the smallest h across the whole frontier.
New and older paths compete together.
Stack order: top (next) on the left → bottom on the right
Next: the new child with h = 7.
Push the h = 8 child first, then the h = 7 child.
Both sit above the older path, despite its lower h.
The difference: greedy uses h for every selection; heuristic DFS uses h to order new siblings, then follows the stack.
Apply the rule to this tree: after E, why are L and K tried before the older F?
h orders new siblings; returned solution costs sum the supplied edge weights.
Actual cost so far
Estimated remaining cost
Estimated total cost
Select the frontier path with the smallest f. With h = 0, A* becomes lowest-cost-first.
g is this path’s cost; h its endpoint’s remaining estimate; f = g + h its total score.
Initially f(⟨A⟩) = 0 + 5 = 5. After expanding A:
| Path | g · paid | h · estimate | f = g + h |
|---|---|---|---|
| A → B | 1 | 2 | 3 ← select |
| A → C | 2 | 4 | 6 |
| A → D | 4 | 3 | 7 |
After B: E has f = 3 + 1 = 4; F has f = 7 + 2 = 9; G has f = 4 + 9 = 13.
Course tree: expand A, then B, then E. Compare all waiting paths again.
| Endpoint / path | g · paid | h · remaining | f = g + h |
|---|---|---|---|
| C · A → C | 2 | 4 | 6 ← next |
| D · A → D | 4 | 3 | 7 |
| F · A → B → F | 7 | 2 | 9 |
| K · A → B → E → K | 4 | 8 | 12 |
| L · A → B → E → L | 5 | 7 | 12 |
| G · A → B → G | 4 | 9 | 13 |
E’s new children do not receive priority just because they are new. A* selects the smallest total estimate.
Why does A* return to C before F? Toggle h = 0 and compare the order.
g: path cost · h: remaining estimate · f = g + h: total estimate. Returned costs use the supplied edge weights.
h estimates the cheapest cost still needed to reach a goal. At a goal, use h = 0.
These two properties answer different questions about that estimate.
It must never exceed the true cheapest remaining cost. Guessing too low is allowed.
If the cheapest remaining cost is 6:
h = 4 is safe; h = 8 is too high.
Why it matters: supports finding a cheapest solution, provided A* keeps better routes available.
After a move, the estimate must not drop by more than the cost of that move.
If a move costs 1:
3 → 2 passes; 5 → 2 drops too much.
Why it matters: with correct cost updates, graph A* only needs to expand each state once.
Consistency is stronger: with h = 0 at goals, consistency also gives admissibility.
An admissible heuristic can be inconsistent; graph A* may then need to expand a state again.
These are properties of h. Selecting the smallest score, testing goals on selection, and keeping cheaper routes are rules of the algorithm.
h is estimated remaining cost; h* (“h star”) is the true cheapest remaining cost.
At every state.
At a goal: h = 0.
The true remaining cost is 6. Estimates of 4 and 6 are admissible because they do not exceed 6; 8 is too high.
Why it matters: admissibility keeps estimates optimistic, so A* does not overlook a cheaper solution.
f = g + h estimates total cost: g is cost paid; h estimates cost still ahead.
A goal costing 10 has been found, but a waiting path could lead to a solution costing 8.
Its estimated total is at most 8, so A* explores it before selecting the more expensive goal.
Assume admissible h and no better route discarded. Stop when a goal is selected, not just found.
Two paths are waiting: a goal costing 7 and an unfinished path with g = 3 already paid.
Its true cheapest remaining cost is 6, so the cheapest completion through that path costs 9.
h estimates remaining cost; f = g + h estimates total cost.
| Waiting path | f |
|---|---|
| Unfinished path | 3 + 2 = 5 ← next |
| Goal | 7 |
Explore the unfinished path first.
Its estimate makes it look cheaper than 7, although it can only finish at 9 or more.
Still safe: 5 does not exceed the true remaining cost of 6.
| Waiting path | f |
|---|---|
| Unfinished path | 3 + 5 = 8 |
| Goal | 7 ← next |
Select the goal costing 7 and stop.
A* avoids expanding the unfinished path in this example.
Tighter means closer to the true remaining cost, while still never overestimating. It makes fewer expensive routes look cheap.
Computing h also takes time. A better estimate can save search work without guaranteeing a faster run in every problem.
If a move costs 1, the estimated remaining cost may drop by at most 1.
Check this rule on every directed edge, from the state before the move (u) to the state after it (v).
The estimate falls from 3 to 2: a drop of 1, matching the move cost.
3 ≤ 1 + 2 · consistent on this edge
The estimate falls from 5 to 2: a drop of 3, although the move costs only 1.
5 > 1 + 2 · inconsistent on this edge
Consistency is stronger than admissibility: passing every edge, with h(goal) = 0, guarantees no overestimation. An admissible heuristic can still fail an edge check.
g is cost paid, h estimates remaining cost, and f = g + h estimates total cost.
Follow one path for a move costing 1: g rises from 4 to 5. What happens to h and f?
| Quantity | Before | After |
|---|---|---|
| g · cost paid | 4 | 5 |
| h · remaining estimate | 3 | 2 |
| f = g + h | 7 | 7 |
g rises by 1; h falls by 1.
They cancel out: f stays at 7.
| Quantity | Before | After |
|---|---|---|
| g · cost paid | 4 | 5 |
| h · remaining estimate | 5 | 2 |
| f = g + h | 9 | 7 |
g rises by 1; h falls by 3.
The drop is too large: f falls from 9 to 7.
Why f cannot fall: consistency limits the drop in h to the move cost; g increases by that same cost. Their sum must stay the same or increase.
Why this helps graph A*: with a consistent h and correct cost updates, the first selected route to a state has its cheapest g. After expanding the state, mark it closed (already expanded): it will not need to be reopened.
g is cost paid from the start; h estimates remaining cost. Two routes to the same state can have different g.
Update its cost and remember the cheaper route.
With an inconsistent h, reopen it: expand it again using the cheaper route.
Reaching X before does not make every new arrival useless. Keep the cheaper route, so its lower cost can improve the solution.
These rules assume nonnegative edge costs. Negative costs need different reasoning.
g is cost paid; h estimates remaining cost; f = g + h is the total estimate.
Here h is admissible but inconsistent.
X has f = 3; B has f = 5.
Discover goal G at cost 6.
Cost to X: 3 → 2.
Goal cost improves: 6 → 5.
Refusing to expand X again leaves the cost-6 solution. Reopening lets the cheaper route reach the goal, giving cost 5.
The edge B → X fails consistency: h(B) = 4 > 1 + h(X) = 1.
UCS (uniform-cost search) selects the smallest g, the cost already paid. A negative edge can make that cost fall later.
UCS selects the direct goal at 2 before B at 5, but the route via B costs −5. A repeatable negative loop on the way to a goal lowers cost forever: no cheapest solution exists.
Avoiding cycles does not restore ordinary UCS or A* guarantees for negative edges.
Use nonnegative costs and 0 ≤ h(v) ≤ h*(v); h* is true least remaining cost.
F: frontier stack · p: popped path · vₛ: start · vG: goal · v: successor · E: legal edges.
F ← stack(⟨vₛ⟩); B ← ∞; best ← none
while F ≠ ∅:
p ← pop(F)
if g(p) + h(end(p)) ≥ B: continue
if end(p) = vG:
best ← p; B ← g(p)
else:
for v with (end(p), v) ∈ E:
if v is not in p: push(F, p ⊕ v)
return bestg: path cost; h: remaining estimate.
g + h ≥ B: skip this path.
continue starts the next loop iteration.
best holds a complete route.
B holds its cost.
A goal updates both; it does not stop the search.
pop removes the latest path; push adds one. p ⊕ v appends v; ∈ means “in”; ← assigns; ∅ means empty.
Check path cycles; return best when the stack is empty. ∞ means infinity; none means no saved route.
Three-exit lab: rightmost-first DFS. g is path cost, h estimated remainder, and B the current incumbent’s cost.
| Event | g + h | Current bound B | Decision |
|---|---|---|---|
| Reach G3 through E | 12 + 0 = 12 | ∞ → 12 | Save the first solution. |
| Select C | 2 + 4 = 6 | 12 | Explore: 6 < 12. |
| Select D | 4 + 2 = 6 | 12 | Explore: 6 < 12. |
| Reach G2 | 6 + 0 = 6 | 12 → 6 | Save the improved solution. |
| Select B | 1 + 7 = 8 | 6 | Prune: 8 ≥ 6. |
The incumbent is a complete solution; g + h is a lower bound for an unfinished path. Comparing them makes pruning safe.
Rightmost-first DFS improves the saved cost from 12 to 6, then prunes state B.
g: path cost · h: estimated remainder · f = g + h: lower bound. The pruning bound is the saved route’s cost.
| Algorithm | Container / order | Information used |
|---|---|---|
| BFS / DFS | Queue / stack | Insertion order |
| IDS | Repeated depth-limited DFS | Depth bound |
| Lowest-cost-first | Minimum g | Cost already paid |
| Greedy best-first | Minimum h | Estimated remaining cost |
| Heuristic DFS | Stack; order new siblings by h | Local heuristic guidance |
| A* | Minimum g + h | Estimated total cost |
| Branch-and-bound | DFS; prune against an incumbent | Lower bounds and best solution |
Try BFS when its frontier fits in memory.
Try IDS when depth is unknown and memory is tight.
Use lowest-cost-first with nonnegative costs and correct duplicates. Check its termination assumptions.
Use A* when you can afford its frontier.
Check admissibility, goal tests on selection, and reopening when needed.
Consider depth-first branch-and-bound.
Safe lower bounds, early saved solutions and termination conditions matter.
Name the selection or pruning rule. For questions 1–2, use Part 1’s BFS, DFS and exit-comparison labs; 3–4 use this part’s A* and branch-and-bound labs.
DFS explores D and the C subtree before B. BFS selects B immediately after A.
BFS finds A → B → G1: two edges, cost 9. A → C → D → G2 has three edges, cost 6.
E has f = 3 + 1 = 4.
F has f = 7 + 2 = 9.
E wins the next comparison.
The lab searches only for costs below 6. It finds none; this does not mean that no solution exists.
Next time you see a search algorithm, ask: what does it keep, and what does it select?
AIML 2025/26 · Lesson 01 — Search
Content sequence, six original interactive examples, course-tree topology, edge costs and heuristic values.
Search strategies, heuristic conditions and pruning.
Adaptation notes, complete slide notes and source mapping are included in the notes folder.
The interactive slides run locally; the gallery and PDF are static review copies.
Choose one idea and explain it in your own words. Use an example or an interactive experiment to support your explanation.
Lecture 04 · Search algorithms · Part 2