Q4 — SEARCH FOR OPTIMAL SOLUTION

With unit costs and an unknown-quality heuristic, only the heuristic-free algorithms — BFS, Dijkstra and Branch-and-Bound — carry optimality guarantees.

The Question

#	Question	Official answer
4	Given a finite state space with unit edge costs, and a heuristic function whose properties are not known, which of the following algorithms are suitable for finding the optimal path?	B, C, D

The Topic in 60 Seconds

An algorithm guarantees the optimal path only if its machinery cannot be spoiled by the inputs. With unit costs, "fewest edges" = "cheapest path". If $h$ 's admissibility is unknown, every method that trusts $h$ inherits that uncertainty. Heuristic-free methods (BFS, Dijkstra, BnB) are immune.

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

Solutions

4 — Finite state space, unit edge costs, heuristic properties unknown. Which find the optimal path?

Options:

Option	Verdict
A — Depth First Search	No: not optimal even with unit costs — it commits to one deep branch and can return a goal at depth 50 while a depth-3 goal waits elsewhere
B — Breadth First Search	Yes: FIFO order dequeues goals in non-decreasing depth; with unit costs minimum depth = minimum cost
C — Dijkstra's algorithm	Yes: expands nodes in increasing $g$ ; first dequeue of the goal has $g = g^*$ regardless of any heuristic
D — Branch and Bound Search	Yes: orders OPEN by path cost $g$ alone (never consults $h$ ); the first complete path popped is provably cheapest
E — A*	No: A* is optimal only for admissible $h$ ; properties unknown → an inflated $h$ can bait it into a suboptimal return
F — WA* for some w	No: any $w > 1$ multiplies $h$ deliberately inadmissibly — speed bought with loss of the optimality guarantee
G — SMGS	No: Sparse Memory Graph Search bounds memory by pruning on $f = g+h$ ; its optimality proof assumes an admissible $h$ , which we are not given

Answer: B, C, D

The pattern

The three correct answers share one property: they ignore $h$ entirely. Their correctness rests only on facts given in the question — finite space, unit costs:

BFS: shallowest goal first; unit costs make that cheapest.
Dijkstra: cheapest-first expansion; no assumptions beyond non-negative costs.
Branch-and-Bound: keeps the best complete solution and prunes partial paths with $g \ge$ best; exact for any finite space.

Every rejected option leans on $h$ : A* and SMGS need admissibility, WA* needs $w=1$ to be optimal at all. "Properties not known" kills all three guarantees in one stroke.

Tricks & Tips

Answers: 4 B, C, D