Q5 — SEARCH FOR OPTIMAL SOLUTION

Euclidean edge costs retire BFS; the best admissible heuristic admits Dijkstra, BnB, A* and SMGS into the optimal club.

The Question

#	Question	Official answer
5	Given a state space with Euclidean edge costs, and with the best admissible heuristics, which of the following algorithms will find the optimal path?	C, D, E, G

The Topic in 60 Seconds

Two inputs changed from Q4: costs are now non-uniform (Euclidean distances), and $h$ is now guaranteed admissible (and "best" = most informed admissible $h$ , so $h = h^*$ is allowed). Non-uniformity disqualifies BFS; admissibility re-qualifies every $f = g + h$ method.

Deep-dive: browse the Concepts section for optimal search.

Solutions

5 — Euclidean edge costs, best admissible heuristics. Which find the optimal path?

Options:

Option	Verdict
A — Depth First Search	No: still neither complete-on-the-nose nor optimal; cost structure is irrelevant to its flaw (it ignores costs altogether)
B — Breadth First Search	No: BFS minimises the NUMBER of edges; with Euclidean weights one long edge can beat three short ones, so fewest-edge ≠ cheapest
C — Dijkstra's algorithm	Yes: cheapest-first expansion needs no heuristic at all; works for any non-negative costs including Euclidean
D — Branch and Bound Search	Yes: ranks partial paths by true accumulated cost $g$ ; first complete path popped is optimal, no heuristic involved
E — A*	Yes: with an admissible $h$ , A* returns the optimal path; "best admissible" only makes it faster, never wrong
F — WA* for some w	No: weighted A* scales $h$ by $w > 1$ , intentionally breaking admissibility; solution quality bounded by $w \cdot C^*$ , not optimality
G — SMGS	Yes: Sparse Memory Graph Search preserves optimality under exactly the missing precondition of Q4 — a known-admissible $h$ — while fitting memory bounds

Answer: C, D, E, G

Why the answer set flipped from Q4

Algorithm	Unit costs, unknown h (Q4)	Euclidean costs, admissible h (Q5)	What changed
BFS	in	out	non-uniform costs broke "depth = cost"
Dijkstra / BnB	in	in	never depended on either input
A*	out	in	admissibility now supplied
SMGS	out	in	its pruning is safe only for admissible h
WA*	out	out	$w > 1$ ruins optimality under any h

The moral: guarantees attach to assumptions, not algorithms. Swap the assumptions and the correct option set swaps with them.

Tricks & Tips

Answers: 5 C, D, E, G