Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Informed search: greedy best-first and A*

Informed search uses heuristic functions to guide search; greedy best-first uses only the heuristic h and is fast but not guaranteed optimal, while A* uses f = g + h and is complete and optimal when h is admissible (and more efficient if h is consistent).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Key ideas

Define every term before use.

  • State: a representation of a possible configuration of the problem (for example, a node in a graph).
  • Action: a transition that moves from one state to another, typically with a non-negative step cost c(n, n').
  • Goal: a state (or set of states) satisfying the goal-test.
  • Path cost g(n): the accumulated cost from the start state to node n along the path chosen so far. g(start) = 0.
  • Heuristic function h(n): an estimate of the cost from node n to the nearest goal. A heuristic maps states to non-negative real numbers.
  • Admissible heuristic: a heuristic h is admissible if for every node n, h(n) ≤ h*(n), where h*(n) is the true lowest cost from n to a goal. Assumption: step costs are non-negative.
  • Consistent (monotone) heuristic: h is consistent if for every node n and successor n' generated by action a, h(n) ≤ c(n,n') + h(n'). Equivalently f(n) = g(n) + h(n) is non-decreasing along any path. Consistency implies admissibility (for nodes reachable from start) when h(goal)=0.
  • Open (frontier): the set of nodes generated but not yet expanded.
  • Closed (explored): the set of nodes already expanded. In tree search, no Closed set is used; in graph search, Closed prevents re-expanding already explored states.

Two search algorithms:

  • Greedy best-first search: select the node from Open that minimizes h(n). Expand it; add its successors with their h values. Greedy uses only the heuristic estimate. It tries to go toward the goal quickly but ignores g(n). Terminate when a goal is selected for expansion (popped), not when first generated. It is not optimal in general, even if h is admissible.
  • A: select the node that minimizes f(n) = g(n) + h(n). Here g(n) is exact path cost so far, and h(n) estimates remaining cost. A* balances exploration cost and estimated remaining cost. Terminate when a goal node is selected for expansion (popped), not upon generation. Special cases: with h ≡ 0, A* reduces to uniform-cost search; with a perfect heuristic h = h, A* expands only nodes on optimal paths.

Important properties (exact statements universities ask for):

  • Completeness: If branching factor b is finite and every action has cost ≥ ε > 0, then A* is complete on graphs (it will find a goal if one exists). Greedy best-first is not complete in general; it is complete on finite state spaces only when repeated states are avoided via a Closed set (graph search), otherwise it can get trapped in loops.
  • Optimality of A*: If h is admissible (and all step costs are non-negative), then A* using f = g + h is optimal on tree search (i.e., the first goal it pops is on an optimal-cost path). On graph search, A* is optimal if h is admissible; if h is only admissible but not consistent, A* may need to re-expand nodes (but still finds optimal path given proper bookkeeping), i.e., nodes in Closed may need to be reopened if a better g is discovered. A* should terminate only when it pops a goal node (not when it is generated); tie-breaking among equal f-values does not affect optimality but can affect the number of expansions.
  • Consistency implies no node will be expanded more than once; consistent heuristics make graph-search implementation simpler and more efficient. You may still need to decrease-key/update the priority of nodes already in Open if a better g is found before they are expanded. Heuristic dominance: if h2(n) ≥ h1(n) for all n and both are admissible, then A* with h2 expands no more nodes than with h1 (ties aside).

Proof sketch of A* optimality (tree search) — exact exam-style steps:

  1. Let G be the goal node returned by A* when it is selected for expansion. Let C* be the cost of an optimal path from start to goal.
  2. Suppose for contradiction there is a different goal G' with cost C < C* (so A* returned a non-optimal goal).
  3. Consider the frontier when A* chose G to expand. Every node n on the optimal path to G' has f(n) ≤ C (because g(n) is cost from start to n and h(n) ≤ true remaining cost).
  4. Therefore some node on that optimal path must have been in Open with f ≤ C, so A* would have expanded it before expanding any node with f > C, contradicting that A* chose G with f(G) = C* > C.
  5. Hence A* cannot return a suboptimal goal. Assumptions: admissibility of h (h ≤ true remaining cost), non-negative step costs, correct tie-breaking or careful statement that A* returns an optimal-cost goal when it pops a goal node whose f equals optimal cost.

What to draw (diagrams commonly asked in exams):

  • Draw a small directed graph: nodes as circles labeled with names and with heuristic numbers beside them; edges labeled with step costs. Show start S and goal G. Draw Open and Closed lists as boxes and show the order of nodes moved from Open to Closed, with f or h values written next to nodes. This makes step-by-step execution clear.

Formulas

  • Consistency condition: h(n) ≤ c(n,n') + h(n') for every edge (n,n').
  • Admissibility condition: h(n) ≤ h*(n) for every node n, where h*(n) is true minimum cost to a goal.
  • Complexity (informal exam form): Time complexity often written as O(b^{d}) or O(b^{C* / ε}) where b is branching factor, d is depth of solution, C* is optimal solution cost, and ε is minimal step cost. These are worst-case and depend strongly on h. Space complexity: A* (and greedy best-first) store all generated nodes on Open (and Closed), so space is also exponential in the worst case (on the order of the number of generated nodes).

Worked examples

Example 1 — Greedy vs A* on the same graph (numerical, exam style): Graph (draw these nodes and edges): S -> A (cost 2), S -> B (cost 10), A -> G (cost 10), B -> G (cost 1). Goal G. Heuristic set 1 (non-admissible for B): h(S)=11, h(A)=1, h(B)=50, h(G)=0.

  • True path costs: S->A->G = 2 + 10 = 12; S->B->G = 10 + 1 = 11 (optimal path is S-B-G cost 11). Greedy best-first (chooses lowest h):
  1. Open = {S(h=11)}. Pop S; expand neighbors A(h=1) and B(h=50). Open = {A, B}.
  2. Pop A (h=1). Expand A -> G(h=0). Open = {G(h=0), B(h=50)}.
  3. Pop G (h=0): goal found. Path = S-A-G with cost 12. Result: greedy finds path cost 12 (suboptimal). A* with admissible heuristic set 2 (replace h for admissibility): h'(S)=11, h'(A)=10, h'(B)=1, h'(G)=0.
  4. Open = {S(f=0+11=11)}. Pop S; expand A: g(A)=2 f(A)=2+10=12; expand B: g(B)=10 f(B)=10+1=11. Open = {B(f=11), A(f=12)}.
  5. Pop B (f=11). Expand B -> G: g(G)=11 f(G)=11+0=11. Open contains A(f=12), G(f=11).
  6. Pop G (f=11): goal found. Path = S-B-G cost 11 (optimal). Conclusion: greedy used a misleading non-admissible heuristic and returned a suboptimal path; A* with admissible h' found the optimal path.

Example 2 — A* with a consistent heuristic (theory model-answer style): Question: Show one step-by-step run where heuristic is consistent and explain why nodes are not re-expanded. Graph: S -> A (2), S -> B (2), A -> G (3), B -> G (3). Heuristic: h(G)=0, h(A)=3, h(B)=3, h(S)=5. Check consistency: h(S)=5 ≤ c(S,A)+h(A)=2+3=5 and ≤ 2+3 for B; h(A)=3 ≤ 3+0 etc. So h is consistent. A* run (calculate f = g + h):

  1. Start: Open {S(f=0+5=5)}. Pop S; expand A(g=2 f=2+3=5) and B(g=2 f=2+3=5). Open = {A(f=5), B(f=5)}.
  2. Pop A (tie-breaking arbitrary). Expand A -> G: g(G)=5 f(G)=5+0=5. Open = {B(f=5), G(f=5)}.
  3. Pop G => goal found, cost 5. Because h is consistent, no previously expanded node can be reached later via a cheaper path; therefore no node needs to be re-expanded. This is the usual property used to implement A* with a Closed set safely.

Common mistakes

  • Forgetting to include g(n) in A*'s selection (i.e., using h instead of f).
  • Not updating or handling the Open list when a better path to an already-open node is found (need decrease-key or reinsert with better g).
  • Assuming polynomial-time guarantees: A* is exponential in worst case (depends on heuristic quality).
  • When doing proofs, omitting the assumption that step costs are non-negative or that h(goal)=0.

For your exam

Kinds of questions you will see:

  • Definitions: define admissible and consistent heuristics, f/g/h, Open/Closed.
  • Short notes: compare greedy best-first vs A* (completeness, optimality, when to use each).
  • Derivations/proofs: prove A* is optimal with admissible h (tree search) or prove that consistency implies no node re-expanded.
  • Numericals: run A* and greedy step-by-step on a small graph with given costs and heuristics (draw Open/Closed and show f/h values at each step).
  • Diagrams: draw a graph and label costs and heuristics; show order of expansion and final path. What a full-marks answer includes:
  • Clear statement of assumptions (non-negative costs, h(goal)=0, branching factor, admissibility/consistency used where needed).
  • Correct step-by-step expansions with Open/Closed states and exact f/g/h numbers.
  • For proofs: explicit contradiction argument showing a lower-cost goal would have been expanded earlier, and clear reference to admissibility.

Quick check

  1. What does it mean for a heuristic to be admissible?
  2. Which value does A* minimize when choosing the next node to expand?
  3. Does consistency imply admissibility or the other way round? Answers: 1. h(n) ≤ true minimum cost from n to a goal for all n (never overestimates). 2. f(n) = g(n) + h(n). 3. Consistency implies admissibility (but admissibility does not imply consistency).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?