COMP9414 Chap.4 Search Strategy and Heuristic Choice
Search Strategy and Heuristic Choice
DFS, BFS, UCS and A* share a search loop but assign different meanings to the best frontier candidate. This chapter derives their guarantees from stack, queue, cumulative-cost and estimated-total-cost priorities. It works an original A* trace with improved paths, distinguishes edge count from weighted cost, and turns admissibility into a numerical check rather than a memorised slogan.
What this chapter covers
- 01
Depth-first search with a LIFO frontier
- 02
Breadth-first search with a FIFO frontier
- 03
Uniform-cost search ordered by cumulative g
- 04
Greedy search ordered by heuristic h
- 05
A* search ordered by f equal to g plus h
- 06
Admissibility as an optimistic remaining-cost estimate
Worked example · free
A* with a goal-cost improvement
- +1Expand S and record separate g, h and f values for A and B before applying the tie rule.
- +1Expand A, giving C priority 5 and a direct goal route with cost and priority 8.
- +1Expand C and improve the goal to g=6 and f=6; reject a later worse route to C.
- +1Return S-A-C-G with actual cost 6 and justify the heuristic through the admissibility comparison.
Key terms
- Depth-first search
- A strategy that expands a deepest frontier path first through last-in, first-out order.
- Breadth-first search
- A strategy that expands shallowest frontier paths first through first-in, first-out order.
- Uniform-cost search
- A strategy that expands the frontier path with the lowest cumulative cost g.
- A* search
- A strategy that expands the lowest estimated total cost f, defined as g plus h.
- Admissibility
- The property that a heuristic never overestimates the true cheapest remaining cost.
Search Strategy and Heuristic Choice FAQ
Why can BFS return an expensive route?
BFS minimises the number of edges, not the sum of arbitrary weights. A two-edge route can cost more than a three-edge route. Its lowest-cost guarantee applies when every action has the same cost, so state the cost model before interpreting optimality.
Why does setting h to zero recover UCS?
A* orders by f=g+h. When h is zero for every node, f equals g, so the priority queue makes the same cumulative-cost choice as uniform-cost search. The result is admissible but supplies no goal-directed guidance.
How do I test whether h is admissible?
For each node where the true cheapest remaining cost is available, compare the estimate directly. The heuristic must lie between zero and that true cost and should be zero at a goal. One overestimate removes the course optimality condition.
Exam move
Use one small weighted graph for four passes. Trace DFS and BFS first to make stack and queue order automatic, then calculate every route cost and trace UCS. Add a heuristic table only after the UCS trace is correct. For A*, maintain columns for node, parent, g, h and f; replace a parent only when the new g is smaller.
After the trace, solve the remaining-cost problem exactly and compare each h with the true value to audit admissibility. Practise explaining why the same graph can yield a shallow but expensive BFS route and a deeper but cheaper UCS route. Finish every algorithm comparison with the condition supporting completeness or optimality. This converts property lists into reasoning that can be reconstructed under exam pressure.
Build a guarantee card for each method with three rows: selection rule, assumption and conclusion. Shuffle the cards and reconstruct the missing row rather than memorising a paragraph. Next perturb one edge weight while leaving graph depth unchanged and predict which algorithms may change their returned route.
Set h to zero to verify the UCS equivalence, then raise one heuristic above the exact remaining cost and identify the lost assurance without claiming that failure is inevitable. During coding practice, print stale priority-queue entries and explain why the best-cost table prevents them from corrupting the result. Compare the number of expansions only after confirming that goal timing and tie-breaking match.
End each session by recomputing the final cost directly from edges and checking that it equals g at the goal. These habits isolate ordering, bookkeeping and proof conditions so one error does not contaminate every conclusion. Maintain a separate uncertainty ledger for every trace.
Record the neighbour order, goal-test timing, duplicate policy and tie rule before the first expansion; if an answer differs from a reference, compare those conventions before changing the algorithm. Then diagnose one deliberately inconsistent heuristic by locating an edge whose local estimate drop exceeds its cost.
Reopen the affected node in a graph-search trace and state why a closed-once implementation could otherwise miss the cheaper route.
Working through Search Strategy and Heuristic Choice in COMP9414? Sia is AskSia’s AI Computer Science tutor — ask any COMP9414 Search Strategy and Heuristic Choice question and get a clear, step-by-step explanation grounded in how COMP9414 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
