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
  1. never decreases along a path.
  2. 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
MovementHeuristic
4-directional, unit costManhattan
8-directional, diagonals cost 1Chebyshev
8-directional, diagonals Octile
Euclidean planestraight-line distance
Road networkstraight-line ÷ max speed
Sliding tile puzzlesum of Manhattan distances
Anything0 (= 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
  1. Scale by for tiny (around ) — bounded optimality loss, often negligible.
  2. 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
KeyAlgorithmOptimal?
Dijkstra / uniform-costyes
, equal costsBFSyes
greedy best-firstno
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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms