Somewhat frequent
0/14
AI Search
Syllabus domain five: BFS, DFS, A*, admissible heuristics, and minimax - hand-workable and reliably examined.
Syllabus domain five: BFS, DFS, A*, admissible heuristics, and minimax - hand-workable and reliably examined.
9 multiple choice at 2 marks and 3 fill-in-the-blank at 5, marked exactly as Round 1 marks them. Each answer is explained as soon as you check it. The clock is shown, not enforced.
Search is one of the ten syllabus domains, but many entrants have never studied it. The questions can all be worked by hand, so a little focused practice can earn you dependable Round 1 marks.
| Algorithm | Complete | Optimal | Time | Space | | --- | --- | --- | --- | --- | | BFS | yes | yes, if step costs are equal | | | | DFS | no | no | | | | Uniform-cost | yes | yes | exponential | exponential | | Iterative deepening | yes | yes, if step costs are equal | | | | Greedy best-first | no | no | | | | A* | yes | yes, with an admissible | exponential | exponential |
This table is examinable directly and worth memorising. Two entries carry most of the questions: BFS's optimality condition is equal step costs, not merely "shortest path"; and DFS is incomplete only because the search space may be infinite, not because of any flaw in the traversal.
is the cost from the start, estimates the cost to the goal. is admissible if it never overestimates the true remaining cost, and A* with an admissible heuristic returns an optimal solution.
Two special cases worth stating: with , A* degenerates to uniform-cost search; with a perfect , it walks straight to the goal expanding nothing extra.
Given two admissible heuristics, is admissible and dominates both. A dominating heuristic expands no more nodes, so it is always at least as good.
Heuristics come from relaxing the problem. In the 8-puzzle, allowing a tile to move anywhere gives "number of misplaced tiles"; allowing tiles to pass through each other gives Manhattan distance. Both are admissible, and Manhattan dominates.
The standard question gives a small graph with edge costs and heuristic values, then asks which node A* expands next, or in what order. Keep a table of frontier nodes with their , , and , and expand the minimum each time. The discipline of writing the table is what prevents mistakes.
Minimax assumes an optimal opponent: the maximising player takes the largest backed-up value, the minimising player the smallest. Alpha-beta pruning skips branches that cannot change the result - tracks the maximiser's best guaranteed value, the minimiser's, and when the remaining children are pruned.
Two examinable facts: pruning does not change the result, only the work; and with perfect move ordering it examines nodes instead of , effectively doubling the depth reachable in the same time.
Memorise the completeness/optimality/complexity table; it is asked directly. BFS is optimal only with equal step costs.
Admissible means never overestimating; of admissible heuristics dominates. Alpha-beta changes the cost, never the answer, and depends on move ordering.
Uniform-cost search is which of these?
with ranks nodes by path cost from the start, which is UCS.
Select an answer
A binary tree (branching factor 2) is searched with BFS. Ignoring the root, how many nodes sit at depth 2?
.