Micro-questions over the A\* module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why it exists
1. What is wrong with Dijkstra’s direction of travel?
Answer
It expands in order of distance from the source and has no concept of a destination, so it grows a circle outward in every direction — including directly away from where you want to go.
2. Give the London–Edinburgh illustration.
Answer
Dijkstra settles every town in Cornwall first, because they are closer to London than Edinburgh is. No shortest path to Edinburgh passes through Cornwall, and a human looking at a map knows it instantly.
3. What does the human have that Dijkstra does not?
Answer
An estimate. Straight-line distance is not the true road distance, but it is never more than it — and that turns out to be exactly the property needed.
4. What did the lab measure on a 368-cell grid?
Answer
Same optimal cost of 37 in all cases: zero heuristic (Dijkstra) expanded 360 cells (97.8%), Euclidean 260 (70.7%), Manhattan 233 (63.3%) — and with tie-breaking, 38 cells (~10%).
B. The vocabulary
5. What is ?
Answer
The cost so far — the best route found from start to . A known, exact quantity about the past; the same number Dijkstra keeps.
6. What is ?
Answer
The heuristic — an estimate of the remaining cost from to the goal. A guess about the future, supplied by you, and the only new ingredient.
7. What is , and what does keying on it mean?
Answer
, the estimated total cost of the best route through . A* is exactly Dijkstra with the priority queue keyed on instead of — that single substitution is the whole algorithm.
8. Define admissible.
Answer
the true remaining cost, for every — never overestimates. An admissible heuristic is optimistic: it may promise a shortcut that does not exist, but it never warns you off a route that is actually good.
9. Define consistent.
Answer
Also monotone — for every edge, with . The estimate may drop by at most the cost of the step you take.
10. How do admissible and consistent relate?
Answer
Consistency is strictly stronger. Every consistent heuristic is admissible; not the reverse.
11. What are the open and closed sets?
Answer
Open (frontier/fringe): discovered but not yet expanded — in practice the priority queue. Closed (expanded/visited): already popped and processed.
12. What does “expanding a node” mean, and why is the expansion count the standard measure?
Answer
Removing it from the open set and generating its successors. The count is proportional to real work and independent of the machine.
13. What is greedy best-first search?
Answer
Keying the queue on alone, ignoring . Fast and not optimal, because it never accounts for the cost already paid.
C. The algorithm
14. What single line differs from Dijkstra?
Answer
The push: heapq.heappush(pq, (ng + h(nb), nb)) instead of (ng, nb).
15. What happens if everywhere?
Answer
It is Dijkstra, character for character — . A* is a strict generalisation, so “A* versus Dijkstra” is better read as “A* with a good versus A* with ”.
16. Why must the goal test happen on pop and not on push?
Answer
The first time you discover the goal you may have an expensive route to it. The first time you expand it, its is the queue minimum, and since , — so is the true shortest distance.
17. Why is the push-time test a nasty bug?
Answer
It returns suboptimal paths, usually right and occasionally wrong, which makes it easy to miss in testing.
D. The optimality proof
18. State the optimality claim.
Answer
If the heuristic never overestimates, then the first time A* expands the goal, it has found the shortest path to it.
19. Give the proof.
Answer
Suppose A* is about to expand the goal at , and a shorter path of cost exists. That path has some node still open. Then
so has smaller and would have been popped first — contradiction.
20. Which step is exactly admissibility?
Answer
The middle inequality, true remaining cost.
21. What does the proof not require of ?
Answer
Anything else. It can be wildly inaccurate, zero, or discontinuous — as long as it never promises the remaining journey is longer than it really is.
E. What consistency buys
22. What are the two things consistency gives you?
Answer
- never decreases along a path.
- A closed node never needs reopening.
23. What goes wrong with a merely-admissible, inconsistent heuristic?
Answer
You can discover a cheaper route to an already-expanded node and must put it back in the open set — costing time and complicating the code.
24. Answer the standard interview question: difference between admissible and consistent?
Answer
Admissible gives you the right answer; consistent gives you the right answer without reopening nodes.
25. Why is Manhattan admissible on a 4-connected unit-cost grid?
Answer
With no walls it is the exact distance, and walls can only make the true distance longer. An estimate equal to the truth in the easiest case, where truth only grows from there, can never overestimate.
26. Why is Manhattan inadmissible on an 8-connected grid?
Answer
A single diagonal step costs 1, but Manhattan reports 2. The heuristic must match the movement model — this is the most common way people break A* in practice.
F. Choosing a heuristic
27. Give the heuristic for each movement model.
Answer
| Movement | Heuristic |
|---|---|
| 4-directional, unit cost | Manhattan |
| 8-directional, diagonals cost 1 | Chebyshev |
| 8-directional, diagonals | Octile |
| Euclidean plane | straight-line distance |
| Road network | straight-line ÷ max speed |
| Sliding tile puzzle | sum of Manhattan distances |
| Anything | 0 (= Dijkstra) |
28. State the design rule for inventing a heuristic.
Answer
Solve a relaxed version of your problem — one with constraints deleted — and use its exact answer. A relaxed problem’s optimum can never exceed the real optimum, so it is automatically admissible.
29. Apply the rule to Manhattan and to the 15-puzzle.
Answer
Manhattan is the exact answer to “this grid with the walls removed”. Sum-of-Manhattan is the exact answer to “this puzzle if tiles could pass through each other”.
30. What does it mean for to dominate ?
Answer
everywhere, both admissible. Dominating heuristics never expand more nodes — which is why Manhattan (233) beats Euclidean (260) on a 4-connected grid, despite both being admissible.
G. Weighted A*
31. What is weighted A*?
Answer
for . Inflating makes the search greedier and faster, at the cost of optimality.
32. Multiply an admissible heuristic by 3 — what changes, and in which direction?
Answer
Both change. Expansions fall; path cost rises; optimality is lost.
33. What is the formal promise?
Answer
The path returned is at most times the optimal cost.
34. At the heuristic already overestimates at 14 cells, yet the path is still optimal. What does that teach?
Answer
Admissibility is sufficient for optimality, not necessary. Breaking it means you have lost the guarantee, not necessarily the answer.
35. Why does that make inadmissible heuristics dangerous?
Answer
They usually work, and then quietly do not.
36. When is the trade legitimate?
Answer
Game pathfinding hundreds of units per frame will take a 10%-worse path for a 3× speedup — nobody can see the difference, everyone can see the frame drop.
H. Tie-breaking
37. What is a plateau, and why does a uniform grid create one?
Answer
A large region of equal that A* has no reason to prefer any part of. Every route of the same length through open ground has identical .
38. What did deliberate tie-breaking achieve in the lab?
Answer
233 cells down to 38 — a 6× reduction — for the same optimal path, with nothing about the heuristic changed.
39. Which way should ties be broken, and why?
Answer
Prefer larger (equivalently smaller , since is constant on the plateau). Larger means further along the journey, so it drives the search down the plateau toward the goal instead of fanning out sideways.
40. How do you implement it?
Answer
Make the priority a tuple: (f, h, counter, node). Python compares on first and only consults later elements on a tie.
41. What is the counter element for?
Answer
Not decoration — it guarantees a total order so the heap never tries to compare node objects themselves, which may not be orderable. It also makes runs reproducible.
42. Name two further standard tie-breaking techniques.
Answer
- Scale by for tiny (around ) — bounded optimality loss, often negligible.
- Add a tiny cross-product term preferring nodes near the straight start–goal line — standard in games, where path aesthetics matter.
I. The family
43. Complete the table: what the queue key decides.
Answer
| Key | Algorithm | Optimal? |
|---|---|---|
| Dijkstra / uniform-cost | yes | |
| , equal costs | BFS | yes |
| greedy best-first | no | |
| A* | yes, if admissible | |
| weighted A* | within factor |
44. Why is greedy best-first the instructive failure?
Answer
Ignoring , it will happily walk a 500-step route that looks like it heads the right way over a 20-step route that starts by moving away. is what keeps the search honest about what has already been spent.
J. Traps
45. What is the mixing-units trap?
Answer
If is in seconds and in metres, is meaningless. Straight-line distance is admissible for a time cost only after dividing by the maximum possible speed.
46. When should you not use A* at all?
Answer
For all-pairs (use Floyd–Warshall) or one-source-to-everything (plain Dijkstra — the heuristic buys nothing without a single target).
47. Does A* work with negative edge weights?
Answer
No. It inherits Dijkstra’s finalisation and therefore Dijkstra’s failure. No heuristic repairs this — use Bellman–Ford.
48. What do you get from a weak heuristic?
Answer
Dijkstra, plus the cost of the machinery. Measure expansions, not intentions.
49. Summarise A* in one sentence.
Answer
Dijkstra with the queue keyed on cost-so-far plus an optimistic estimate of cost-remaining — optimal whenever the estimate never overestimates, and faster in proportion to how good the estimate is.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- A\* Search — the module
- Dijkstra — Question Bank — A* with
- Bellman–Ford — Question Bank — what no heuristic can fix
Software engineering
Infrastructure & security
Computer science
Hardware & engineering