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:
- 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.
- Suppose for contradiction there is a different goal G' with cost C < C* (so A* returned a non-optimal goal).
- 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).
- 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.
- 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})orO(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):
- Open = {S(h=11)}. Pop S; expand neighbors A(h=1) and B(h=50). Open = {A, B}.
- Pop A (h=1). Expand A -> G(h=0). Open = {G(h=0), B(h=50)}.
- 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.
- 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)}.
- Pop B (f=11). Expand B -> G: g(G)=11 f(G)=11+0=11. Open contains A(f=12), G(f=11).
- 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):
- 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)}.
- Pop A (tie-breaking arbitrary). Expand A -> G: g(G)=5 f(G)=5+0=5. Open = {B(f=5), G(f=5)}.
- 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
- What does it mean for a heuristic to be admissible?
- Which value does A* minimize when choosing the next node to expand?
- 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?