Q5 — SEARCH FOR OPTIMAL SOLUTION
Arbitrary edge costs retire BFS, and an unknown-quality heuristic retires everything that trusts h — only Dijkstra and Branch-and-Bound remain.
The Question
| # | Question | Official answer |
|---|---|---|
| 5 | Given a finite state space with edge costs that may or may not be Euclidean and a heuristic function whose properties are not known, which of the following algorithms are suitable for finding the optimal path? | C, D |
The Topic in 60 Seconds
A guarantee can only rest on what the question gives you. Here you are given: finite space, arbitrary (possibly non-uniform) costs — and explicitly not given anything about . So every algorithm whose correctness proof says "…assuming admissible " is disqualified.
Deep-dive: browse the Concepts section for optimal search.
Solutions
5 — Finite space, costs of unknown shape, heuristic of unknown quality. Which find the optimal path?
| Option | Verdict |
|---|---|
| A — Depth First Search | No: ignores costs completely; returns a goal, rarely the cheapest |
| B — Breadth First Search | No: minimises the NUMBER of edges; with non-uniform costs one long edge can beat three short ones |
| C — Dijkstra's algorithm | Yes: expands in increasing true cost ; never consults ; correct for any non-negative costs |
| D — Branch and Bound | Yes: ranks partial paths by accumulated and prunes against the best complete tour; no heuristic involved |
| E — A* | No: optimal only when is admissible — "properties not known" removes the guarantee |
| F — WA* for some w | No: any is inadmissible by design; even is just A* needing admissibility |
| G — SMGS | No: its pruning rule is safe only under admissible , which we are not given |
Answer: C, D
The pattern
The two survivors share one property: they ignore entirely. Their correctness needs nothing beyond finite space + non-negative costs — both supplied.
| Algorithm | Depends on h? | Survives unknown h? |
|---|---|---|
| DFS / BFS | no — but fails on costs instead | out for a different reason |
| Dijkstra / BnB | no | in |
| A* / SMGS | yes (admissibility) | out |
| WA* | yes (w·admissibility) | out |
Compare the sibling questions: add "unit costs" and BFS joins the club; swap to "best admissible h" and A*/SMGS join. Guarantees attach to assumptions, not algorithms.
Tricks & Tips
Answers: 5 C, D