iii. A*, IDA* and Branch and Bound

A* Search

Purpose: Find the shortest path from a start node to a goal node in a weighted graph, using a heuristic estimate of remaining distance to guide the search toward the goal, in O(E log V) time worst case (typically far less in practice with a good heuristic).

Algorithm

1. Maintain a priority queue of nodes ordered by f(n) = g(n) + h(n), where g(n) is the known cheapest cost from start to n, and h(n) is a heuristic estimate of the cost from n to the goal.
2. Start by placing the start node in the queue with g = 0.
3. Repeatedly pop the node with the smallest f value.
4. If it’s the goal, stop — the path has been found.
5. Otherwise, for each neighbor, compute the tentative cost of reaching it through the current node. If this is better than any previously known cost, update it, record the current node as its parent, and push it into the queue with its new f value.
6. Repeat until the goal is popped (success) or the queue empties (no path exists). Reconstruct the path by following parent pointers backward from the goal.

Code

struct AStar {
    struct Edge { int to, weight; };
    vector<vector<Edge>> adj;
    int n;
 
    AStar(int n) : n(n), adj(n) {}
 
    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
    }
 
    vector<int> findPath(int start, int goal, function<int(int)> heuristic) {
        vector<int> g(n, INT_MAX), parent(n, -1);
        vector<bool> closed(n, false);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> open;
 
        g[start] = 0;
        open.push({heuristic(start), start});
 
        while (!open.empty()) {
            auto [f, u] = open.top(); open.pop();
            if (closed[u]) continue;
            closed[u] = true;
            if (u == goal) break;
 
            for (auto& e : adj[u]) {
                int tentative = g[u] + e.weight;
                if (tentative < g[e.to]) {
                    g[e.to] = tentative;
                    parent[e.to] = u;
                    open.push({tentative + heuristic(e.to), e.to});
                }
            }
        }
 
        vector<int> path;
        if (g[goal] == INT_MAX) return path;
        for (int v = goal; v != -1; v = parent[v]) path.push_back(v);
        reverse(path.begin(), path.end());
        return path;
    }
};

Complexity

• Time: O(E log V) worst case (degenerates to Dijkstra when h = 0); typically far fewer nodes expanded with an informative heuristic
• Space: O(V)

Proof of Correctness

Claim: If h is admissible (never overestimates the true remaining cost) and consistent (h(u) ≤ weight(u, v) + h(v) for every edge), A* returns the true shortest path.

Invariant: Whenever a node u is popped from the open queue (closed), g[u] equals the true shortest distance from start to u.

Proof by induction on pop order: The start node trivially has g = 0, correct. Assume the invariant holds for all nodes popped before u. Since h is consistent, f values are non-decreasing along any path, so any path to u through an unclosed node would have f ≥ f(u) at the time u is popped — meaning no cheaper route to u remains undiscovered. Hence g[u] at pop time is already the minimum possible, proving the invariant.

Termination and optimality: By the invariant, when the goal is popped, g[goal] is the true shortest distance, and the parent pointers trace out an actual shortest path. ∎

Variants / Use Cases

• Weighted A* $\to$ inflates h by a factor > 1 to trade optimality for speed
• IDA (Iterative Deepening A)** $\to$ depth-first variant with O(V) space, repeatedly deepening an f-value threshold
• Bidirectional A* $\to$ searches simultaneously from start and goal to meet in the middle
• Jump Point Search $\to$ grid-specific pruning that skips symmetric paths for large speedups
• D / D Lite** $\to$ dynamic replanning variants for changing graphs, used in robotics path planning
• Pathfinding in games, GPS navigation, robotics motion planning $\to$ primary real-world applications

Iterative Deepening

IDDFS: run depth-limited DFS with limit $1,2,3,\dots$ until the goal is found. You get BFS’s optimal depth with DFS’s $O(d)$ memory. Re-exploring shallow levels costs only a constant factor, since the last level dominates ($b^d$).

IDA*: the same, but the limit is on $f=g+h$ (cost so far + admissible heuristic). Each iteration’s new limit is the smallest $f$ that exceeded the previous one. It’s the standard for 15-puzzle-type problems where A*‘s memory explodes.

IDDFS

bool dls(State& s, int depth, int limit) {
    if (isGoal(s)) return true;
    if (depth == limit) return false;
    for (auto& mv : moves(s)) {
        apply(s, mv);
        if (dls(s, depth + 1, limit)) return true;
        undo(s, mv);
    }
    return false;
}
for (int limit = 0; ; limit++) if (dls(start, 0, limit)) { /* answer = limit */ break; }

IDA*

const int FOUND = -1;
int search(State& s, int g, int bound, int lastMove) {
    int f = g + h(s);
    if (f > bound) return f;
    if (isGoal(s)) return FOUND;
    int nextBound = INT_MAX;
    for (auto& mv : moves(s)) {
        if (isInverse(mv, lastMove)) continue;        // don't undo the previous move
        apply(s, mv);
        int t = search(s, g + cost(mv), bound, mv);
        if (t == FOUND) return FOUND;
        nextBound = min(nextBound, t);
        undo(s, mv);
    }
    return nextBound;
}
int bound = h(start);
while (true) {
    int t = search(start, 0, bound, -1);
    if (t == FOUND) break;            // answer = bound
    if (t == INT_MAX) break;          // unreachable
    bound = t;
}

Heuristics (15-puzzle)

• Manhattan distance of tiles: admissible.
• • linear conflict (two tiles in their goal row but reversed: +2): still admissible, much stronger.
• Pattern databases: precomputed exact costs for subsets of tiles.

When to use

• Answer depth is small (≤ 20–50) but the state space is huge.
• Memory is tight (A* would store millions of states).
• “Minimum number of moves” puzzles: sliding puzzles, Rubik’s, the addition-chain problem, “Power Calculus” (UVa 1374), Egyptian fractions.

Pitfalls

• Must apply/undo in place, so no copying of states per call.
• Prune moves that immediately undo the previous move.
• A non-admissible heuristic loses optimality.

Branch and Bound

Backtracking for optimisation: maintain the best solution found so far (the incumbent), and prune any branch whose optimistic bound cannot beat it.

The skeleton

long long best = INF;                                   // incumbent (minimisation)
 
void solve(State& s) {
    if (complete(s)) { best = min(best, cost(s)); return; }
    if (lowerBound(s) >= best) return;                  // PRUNE
    for (Choice c : orderedCandidates(s)) {
        apply(s, c);
        solve(s);
        undo(s, c);
    }
}

Three ingredients determine whether it works:

1. The bound — a fast, optimistic estimate of the best completion.
2. The incumbent — found early by a good heuristic, so pruning starts immediately.
3. The branching order — explore promising branches first.

The bound is everything

A bound must be admissible (never worse than the true optimum) and cheap. Stronger bounds prune more but cost more; the trade-off is the whole engineering problem.

Problem	Bound
TSP	sum of the two cheapest edges per city, halved
TSP (stronger)	MST of the unvisited cities + two connecting edges
TSP (strongest practical)	Held-Karp 1-tree Lagrangian bound
Knapsack	the fractional (LP) relaxation
Max clique	a greedy colouring of the candidate set
Scheduling / makespan	$\max (\text{average load},\text{longest job})$
Assignment	the Hungarian LP relaxation
Bin packing	$\lceil \text{total size}/\text{capacity}\rceil$
Graph colouring	max clique size
Any IP	the LP relaxation

The LP relaxation is the general answer — solve the fractional version and use its value as the bound. That is exactly what commercial MIP solvers do.

The colouring bound for max clique

Greedily colour the candidate vertices; a clique cannot be larger than the number of colours used. Cheap, and dramatically effective — it is why modern max-clique solvers handle graphs with hundreds of vertices.

Search order

Strategy	Memory	Note
Depth-first	$O(d)$	finds an incumbent quickly; the default
Best-first	$O(\text{tree})$	expands the most promising node; fewest nodes but memory-hungry
Breadth-first	huge	rarely used
Iterative deepening	$O(d)$	best-first behaviour with DFS memory
Depth-first with restarts	$O(d)$	escapes bad early choices

Depth-first is the practical default: it reaches a complete solution fast, which gives an incumbent, which enables pruning.

Getting a good incumbent early

Pruning only works once best is tight. So:

1. Run a greedy or heuristic first (LPT, nearest neighbour, local search) and seed best with its value.
2. Order the branches so the greedy choice is explored first.
3. Consider beam search on the first few levels to find a strong incumbent cheaply.

A good incumbent is often worth more than a better bound.

Branch and bound vs the alternatives

Situation	Method
Optimisation, good bound available	branch and bound
Feasibility (any solution)	backtracking
Small $n$, subset structure	bitmask DP
Splittable	meet in the middle
Exact cover structure	DLX
Integer linear program	branch and bound on the LP (branch and cut)
Approximate answer acceptable	heuristics

Branch and cut, branch and price

The industrial versions:

• Branch and cut — add violated cutting planes to tighten the LP relaxation before branching. This is how CPLEX and Gurobi solve TSP instances with tens of thousands of cities to proven optimality.
• Branch and price — generate variables (columns) lazily; used for vehicle routing and crew scheduling.

Not contest tools, but worth knowing that “NP-hard” does not mean “unsolvable in practice” — with good bounds, instances far beyond the exponential-DP range are routinely solved exactly.

Practical notes

• Prune before recursing, not after — checking the bound at the top of the call saves an entire subtree.
• Compute the bound incrementally where possible; a bound that costs $O(n)$ per node can dominate the runtime.
• Use $\ge$ rather than $>$ in the pruning test when you only need one optimal solution.
• Track the node count while debugging; if it is not dropping sharply as you add pruning, the bound is too weak.
• For contests, check the constraints first — if $n\le 22$ there is probably an intended bitmask DP, and branch and bound is unnecessary.

15-Puzzle

Problem. Tiles numbered $\mathrm{1..}{n}^2-1$ in an $n\times n$ grid with one blank. A move slides an adjacent tile into the blank. Reach the goal configuration in the fewest moves.

Solvability — the parity invariant

Not every configuration is reachable. Define:

• $\mathrm{inv}$ = the number of inversions in the tile sequence (reading row by row, ignoring the blank);
• $r$ = the blank’s row, counted from the bottom, 1-indexed.

Board	Solvable iff
$n$ odd (e.g. 3×3)	$\mathrm{inv}$ is even
$n$ even (e.g. 4×4)	$\mathrm{inv}+r$ is odd

Why: a horizontal move changes neither $\mathrm{inv}$ nor $r$. A vertical move changes $\mathrm{inv}$ by $\pm (n-1)$ and $r$ by $\pm 1$. For $n$ odd, $n-1$ is even, so $\mathrm{inv}$ alone is invariant mod 2. For $n$ even, $n-1$ is odd, so $\mathrm{inv}$ and $r$ change parity together, and only their sum $\mathrm{inv}+r$ stays invariant mod 2. Exactly half of all configurations are reachable.

Proof: the solvability invariant

Horizontal move (blank swaps with a tile in the same row): this only swaps two adjacent positions in the row-major reading order with nothing else between them changing, so the tile sequence (ignoring the blank) is unaffected in relative order except that one tile crosses the blank’s old/new slot — since the blank itself is excluded from the inversion count, a horizontal move doesn’t change which pairs of numbered tiles are inverted at all (the sliding tile just occupies a different column in the same row; its position relative to every other numbered tile in reading order is unchanged, since no other tile moved). So $\mathrm{inv}$ changes by $0$, and the blank’s row is unchanged, so $r$ changes by $0$ too.
Vertical move (blank swaps with a tile one row up or down): the sliding tile jumps over exactly $n-1$ other tiles in the reading order (moving from row $k$ to row $k\pm 1$ skips past the rest of one full row, $n-1$ numbered tiles, in linear reading position), so it crosses $n-1$ other tiles’ relative order, changing $\mathrm{inv}$ by $\pm (n-1)$, and the move always changes $r$ by exactly $1$.
Case $n$ odd: $n-1$ is even, so every move (horizontal: $0$; vertical: $\pm (n-1)$, even) changes $\mathrm{inv}$ by an even amount — $\mathrm{inv}\mathrm{mod}2$ alone is preserved, independent of $r$, matching the table’s odd-$n$ row.
Case $n$ even: $n-1$ is odd, so a vertical move changes $\mathrm{inv}$ by an odd amount and $r$ by $1$ (also odd), so their sum changes by an even amount; a horizontal move changes both by $0$. Either way $\mathrm{inv}+r\mathrm{mod}2$ is preserved, matching the table’s even-$n$ row.
Reachability is exactly this invariant class. That the invariant is preserved shows unreachable configurations (wrong invariant value) can never be reached. That every configuration sharing the goal’s invariant value is reachable is the nontrivial direction, established constructively: any two configurations with the same invariant can be connected by an explicit sequence of moves (e.g. via 3-cycles of tiles, which can be shown to preserve the invariant and generate the full even-permutation-like structure of reachable states) — a classical result first established for the original 15-puzzle by Johnson and Story (1879) and Wilson (1974) in general. $■$

bool solvable(const vector<int>& board, int n) {
    int inv = 0, blankRow = 0;
    vector<int> a;
    for (int i = 0; i < n * n; i++) {
        if (board[i] == 0) { blankRow = n - i / n; continue; }
        a.push_back(board[i]);
    }
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = i + 1; j < (int)a.size(); j++)
            if (a[i] > a[j]) inv++;
    return (n % 2) ? (inv % 2 == 0) : ((inv + blankRow) % 2 == 1);
}

This is the invariant argument in its purest form — it settles half of all inputs in $O(n^2)$ with no search at all.

Solving it

Board	State space	Method
8-puzzle (3×3)	$9!/2=181440$	BFS over all states, or A*
15-puzzle (4×4)	$16!/2\approx 10^{13}$	IDA* with a good heuristic
24-puzzle (5×5)	$\approx 10^{25}$	IDA* with pattern databases

A* and IDA*

Use $f=g+h$ with an admissible heuristic $h$ (never overestimating):

Heuristic	Quality
Misplaced tiles	weak
Manhattan distance	the standard baseline
Manhattan + linear conflict	noticeably better
Walking distance	stronger
Pattern databases	by far the strongest; solves the 15-puzzle in milliseconds

IDA* (iterative-deepening A*) is preferred over A* here because A*‘s open list does not fit in memory for the 15-puzzle. IDA* uses $O(d)$ space:

int search(State& s, int g, int bound) {
    int f = g + h(s);
    if (f > bound) return f;                       // exceeded: report the new bound
    if (s.isGoal()) return FOUND;
    int minExceed = INF;
    for (Move m : s.moves()) {
        if (m.undoes(lastMove)) continue;          // essential pruning
        s.apply(m);
        int t = search(s, g + 1, bound);
        if (t == FOUND) return FOUND;
        minExceed = min(minExceed, t);
        s.undo(m);
    }
    return minExceed;
}
// outer loop: bound = h(start); repeat with bound = returned value

Never undoing the previous move is the single most important pruning — it halves the branching factor.

Bidirectional BFS

Since the goal is known, searching from both ends turns $b^d$ into $2b^{d/2}$. For the 8-puzzle this makes plain BFS trivial; for the 15-puzzle it helps but is not enough on its own.

God’s number

Puzzle	Maximum optimal moves
8-puzzle	31
15-puzzle	80
24-puzzle	152 (conjectured)
Rubik’s cube (quarter turns)	26
Rubik’s cube (half turns)	20

The Rubik’s cube number 20 was proved in 2010 by an exhaustive computation using coset decomposition — 35 CPU-years donated by Google.

The general lesson: state-space search

The 15-puzzle is the reference problem for the whole search toolkit:

Technique	Role
BFS	optimal, but memory-bound
A*	guided by a heuristic; still memory-bound
IDA*	A*‘s guidance with DFS memory
Bidirectional search	halves the exponent
Pattern databases	precomputed admissible heuristics
Invariant checking	rules out half the inputs instantly
Symmetry reduction	shrinks the effective state space

The same combination solves Rubik’s cube, sliding-block puzzles, Sokoban (PSPACE-complete), and general planning problems.

Why it is worth knowing

Two lessons: check for an invariant before searching (it may answer the question outright), and a good admissible heuristic beats a faster search — Manhattan distance turns an intractable 15-puzzle into a solvable one, which no amount of BFS optimisation would achieve.