Q1 — Best First Search, A* and Branch-and-Bound on the Grid Map
h values are given outright — Best First detours through E and D, while A* and Branch-and-Bound both find the cost-24 southern route.
The Question
1×1 grid, start S, goal G. MoveGen alphabetical, Manhattan heuristic, ties by label. The h values are given in the paper: h(S)=10, h(E)=9, h(F)=10, h(D)=4, h(C)=6, h(B)=7, h(A)=3, h(G)=0.
| # | Question | Official answer |
|---|---|---|
| 1.1 | Best First Search path | S,E,D,G |
| 1.2 | A* path | S,F,C,A,G |
| 1.3 | Branch-and-Bound path | S,F,C,A,G |
| 1.4 | Who finds the shortest path? (multi-select) | B, C |
| 1.5 | Admissibility | A — admissible |
The Topic in 60 Seconds
BFS sorts by h, A* by f = g + h, BnB by g on full paths. A* is optimal when h never overestimates.
Deep-dive: A* Search, Best First Search, Branch and Bound.
Step 0 — Heuristic table (given in the paper)
| Node | S | E | F | D | C | B | A | G |
|---|---|---|---|---|---|---|---|---|
| 10 | 9 | 10 | 4 | 6 | 7 | 3 | 0 |
1.1 — Best First Search → S,E,D,G
| Step | OPEN (node : h) | Pick |
|---|---|---|
| 1 | S : 10 | S → E(9), F(10) |
| 2 | E : 9, F : 10 | E → D(4) |
| 3 | D : 4, F : 10 | D → A(3), G(0) |
| 4 | G : 0, A : 3, F : 10 | G — goal! |
Path: S → E → D → G, cost 12 + 8 + 8 = 28 — h alone never looks at edge costs.
1.2 — A* → S,F,C,A,G
Every line below is f = g + h. Watch steps 3 and 7: E (21) must be expanded before C, and D (24) before G, or your OPEN list is wrong.
| Step | OPEN (node : g+h = f) | Pick |
|---|---|---|
| 1 | S : 0+10 = 10 | S → E : 12+9 = 21, F : 8+10 = 18 |
| 2 | F : 18, E : 21 | F → D : 20+4 = 24, C : 16+6 = 22, B : 16+7 = 23 |
| 3 | E : 21, C : 22, B : 23, D : 24 | E → D via E : 20+4 = 24 (tie with old 24 — keep either) |
| 4 | C : 22, B : 23, D : 24 | C → A : 20+3 = 23, B via C : 24+7 = 31 (keep 23) |
| 5 | A : 23, B : 23, D : 24 | A (tie 23 vs 23 → labels A < B) → G : 24+0 = 24 |
| 6 | B : 23, D : 24, G : 24 | B → G via B : 28+0 = 28 (keep 24) |
| 7 | D : 24, G : 24 | D (tie → labels D < G) → G via D : 28 (keep 24) |
| 8 | G : 24 | G — goal! |
Path: S → F → C → A → G, cost 8+8+4+4 = 24.
1.3 — Branch-and-Bound → S,F,C,A,G
Pop the cheapest partial path; ties break by path labels (SE < SF, SFCA < SFCB).
| Pop | Extend | OPEN afterwards (path : g) |
|---|---|---|
| S : 0 | SE : 12, SF : 8 | SF : 8, SE : 12 |
| SF : 8 | SFD : 20, SFC : 16, SFB : 16 | SE : 12, SFC : 16, SFB : 16, SFD : 20 |
| SE : 12 | SED : 20 | SFC : 16, SFB : 16, SED : 20, SFD : 20 |
| SFC : 16 (tie SFB) | SFCA : 20, SFCB : 24 | SFB : 16, SFCA : 20, SED : 20, SFD : 20, SFCB : 24 |
| SFB : 16 | SFBG : 28 | SFCA : 20, SED : 20, SFD : 20, SFCB : 24, SFBG : 28 |
| SED : 20 | SEDA : 28, SEDG : 28 | SFCA : 20, SFD : 20, SFCB : 24, SEDA/SEDG/SFBG : 28 |
| SFCA : 20 | SFCAG : 24 ← goal on queue | SFD : 20, SFCAG : 24, SFCB : 24, … all 28s |
| SFD : 20 | SFDG : 28 | SFCAG : 24, SFCB : 24, … |
| SFCAG : 24 | goal popped — cheapest open is SFCB : 24 ≥ 24 | → optimal |
Path: S → F → C → A → G, cost 8+8+4+4 = 24 ✓
1.4 — Shortest path → B, C (both)
A* and BnB both returned 24; BFS returned 28 → B and C (multi-select!).
1.5 — Admissibility → A (admissible)
Every h ≤ true cheapest cost from that node:
| Node | (best real cost to G) | OK? | |
|---|---|---|---|
| A | 3 | 4 (A-G) | ✓ |
| D | 4 | 8 (D-G) | ✓ |
| C | 6 | 8 (C-A-G = 4+4) | ✓ |
| B | 7 | 12 (B-G) | ✓ |
| F | 10 | 16 (F-C-A-G) | ✓ |
| E | 9 | 16 (E-D-G) | ✓ |
| S | 10 | 24 (S-F-C-A-G) | ✓ |
No overestimate anywhere → admissible ✓ — which is exactly why A* hit the optimum.
Tricks & Tips
Answers: 1.1 S,E,D,G · 1.2 S,F,C,A,G · 1.3 S,F,C,A,G · 1.4 B, C · 1.5 A