Heuristics in Search: Meaning, Completeness/Optimality Conditions, and Admissibility Proofs

In the context of search strategies, Heuristic refers to an informative estimate used to guide exploration. Rather than expanding nodes purely by path cost so far, informed search uses a Evaluation function that combines:

• the cost already incurred ($g(n)$), and
• an estimated remaining cost ($h(n)$, from the heuristic).

A classic example is *[A search]{def="Best-first search using f(n)=g(n)+h(n)"}**, which expands nodes in order of $f(n) = g(n) + h(n).$

Intuitively, the heuristic makes the search “look ahead” by preferring nodes that seem closer (in cost) to a goal.

To reason about guarantees, we distinguish three concepts:

• Admissible heuristic
• Completeness
• Optimality

A* is commonly analyzed under the assumptions of nonnegative step costs and suitable properties of $h$. Below, we state conditions for completeness and optimality and then prove admissibility of an A* strategy based on the heuristic’s property.

Key technical terms introduced here: Heuristic, A* search, Admissible heuristic, Completeness, Optimality.

Meaning of “heuristics” in search strategies

The word “heuristics” is used because the estimate is typically derived from rules of thumb or domain knowledge that is fast but may not be perfectly accurate. Formally, in search we treat it as a function:

• $h(n)$: an estimate of the true remaining optimal cost from node/state $n$ to any goal.
• Let the true remaining optimal cost be $h^*(n)$.

Then a heuristic is admissible if: $\forall n,\; h(n) \le h^*(n).$

This definition directly connects to optimality of A* because A* uses $f(n)=g(n)+h(n)$ as a lower bound on the cost of any complete solution that goes through $n$.

Conditions on a search for completeness and optimality

There are two common “modes” of analysis:

• Tree search (no repeated-state handling)
• Graph search (uses a closed set / explored set; repeated states may be skipped or handled carefully)

Because the prompt asks for guarantees, we state widely used sufficient conditions for standard implementations of informed search (especially A* and Uniform Cost Search).

Completeness (guaranteed to find a goal if one exists)

A standard sufficient condition for completeness is:

1. Finite branching: from any node, the number of successors is finite.
2. Nonnegative step costs (especially for cost-based best-first rules).
3. Systematic expansion in increasing-cost layers (or an equivalent strategy), so that if a goal exists, it is not “skipped forever.”

Common textbook results (for graph search with nonnegative costs) typically guarantee:

• Uniform Cost Search (UCS) is complete if step costs are nonnegative and branching is finite.
• A* with a suitable priority queue ordering inherits completeness under the same broad conditions (and admissible heuristic does not “prevent” goal discovery).

Core idea: when costs are nonnegative, expanding the lowest-cost frontier prevents infinite deferral of any reachable finite-cost goal.

Important constraint: if there are negative step costs, “infinite descent” can defeat both completeness and optimality.

Optimality (least-cost solution)

Optimality depends on how $f(n)$ relates to the true solution costs.

For UCS:

• Optimality holds because it expands nodes in order of increasing $g(n)$; the first goal popped is guaranteed minimal.

For A*:

• Optimality holds if $h(n)$ is admissible, i.e. it never overestimates remaining optimal cost.

Prove admissibility of an A search strategy

There is a subtle wording issue in the prompt:

• Admissibility is a property of the heuristic $h(n)$ (and sometimes of derived bounds), not of the mere search strategy alone.
• A search algorithm (like A*) is optimal when it uses an admissible heuristic (plus standard nonnegative-cost conditions).

So the correct formal target is usually:

Prove that the heuristic used in A* is admissible, i.e. $h(n)\le h^*(n)$ for all $n$.

Below is a standard proof template. It is complete, formal, and exactly what you need to “prove admissibility” in the A* setting.

Formal proof (general form)

Let $n$ be any state in the search space. Let:

• $h^*(n)$ be the optimal remaining cost from $n$ to a goal: $h^*(n) = \\min_{\\pi \\in \\text{Paths}(n\\to \\text{goal})} \\text{cost}(\\pi).$
• $h(n)$ be the heuristic used by A*.

To prove admissibility, we must show: $h(n) \\le h^*(n)\\quad \\text{for all } n.$

A common way to complete the proof is:

1. Show that for every path $\\pi$ from $n$ to a goal, $h(n) \\le \\text{cost}(\\pi).$
2. Then, because $h^*(n)$ is the minimum over all such path costs, $h(n) \\le \\min_{\\pi} \\text{cost}(\\pi) = h^*(n).$

Therefore $h(n) \\le h^*(n)$ for all $n$, so $h$ is admissible.

From admissibility to optimality of A* (why this matters)

Even though you asked specifically to “prove admissibility,” it’s typically used to establish optimality.

Let A* expand nodes in increasing $f(n)=g(n)+h(n)$ and assume:

• Nonnegative step costs (standard condition for cost-based best-first search).
• $h$ is admissible.

Because $h(n)\le h^*(n)$, for any node $n$ we get: $f(n)=g(n)+h(n) \\le g(n)+h^*(n).$

But $g(n)+h^*(n)$ is exactly the cost of an optimal completion via $n$, so $f(n)$ is a lower bound on the cost of any solution through $n$. Consequently, when A* selects the next node with the smallest $f$, it cannot “miss” a cheaper goal solution; when a goal is selected for expansion (or popped, depending on the implementation details), its path cost is minimal among all solutions.