Informed (Heuristic) Search — Greedy Best-First and A*

Heuristic functions and evaluation functions, greedy best-first search, A* search with f = g + h traced step by step, admissible and consistent heuristics and why they guarantee optimality, dominance and designing heuristics from relaxed problems (8-puzzle examples), memory-bounded variants (IDA*, weighted A*), and local search in brief.

Section 79 practice questions

Heuristics

Uninformed search explores blindly. Informed search uses problem-specific knowledge in a heuristic function $h(n)$ : an estimate of the cheapest cost from node $n$ to a goal (with $h(\text{goal}) = 0$ ). Examples: straight-line distance in route finding; misplaced tiles or Manhattan distance in the 8-puzzle.

Best-first search expands the frontier node with the lowest evaluation function $f(n)$ :

Algorithm	$f(n)$	Behaviour
Uniform-cost search	$g(n)$	cost so far only (no heuristic)
Greedy best-first	$h(n)$	rushes towards the goal; fast but not optimal
A*	$g(n) + h(n)$	estimated total cost of the cheapest solution through $n$

Greedy best-first search

Always expands the node that looks closest to the goal. It can be very fast, but ignores the cost already paid, so it is not optimal and, in infinite spaces or with tree search on graphs with cycles, not complete (it can oscillate).

A* search

f(n) = g(n) + h(n).

Python

import heapq

def astar(start, goal, succ, h):          # succ(n) yields (neighbour, step_cost)
    frontier = [(h(start), 0, start, [start])]
    best_g = {start: 0}
    while frontier:
        f, g, n, path = heapq.heappop(frontier)
        if n == goal:
            return path, g
        if g > best_g.get(n, float("inf")):
            continue                       # stale queue entry
        for m, c in succ(n):
            g2 = g + c
            if g2 < best_g.get(m, float("inf")):
                best_g[m] = g2
                heapq.heappush(frontier, (g2 + h(m), g2, m, path + [m]))
    return None

A* (highlighted path S–B–D–G, cost 7) expands S, B, A, D, G and never needs C.

Admissibility and consistency

Property	Definition	Guarantees
Admissible	$0 \le h(n) \le h^*(n)$ — never overestimates	A* tree search is optimal
Consistent (monotone)	$h(n) \le c(n, a, n') + h(n')$ for every successor, $h(\text{goal}) = 0$	A* graph search is optimal; $f$ never decreases along a path; each node is expanded at most once

Consistent ⇒ admissible (not conversely). Most natural admissible heuristics are also consistent.

Why A* is optimal (sketch): when A* is about to expand a suboptimal goal $G_2$ with $f(G_2) = g(G_2) > C^*$ , some node $n$ on an optimal path is still on the frontier with $f(n) = g(n) + h(n) \le C^*$ (admissibility), so $n$ would be expanded first.

A* is also optimally efficient: no other optimal algorithm using the same heuristic is guaranteed to expand fewer nodes. It expands every node with $f(n) < C^*$ .

Designing heuristics

Relaxed problems: the exact cost of a problem with fewer restrictions is an admissible heuristic. In the 8-puzzle, letting a tile move anywhere gives misplaced tiles ( $h_1$ ); letting it move to any adjacent square gives Manhattan distance ( $h_2$ ).
Dominance: if $h_2 \ge h_1$ everywhere (both admissible), $h_2$ is better. $\max(h_1, h_2, \dots)$ of admissible heuristics is admissible and dominates each.
Pattern databases: precomputed exact costs of sub-problems.
Effective branching factor $b^*$ : the branching factor a uniform tree of depth $d$ would need to contain the $N$ expanded nodes; good heuristics have $b^*$ close to 1.

Memory-bounded and approximate variants

Variant	Idea
IDA*	iterative deepening on $f$ -cost thresholds; memory $O(bd)$
RBFS, SMA*	recursive / memory-bounded best-first
Weighted A*	$f = g + w\,h$ , $w > 1$ : faster, cost $\le w\,C^*$
Beam search	keep only the best $k$ nodes per level (incomplete)

Local search in brief

When only the final state matters (scheduling, configuration, 8-queens), keep one current state and move to better neighbours: hill climbing (gets stuck in local maxima and plateaus), random restarts, simulated annealing (sometimes accept worse moves, with probability $e^{-\Delta/T}$ that falls as the temperature $T$ cools), and genetic algorithms.

Quick revision

Practice questions

GATE-style questions: 3 one-mark and 6 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.

Q1MCQ2 marks

Directed graph with step costs (ties broken alphabetically): S→A (1), S→B (4), A→C (2), A→D (5), B→D (1), C→G (6), D→G (2). Start S, goal G. Heuristic $h$ : S 5, A 5, B 1, C 5, D 2, G 0. Graph search; goal test on expansion.

In which order does A* expand the nodes?

Q2NAT2 marks

The value of $f = g + h$ of node C when A* generates it is ______.

Q3MCQ1 mark

A heuristic $h$ is admissible if, for every node $n$ ,

Q4MSQ2 marks

Which statements about heuristic search are correct (positive step costs)?

One or more options are correct.

Q5NAT2 marks

In the 8-puzzle, the state below must reach the goal shown. The sum of Manhattan distances of the tiles (not counting the blank) is ______.

state			goal
2	8	3	1	2	3
1	6	4	8	_	4
7	_	5	7	6	5

Q6MCQ1 mark

Two admissible heuristics satisfy $h_2(n) \ge h_1(n)$ for every node. Then

Q7NAT1 mark

At a node, two admissible heuristics give $h_1 = 3$ and $h_2 = 5$ . The largest admissible estimate obtainable by combining them, $\max(h_1, h_2)$ , is ______.

Q8MCQ2 marks

A* graph search (which never re-expands a closed node) is guaranteed to return an optimal solution when the heuristic is

Q9NAT2 marks

Weighted A* expands nodes in order of $f(n) = g(n) + w\,h(n)$ with an admissible $h$ and $w = 2$ . If the optimal solution cost is $C^* = 10$ , the cost of the solution it returns is guaranteed to be at most ______.