Why can't the Manhattan algorithm route around a blocked intersection?
- A.It runs too slowly
- B.It only knows one fixed strategy (across, then up or down) and has no concept of obstacles
- C.It can, if you turn it off and on again
- D.The robot has no wheels
Answer Why?
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?
- A.The Manhattan distance is wrong
- B.With obstacles, the real shortest path can be longer than the Manhattan distance
- C.Obstacles always add exactly 2 steps
- D.The destination is unreachable
Answer Why?
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?
- A.Nothing — it keeps its 2
- B.4, because 3 + 1
- C.3, the smaller of 3 and 4
- D.Cross out the 2 and write 4
Answer Why?
The start has just been given a 5. Could a shorter way from the start to the destination still turn up?
- A.No: every intersection 4 or fewer steps from the destination is already numbered, so 5 is the shortest
- B.Yes: finish the whole grid, then look for a smaller number on the start
- C.Yes: a path that heads straight toward the destination might be shorter
- D.It depends on how many intersections are blocked
Answer Why?