CSE 4355 W4 · Class 1 Heuristics, greedy search and A*
Sakeef Sani ↗ ↓ PDF

CSE 4355Week 4Class 1Saturday · 9:30 AM – 10:50 AM80 min

Heuristics, greedy search and A*

Last week's searches were blind: they only knew how far they had come. Today we give the search a sense of direction, and prove when that sense can be trusted.

S present · L lecturer notes · → next step · F full screen · P presenter window
01 Cold open 0–4 min

The rickshaw-puller's compass

Ask a rickshaw-puller in Old Dhaka to reach Sadarghat. No map, no GPS, but he never turns away from the river.

UCS last week expanded every city cheaper than the answer, in all directions, including Sylhet, 190 km the wrong way. It knew how far it had come, not how far it had left.

Today: add an estimate of the distance left, h(n), and decide which city to expand using it.

10510012019065656010090359515075100DhakaSh 300Brahmanbariah 270Sylheth 390Cumillah 230Chandpurh 240Fenih 180Noakhalih 190Chattogramh 120Bandarbanh 85Cox's Bazarh 0Gh = straight-line km to Cox's Bazar (approx.)
02 Concept 4–8 min

Best-first search: one skeleton, three orders

  • A heuristic h(n) estimates the cost of the cheapest path from n to a goal. It uses knowledge about the problem; h(goal) = 0.
  • Best-first search is last week's UCS skeleton with the priority queue ordered by an evaluation function f(n):
Strategyf(n)Reads as
Uniform-costg(n)cheapest so far
Greedy best-firsth(n)looks closest to the goal
A*g(n) + h(n)estimated cost of the best solution through n

Notation

g(n): cost from the start to n (known).

h(n): estimated cost from n to the goal (guessed).

h*(n): true cheapest cost from n to the goal (unknown during search).

Pop culture

A* was published in 1968 by Hart, Nilsson and Raphael at SRI, for Shakey, the first mobile robot that planned its own moves. It is older than the Apollo moon landing.

03 Concept 8–11 min

Greedy best-first: fast, short-sighted

  • Always expand the node with the smallest h. On our map it walks straight down the coast: DHK, CUM, FEN, CTG, COX, 5 expansions (UCS needed 10).
  • Not optimal: it ignores g, so a node that looks close but was expensive to reach still wins.
  • Not complete as tree search: it can oscillate between two nodes that both look close (a dead end next to the goal). Graph search in a finite space fixes that.
  • Worst case O(bm) time and space, but a good h cuts this dramatically.
Gotcha

"Closest to the goal" is not "on the best path". A river, a cantonment wall or a one-way street can make the nearest-looking point a trap.

Think deeper

When would you happily use greedy search anyway?

Argue it in pairs for two minutes. There may be more than one defensible answer.

04 Live lab 11–16 min

Live lab: greedy vs A* on the road to Cox's Bazar

Greedy vs A*: Dhaka → Cox's Bazar The tags are h(n), the straight-line km to the goal. Compare how many cities each strategy expands, and what route it returns.
10510012019065656010090359515075100DhakaSh 300Brahmanbariah 270Sylheth 390Cumillah 230Chandpurh 240Fenih 180Noakhalih 190Chattogramh 120Bandarbanh 85Cox's Bazarh 0Gschematic · road km approximate

Frontier

priority queue: pop lowest f = g + h
DHK0+300=300

Explored

in the order expanded
empty

initStart: frontier = [Dhaka (f = 0 + 300 = 300)]

Expanded0 / 8
Cost—
Optimal405 km
05 Your turn 16–21 min

Your turn · 1: where greedy goes wrong

04:00
1 Exam CQ
236633Sstarth 7Ah 5Bh 6Ch 4Dh 3Gh 0goal

Edge costs on the lines, h(n) in the tags. Run greedy best-first and then A* (graph search) from S to G. Give the expansion order and the path for each.

Work it out first.
Press Solve when the class has an answer.

06 Concept 21–25 min

A*: cost so far + estimate to go

f(n)=g(n)+h(n)  ≈  cost of the cheapest solution that passes through nf(n) = g(n) + h(n) \;\approx\; \text{cost of the cheapest solution that passes through } n
  • Exactly UCS with the queue on f instead of g. Goal test on pop (as in UCS: a goal on the frontier may still be beaten).
  • If h is good, A* expands few nodes off the best path. If h = 0, A* is UCS. If h = h*, A* walks straight down the optimal path.
  • Two conditions on h make A* optimal: admissibility (tree search) and consistency (graph search). Next slides.

A* in one picture: contours

UCS spreads in circles of equal g around the start. A* spreads in ellipse-like contours of equal f, stretched towards the goal. A better h makes them thinner.

Pro tip

The frontier entry for the goal has f = g (because h = 0). A* stops when that is the smallest f on the frontier, i.e. when nothing else could possibly lead somewhere cheaper.

07 Worked example 25–31 min

Worked example: A* by hand

Given

Last week's map with h = straight-line km to Cox's Bazar (tags). Start Dhaka, goal Cox's Bazar. Graph search.

Find

The frontier (with f = g + h) after each expansion, the expansion order and the route.

10510012019065656010090359515075100DhakaSh 300Brahmanbariah 270Sylheth 390Cumillah 230Chandpurh 240Fenih 180Noakhalih 190Chattogramh 120Bandarbanh 85Cox's Bazarh 0Gschematic · km approximate

Method: A* graph search (Russell & Norvig); f = g + h

Solution

Predict the answer first. Then reveal one step at a time.

08 Concept 31–36 min

When can we trust A*? Admissible and consistent

Admissible: never overestimates

h(n)≤h∗(n)for every nh(n) \le h^*(n)\quad\text{for every } n

Straight-line distance ≤ any road distance. Tree-search A* with an admissible h is optimal.

Consistent (monotone): the triangle inequality

h(n)≤c(n,a,n′)+h(n′)for every edge n→n′h(n) \le c(n, a, n') + h(n')\quad\text{for every edge } n \to n'

Consistent ⇒ admissible, and f never decreases along a path, so graph-search A* is optimal and never needs to re-open a closed node.

Why admissible ⇒ optimal (tree search)

Let C* be the optimal cost and G₂ a worse goal on the frontier: f(G₂) = g(G₂) > C*. Some node n of the optimal path is also on the frontier, and

f(n)=g(n)+h(n)≤g(n)+h∗(n)=C∗<f(G2)f(n) = g(n) + h(n) \le g(n) + h^*(n) = C^* < f(G_2)

So n (and the rest of the optimal path) is popped before G₂ can be. ∎

Pro tip

Check consistency edge by edge: Feni–Chattogram: 180 ≤ 95 + 120 = 215 ✓. Bandarban–Cox's: 85 ≤ 100 ✓. Every edge of our map passes.

09 Your turn 36–42 min

Your turn · 2: admissible is not always enough

05:00
2 Trap
145123Sstarth 6Ah 6Bh 2Ch 3Gh 0goal

(a) Is h admissible? (b) Is it consistent? (c) Run A* graph search (never re-expand an explored node). Is the answer optimal? Explain.

Work it out first.
Press Solve when the class has an answer.

10 Live lab 42–49 min

Live lab: path-finding on a grid

Path-finding on a grid: who explores what? Each move costs 1. Purple = expanded, cyan = frontier, yellow = path. Draw walls with the mouse; drag S or G. Every run is animated.
SG
Expanded115
Max frontier73
Path33 moves
Optimal33 moves
11 Think deeper 49–53 min

Critical thinking · how wrong can a heuristic be?

Think deeper

Your boss multiplies the straight-line heuristic by 1.5 'to make the route planner faster'. What do you gain, and what can you lose?

Argue it in pairs for two minutes. There may be more than one defensible answer.

Think deeper

Two admissible heuristics h₁ and h₂ give different numbers for the same node. Which should A* use?

Argue it in pairs for two minutes. There may be more than one defensible answer.

12 Concept 53–57 min

A*'s weakness: memory

QuestionGreedyA*
Complete?graph search in finite spacesyes (finite b, step costs ≥ ε > 0)
Optimal?noyes (admissible: tree; consistent: graph)
TimeO(bm), often far lessexponential in the error of h
SpaceO(bm)keeps every generated node
Gotcha

A* usually runs out of memory long before it runs out of time: it stores the whole frontier and explored set.

Memory-bounded relatives (names to know)

IDA*: iterative deepening on f instead of depth (W3's IDS idea). RBFS and SMA*: forget the worst nodes when memory is full, re-create them if needed.

13 Real world 57–63 min

Real world: A* everywhere you move

Games

When you click a destination in a strategy game, units follow paths from A* on a grid or a navigation mesh. Engines add tricks (precomputed waypoints, path smoothing), but the core is the lab you just played with.

Road routing

Map apps route over millions of road segments. Plain straight-line A* is too slow there; engines use A* with much better precomputed heuristics (landmarks and the triangle inequality, "ALT") or hierarchies of shortcuts. Same admissibility idea, smarter h.

Hospital robots

Autonomous delivery robots carry medicines and samples along hospital corridors on an occupancy grid, re-planning with A*-family planners (D* Lite) when a trolley blocks the way.

Think deeper

A Pathao rider's app uses travel time as cost and straight-line km ÷ 60 km/h as h. During Dhaka traffic, is this h admissible?

Argue it in pairs for two minutes. There may be more than one defensible answer.

14 Pop quiz 63–68 min

Pop quiz

Score 0

Question 1 / 5

Greedy best-first search orders its frontier by…

15 Recap 68–80 min

Three things to remember

01

Best-first search sorts by f: UCS f = g, greedy f = h (fast, not optimal), A* f = g + h.

02

Admissible (h ≤ h*) ⇒ tree-search A* optimal. Consistent (h(n) ≤ c + h(n')) ⇒ graph-search A* optimal, f never decreases.

03

Better h ⇒ fewer expansions. Inflate h (weighted A*) for speed with a bounded loss. A*'s real limit is memory (IDA*).

HW Before next class

A landslide closes the Chattogram–Cox's Bazar road. Re-run A* (same h) by hand from Dhaka. Which route, what cost, how many expansions? Is h still consistent?

Work it out first.
Press Solve when the class has an answer.