Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right)
to preview the student view.
Your Manhattan robot has no way around a blocked intersection. Today you find a way
around one by eye, then work out, as a class, a method that never guesses. It's called
breadth-first search. No code today, just paper.
Learning Objectives
By the end of this lesson you will be able to:
Explain why the Manhattan algorithm can't handle a blocked intersection
Explain why "look at the grid and guess" isn't a method a computer can use
Number every intersection with its distance to the destination, one step further out at a time, around blocked intersections
Explain why the number on the start is the shortest path length
When your usual route to school is closed, your GPS finds a detour. The robot needs to do
the same. The Manhattan algorithm from Module 4 knows one strategy, across first, then up
or down. It has no concept of an obstacle, so it drives right into a blocked intersection.
A maps app solves the same puzzle: a closed road is blocked, and heavy traffic makes some
streets slower. This module and the next build the ideas those apps use:
This module, breadth-first search, finds a route around blocked intersections.
Module 6, Dijkstra's algorithm, finds the fastest route when some streets are
slow. Real apps use faster descendants of it (A* is the best known), but the core
idea is the one you'll write.
A maps app solving this module's problem and the next one's: go around the closed road, and avoid the slow street.
Knowledge Check
Why can't the Manhattan algorithm route around a blocked intersection?
On a 3×3 grid, block (1,0) and find the shortest path from (0,0) to (2,0). A blocked
intersection is out of play: the robot can't stop on it or drive through it.
Straight across is closed. Find the way around before you open the answer.
Manhattan's straight line goes through (1,0), so it fails. Trace a way around with your
finger and count the steps.
Without the obstacle the path is 2 steps: the steps across plus the steps up or down.
That count is the Manhattan distance. Obstacles make paths longer, so the
Manhattan distance is only a lower bound.
Knowledge Check
With (1,0) blocked, the shortest path from (0,0) to (2,0) is 4 steps, but the Manhattan distance is 2. What does that tell you?
You found that path by looking at the whole grid. A computer can't: it only sees one
intersection and which of its neighbors are open. Write your rule, in numbered steps,
for someone who can only see that much. Your rule must get them to the destination by a
shortest path, every time, on any grid.
Give it two minutes, then test your rule on this one:
Your rule can only look at one intersection and its open neighbors at a time.
Start at S (0,0), destination D (3,0), straight across the bottom row, with a wall at
(1,0) and (1,1).
Draw a 4×4 grid. Mark the start, S, in the bottom-left corner, (0,0), and the destination,
D, in the far corner, (3,3). No obstacles yet. This time, work from the destination.
Answer each question before you go on to the next.
On our grid, what does "shortest" mean?
Forget S for a moment. Which intersections are exactly 1 step from D? Write a 1 on
each.
Which are exactly 2 steps from D? Write a 2 on each. How did you find them?
Keep going until S gets a number. Could there be a shorter way from S to D than S's
number says?
Now put back the wall from the last activity, (1,0) and (1,1) blocked, with D at (3,0)
and S at (0,0), and number the grid again from D. Do you need a new rule for the
blocked intersections?
Every intersection one step from a 1 that doesn't have a number yet gets a 2.
Keep going, finishing every intersection at one distance before you start the next,
until the start has a number.
The numbers spread out from the destination like a wave, around a blocked intersection. Each number is the steps to D. The red walk on the right is next lesson's idea.
Think of dropping a stone in a pond, right on the destination. A wave spreads out from
that one point, the same distance in every direction, and flows around anything in its
way, the way the numbers flow around a blocked intersection. The wave front, the
intersections just numbered, moves out one step at a time, so everything closer is
reached first and each number is the shortest distance to the destination. That's why
this search is called breadth-first (it goes wide before it goes deep), and on a grid
a wavefront algorithm. It never looks at where the start is, so a wall that forces you
away from the destination is no problem.
Knowledge Check
An intersection already has a 2 on it. Later, while looking around an intersection with a 3, you find it's a neighbor. What do you write on it?
Knowledge Check
The start has just been given a 5. Could a shorter way from the start to the destination still turn up?
A 3×3 is small enough to trace by hand, but too small to show the shape of
breadth-first search. Here is the same rule on an 8 by 6 grid with a wall across the
middle.
Same rule as your grid: every intersection one step from D is numbered before any two steps away. Press Step to move the wave out one step at a time, or Play to watch it spread and bend around the wall.
The wave spreads evenly in every direction, even away from S: it never looks at where the
start is. Here it fills the whole grid. The red line at the end is next lesson's idea.