Week 3 Tutorial: Reopen a better route
An admissible but inconsistent heuristic on a four-edge graph: predict, trace, find the bug, fix re-expansion, then compare h = 0 with a legal heuristic.
10 March 2027
Open Week 3 in the Lab →Try your own change on this week's case.
Two-hour tutorial: preparation, coding and checks
This week’s task#
Model: S→A=3, S→B=1, B→A=1, A→G=2; h(B)=3, other h=0. Symbolic costs; no energy.
Before you start · 15 minutes#
Read W3. Predict the cost with reopening disabled. Check h(B) against the true B→G cost and against cost(B,A)+h(A).
Trace the example · 25 minutes#
Allow reopening and compare cost 5 with 4. Inspect the step where B reaches A more cheaply.
Implement and compare · 55 minutes#
Extend mySearch so a better g can reopen an expanded node. Keep the old counterexample as a regression test and compare h=0 on exactly the same graph.
Use Open full Lab for editable inputs, strategy code, exports and the practice pack. The example on this page compares this week’s published cases; your local student runner must call the functions you complete.
Check and explain · 25 minutes#
Record the inconsistent edge, the changed parent and returned path. State the conditions on the heuristic separately from the conditions on the implementation.
What to keep: A1: A*, heuristic justification and regression tests. Show the tutor your prediction, experiment and explanation for this week’s participation point; keep the record to develop your assignment.
Optional extension#
Edit the micrograph in the advanced inputs to construct another admissible-but-inconsistent case. Then compare expansions on the canonical map.
W3 · Reopen A after a better arrival.
Can an admissible heuristic still return the wrong answer?
A cheaper way to reach A appears later. Watch what happens when the search is allowed to revisit it.
Returned S → A → G with cost 5. Dijkstra with goal-on-pop returns 4. The diagnostic rule returned a worse answer.
Computed from this case · 1.19 ms · lab-1.0 · reopen
Arrows are directed edges; numbers are costs. Follow the OPEN trace to see which edge improves each distance. The graph redraws from this run's edge table.
Returned 5 · correct 4
A cheaper arrival at A
| Step | Node | g | f | OPEN | CLOSED |
|---|---|---|---|---|---|
| 1 | S | 0 | 0 | A, B | S |
| 2 | A | 3 | 3 | B, G | S, A |
| 3 | B | 1 | 4 | G | S, A, B |
| 4 | G | 5 | 5 | S, A, B |
The path through B improves A. Reopening lets that improvement reach G.
Explore the evidence, replay or open full Lab
Open full Lab ↗ for editable inputs, strategy code and saved comparisons.
Compare cost 5 with 4 and inspect the improved route through B→A.
Read the example above
Compare cost 5 with 4 and inspect the improved route through B→A.
Symbolic teaching case · Published example units; not flight-model totals · Heuristics and reopening
| Inspect | Step | Node | g | f | OPEN | CLOSED |
|---|---|---|---|---|---|---|
| 1 | S | 0 | 0 | A, B | S | |
| 2 | A | 3 | 3 | B, G | S, A | |
| 3 | B | 1 | 4 | G | S, A, B | |
| 4 | G | 5 | 5 | S, A, B |
Continue in the Lab →The same case, with every input open to change.
The spec
What you bring to the session. Written so a reader can tell whether it has been met without asking you.
- your fixed A* returns cost 4 on the four-edge graph, and the test fails on the unfixed one
- you can state the heuristic's conditions and the implementation's conditions separately
- your heuristic has a unit, and it is the unit of the cost
Teaching team
- Kofi Marchetti — tutor