Coursify

A* Optimality and Heuristic Conditions (Admissible vs. Consistent vs. Inconsistent vs. Arbitrary)

A* Optimality and Heuristic Conditions (Admissible vs. Consistent vs. Inconsistent vs. Arbitrary)

Verified Sources
Sep 12, 2026

In graph search, the A* algorithm uses evaluation function f(n)=g(n)+h(n)f(n)=g(n)+h(n) where g(n)g(n) is the path cost from the start to state nn, and h(n)h(n) is a heuristic estimate of the remaining cost to a goal. The commonly tested multiple-choice fact is:

A* guarantees optimality if the heuristic is admissible and consistent (under the standard graph-search version of A* that uses a closed list without reopening states).

A quick intuition is that admissibility means the heuristic never overestimates the true remaining cost, while consistency (a.k.a. monotonicity) imposes a “triangle-inequality-like” constraint that prevents ff-values along a path from decreasing, which in turn supports optimal goal selection in graph search.2

Key learning terms:

  • heuristic
  • admissible heuristic
  • consistent heuristic
  • A* graph search
  • optimality

Footnotes

  1. A* search algorithm - Wikipedia - Describes A* and notes optimality relations with heuristic conditions and consistency/reopening issues. ↩ ↩2

  2. CS 188: Artificial Intelligence (CS188) Lec 04 PDF - States: tree search optimal with admissible heuristic; graph search optimal with consistent heuristic; includes consistency definition. ↩

  3. Search: A* (Stanford CS221 autumn2022 module PDF) - Provides formal discussion of admissibility/consistency and how consistency implies admissibility. ↩

Admissible and Consistent Heuristics (A*)

The correct option among (i)–(iv)

Let’s map each proposed heuristic condition to A*’s optimality guarantee (for the standard graph-search interpretation):

  • (i) Arbitrary → No guarantee. A* relies on heuristic conditions to ensure the first goal found is optimal.
  • (ii) Inconsistent → Optimality guarantee is not assured in general (graph-search may require re-expansions; some variants can still be made optimal, but the usual guarantee does not hold under inconsistent heuristics without special handling).
  • (iii) Admissible and consistent → Yes, optimality is guaranteed (standard A* graph search).
  • (iv) Random → No guarantee (it is not constrained to be admissible/consistent).

Therefore, the correct choice is (iii) Admissible and consistent.

Footnotes

  1. A* search algorithm - Wikipedia - Describes A* and notes optimality relations with heuristic conditions and consistency/reopening issues. ↩ ↩2

  2. A* Search with Inconsistent Heuristics (IJCAI 2009 paper) - Discusses consequences of inconsistent heuristics and node reopening/re-expansion behavior. ↩

  3. Search: A* (Stanford CS221 autumn2022 module PDF) - Provides formal discussion of admissibility/consistency and how consistency implies admissibility. ↩ ↩2

Why consistency matters for graph-search optimality

Never overestimate

Heuristic admissibility

Ensures optimistic estimates; supports optimality arguments for search."

Triangle-inequality-like constraint

Heuristic consistency

Guarantees ff does not decrease along paths, preventing problematic re-expansions in standard graph search."

Closed list safety

A* graph search loop

With consistency, once a state is expanded, it need not be “improved later” in a way that breaks optimality."

Optimal goal cost returned

First goal selection

A* returns an optimal least-cost solution under these assumptions."

Definitions (formal conditions)

Let c(n,n′)c(n,n') be the step cost from node nn to a neighbor node n′n', and let h∗(n)h^*(n) be the true minimal cost from nn to a goal.

  1. Admissible means:
    h(n)≤h∗(n)h(n) \le h^*(n)
  2. Consistent means:
    h(n)≤c(n,n′)+h(n′)for every edge (n,n′)h(n) \le c(n,n') + h(n') \quad \text{for every edge } (n,n')

Consistency implies admissibility, and the standard A* optimality statement for graph search uses consistency.2

Key learning terms for this section:

  • cost-to-go
  • monotonicity
  • triangle inequality (heuristic form)

Footnotes

  1. Search: A* (Stanford CS221 autumn2022 module PDF) - Provides formal discussion of admissibility/consistency and how consistency implies admissibility. ↩

  2. CS 188: Artificial Intelligence (CS188) Lec 04 PDF - States: tree search optimal with admissible heuristic; graph search optimal with consistent heuristic; includes consistency definition. ↩

A* and the role of heuristic consistency (graph search view)

  1. 1
    Step 1

    A* prioritizes nodes by the smallest estimated total solution cost, using f=g+hf=g+h.

  2. 2
    Step 2

    The algorithm removes the lowest-ff node from open and expands it.

  3. 3
    Step 3

    In the standard graph-search formulation, consistency ensures that once expanded, a node will not later need re-expansion to preserve optimality.

  4. 4
    Step 4

    With admissible and consistent heuristics, when a goal node is selected for expansion (popped from open), its path cost is guaranteed minimal.

  5. 5
    Step 5

    If the heuristic is arbitrary or inconsistent, the assumptions used for the “first goal is optimal” argument no longer hold.

Admissible vs. consistent (what to remember)

"Admissible prevents overestimation; consistent additionally enforces h(n)≤c(n,n′)+h(n′)h(n) \le c(n,n') + h(n'), which is what most graph-search optimality proofs rely on for avoiding harmful re-expansions."

Footnotes

  1. Search: A* (Stanford CS221 autumn2022 module PDF) - Provides formal discussion of admissibility/consistency and how consistency implies admissibility. ↩

Inconsistent heuristics can harm the standard A* optimality argument

"With inconsistent (but admissible) heuristics, A* may expand the same node multiple times (reopen/re-expand behavior), and naive “closed list = final” reasoning no longer applies; the usual guarantee is therefore stated for admissible+consistent heuristics under the standard graph-search model." 2

Footnotes

  1. A* Search with Inconsistent Heuristics (IJCAI 2009 paper) - Discusses consequences of inconsistent heuristics and node reopening/re-expansion behavior. ↩

  2. CS 188: Artificial Intelligence (CS188) Lec 04 PDF - States: tree search optimal with admissible heuristic; graph search optimal with consistent heuristic; includes consistency definition. ↩

Common exam nuance: “admissible” vs “admissible & consistent”

Knowledge Check

Question 1 of 3
Q1Single choice

The A* algorithm guarantees optimality if the heuristic used is:

Explore Related Topics

1

Algorithms

Algorithms are finite, well-defined procedures that transform inputs into outputs, requiring correctness, efficiency, and formal properties such as definiteness and finiteness.

  • Valid algorithms must be definite, finite, have clear input/output, and be effective; correctness and efficiency are essential.
  • Analyzing an algorithm involves problem specification, pseudocode, correctness proof, and measuring time (O(⋅)O(\cdot), Θ(⋅)\Theta(\cdot), Ω(⋅)\Omega(\cdot)) and space complexity.
  • Common growth rates range from O(1)O(1) to O(2n)O(2^n), with divide‑and‑conquer recurrences like T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n).
  • Key design paradigms include divide‑and‑conquer, dynamic programming, greedy, backtracking, and branch‑and‑bound.
  • Choosing an algorithm depends on input characteristics, worst‑case vs. average performance, memory limits, stability, and preprocessing needs.
2

Ambiguity in the Grammar \(S \rightarrow ABA,\; A \rightarrow aA \mid \epsilon,\; B \rightarrow bB \mid \epsilon\)

The grammar (S\rightarrow ABA,;A\rightarrow aA\mid\epsilon,;B\rightarrow bB\mid\epsilon) is ambiguous because the two (A) nonterminals can distribute the same (a)-string in multiple ways, especially when (B) derives (\epsilon).

  • It generates the language (L(S)={a^i b^j a^k\mid i,j,k\ge0}=a^*b^a^).
  • The shortest string (a) has two distinct left‑most derivations (or parse trees), proving ambiguity.
  • Every string (a^n) with (n\ge1) can be split between the two (A) symbols in (n+1) ways, yielding multiple parse trees.
  • The ambiguity stems from both (A) producing (a^*) and (B) being able to vanish via (\epsilon).
  • An equivalent unambiguous grammar can be constructed, showing the ambiguity is a property of this grammar, not necessarily of the language.
3

Criteria for Evaluating a Search Strategy

Browse all research articles