NeFut Logo NeFut
中 Admin Login

Heuristic Search and A* Algorithm: In-Depth Analysis and Implementation

Published at: 2026-05-27 09:17 Last updated: 2026-07-05 08:49
#C++ #Tutorial

Core Logic and Mathematical Principles

The essence of Heuristic Search lies in introducing external prior knowledge to quantitatively assess the unknown search space, thereby breaking the disorder of blind search. Its mathematical foundation is the Evaluation Function:

$$f(x) = g(x) + h(x)$$

A and IDA

From the perspective of graph theory and state space search, the underlying control flow and spatial topology models of A and IDA are fundamentally different:

The essence of A is "heuristic heap-optimized BFS" based on explicit graph space (using global queues and closed lists to trade space for time), while the essence of IDA is "cost-bound pruned iterative deepening DFS" based on implicit tree space (using backtracking stacks and dynamic thresholds to trade time for space).

The Relationship between A Algorithm and IDA Algorithm

The engine of the IDA* algorithm is Iterative Deepening Search (IDS): it is essentially the most straightforward depth-first search.

Both aim to find the "optimal solution" (i.e., the solution with the lowest cost and shallowest depth). The first time A pops the goal state from the priority queue, it is guaranteed to be the optimal solution. The first time IDA encounters the goal state in a given iteration, it is also guaranteed to be the optimal solution.

A requires extremely fast response times and relatively abundant memory. IDA optimizes for space, trading time for space. The depth of the solution is usually controllable; using A* might cause memory overflow.

The Design Principle of the Evaluation Function $h(x)$: Admissibility

Let the true shortest distance from state $x$ to the goal be $h^*(x)$. To ensure that the algorithm can find the optimal solution, $h(x)$ must satisfy:

$$0 \le h(x) \le h^*(x)$$

That is, $h(x)$ must be optimistic and never exceed the actual cost.

State Design and Algorithm Derivation

Taking the classic grid path and sliding puzzle transformation as examples, we briefly describe the problem and derive the construction method of $h(x)$ and the state transitions of IDA*.

Construction Models for the Evaluation Function $h(x)$

$$h(x) = |x.row - T.row| + |x.col - T.col|$$

$$h(x) = \sum_{i} (|tile_i.row - T_i.row| + |tile_i.col - T_i.col|)$$

Logical Proof of Admissibility The evaluation function must satisfy $0 \le h(x) \le h^*(x)$. In sliding puzzle problems, a single legal swap operation moves only one numbered tile. Therefore, the maximum efficiency of a single operation in repairing the Hamming distance is 1. Suppose the number of misplaced elements is $k$, i.e., $h(x) = k$. Since each operation can place at most one misplaced tile back to its correct position, the true minimum number of operations required to restore all $k$ misplaced elements, $h^*(x)$, must be greater than or equal to $k$. This derives that $h(x) \le h^*(x)$ holds, satisfying the underestimation of the remaining cost and guaranteeing the correctness of the algorithm.

In sliding puzzle problems, $$h_{Hamming}(x) \le h_{Manhattan}(x) \le h^*(x)$$ Therefore, Manhattan distance is used as the evaluation function.

IDA* State Transition and Pruning Derivation

Define a recursive DFS function, with the state implicitly recorded in global arrays or bitwise operations.

$$\text{if } dep + h(current) > bound \text{ then return false}$$

Proof of Pruning Safety The $dep$ in the equation is equivalent to the actual cost $g(x)$ already paid along the current path. Since the evaluation function satisfies admissibility $h(current) \le h^*(current)$, the lower bound of the true total cost that can be achieved along the current branch is $dep + h(current)$. If this lower bound already exceeds the current iteration's depth limit ($dep + h(current) > bound$), since the true remaining cost will only be greater or equal, we must have $dep + h^*(current) > bound$. This mathematically proves that along this branch, it is absolutely impossible to find the optimal solution within the current limit, and therefore triggering the pruning is absolutely safe.

$$h(next) = h(current) + \Delta h$$

Mathematical Principle of Incremental Maintenance State transitions typically have high locality. Taking the sliding puzzle problem as an example, each legal move essentially swaps only one specific numbered tile with the blank space, while the relative coordinates of all other tiles on the board remain unchanged. Suppose the tile that moves during this transition is $v$, with its Manhattan distance before the move being $dist_{old}(v)$ and after the move being $dist_{new}(v)$. At this point, the global evaluation delta can be precisely quantified as the local change: $\Delta h = dist_{new}(v) - dist_{old}(v)$. The algorithm only needs $O(1)$ time to compute this change and add it to the current evaluation, completing the efficient transition of $h(x)$.

IDA* Core Code Template

This code solves the problem of finding the minimum number of moves (shortest path) from any given starting point $(start\_x, start\_y)$ to the fixed goal point $(3, 3)$ on a $4 \times 4$ grid matrix. Although this scenario does not include obstacles (the shortest path in an open grid is simply the Manhattan distance), it provides a standard and core template for the IDA* algorithm that can be directly extended to complex maze pathfinding with obstacles, 15-puzzle problems, or other state-space transformation problems.

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// Note the order of dx, dy: 0 and 1 correspond to up and down, 2 and 3 correspond to left and right,
// ensuring that XOR 1 (i ^ 1) correctly represents the opposite direction

int target_x = 3, target_y = 3;
int next_bound; // Record the minimum out-of-bounds cost for the next iteration
bool success;

inline int h(int cx, int cy) {
    return abs(cx - target_x) + abs(cy - target_y);
}

void idastar(int dep, int bound, int cx, int cy, int pre_dir) {
    int f = dep + h(cx, cy);

    // Heuristic pruning: f(x) exceeds the current depth limit, update the relaxed bound for the next round and backtrack
    if (f > bound) {
        next_bound = min(next_bound, f); 
        return;
    }

    if (cx == target_x && cy == target_y) {
        success = true;
        return;
    }

    for (int i = 0; i < 4; ++i) {
        // Logical pruning: use bitwise operation (i ^ 1) to eliminate backtracking
        if (dep > 0 && (i ^ 1) == pre_dir) continue; 

        int nx = cx + dx[i], ny = cy + dy[i];
        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

        idastar(dep + 1, bound, nx, ny, i);

        // Break through the recursion tree: once a solution is found, return immediately, refusing unnecessary backtracking
        if (success) return; 
    }
}

int solve(int start_x, int start_y) {
    int bound = h(start_x, start_y);
    success = false;

    while (!success && bound <= 100) { 
        next_bound = 2e9; 
        idastar(0, bound, start_x, start_y, -1);
        if (success) return bound;
        if (next_bound == 2e9) break; // The entire connected component has been searched, no solution
        bound = next_bound; // Iterative deepening: precisely raise the bound to the minimum cost among all pruned nodes
    }
    return -1;
}

next_bound Optimization

if (f > bound) {
next_bound = min(next_bound, f); 
return;
}

In many non-grid graph problems (such as complex graph shortest paths or models where the single-step cost is not 1), state transition costs may be discrete and non-continuous. If we mechanically execute bound++ (making it 6) for the next round, but there may be no legal state in the entire search space with a total cost of exactly 6, this round of search will instantly enter and immediately be completely pruned, wasting a full DFS traversal of the entire board. Through min(next_bound, f), the algorithm can precisely pinpoint the next threshold, directly raising the bound to the "nearest step that is truly likely to be explored in the next round."

NOIP Practical Pitfall Guide

  1. The evaluation function does not meet admissibility ($h(x) > h^*(x)$) leading to non-optimal answers: When designing complex graph theory or combinatorial optimization problems, some contestants mistakenly inflate the estimated value in pursuit of rapid pruning. For example, setting the evaluation function to the square of the Manhattan distance directly violates the $h(x) \le h^*(x)$ principle, causing the truly optimal path with slightly higher initial cost to be incorrectly pruned, ultimately resulting in WA.
  2. *Incorrect updates to IDA iterative bounds leading to infinite loops or TLE**: When backtracking is triggered by pruning in DFS, the next round's bound cannot simply be incremented. If the problem's step costs are not uniformly 1, mechanically incrementing will lead to countless useless searches. A global variable must be introduced to precisely align the next round's bound with the minimum cost among all out-of-bounds branches. Forgetting to reset the bound variable to infinity will prevent the bound from increasing, causing a deadlock at the first layer.

Classic Problem Analysis and Core Code

UVA10181: 15-Puzzle Problem

On a 4x4 board, there are numbered tiles 1-15 and one blank space. Find the minimum number of moves to transform the scrambled state into the ordered state. The maximum number of steps is limited to 45. Core Idea: Design the evaluation function as the sum of Manhattan distances from the current positions of all non-blank tiles to their target positions. If a move increases the distance, it means $f(x)$ increases.

int a[5][5];
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

// Calculate the sum of Manhattan distances, ignoring the blank space (number 0)
inline int get_h() {
    int res = 0;
    for (int i = 1; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
            if (a[i][j] == 0) continue;
            // Map 1-15 to coordinates using (val-1) to find the target position
            int tx = (a[i][j] - 1) / 4 + 1;
            int ty = (a[i][j] - 1) % 4 + 1;
            res += abs(i - tx) + abs(j - ty);
        }
    }
    return res;
}

bool dfs(int dep, int bound, int pre_dir, int zx, int zy) {
    int hv = get_h();
    if (dep + hv > bound) return false;
    if (hv == 0) return true; // Evaluation is 0, meaning all tiles are at their target positions

    for (int i = 0; i < 4; ++i) {
        if (dep > 0 && (i ^ 1) == pre_dir) continue;
        int nx = zx + dx[i], ny = zy + dy[i];
        if (nx < 1 || nx > 4 || ny < 1 || ny > 4) continue;

        swap(a[zx][zy], a[nx][ny]); 
        if (dfs(dep + 1, bound, i, nx, ny)) return true;
        swap(a[zx][zy], a[nx][ny]); // Backtracking: restore the scene
    }
    return false;
}

$N$ (total inversions): The number of pairs $(i, j)$ satisfying $i < j$ and $a_i > a_j$ in the sequence (excluding 0). $R$ (row number of the blank space): top row $R=1$, bottom row $R=4$.

Left/right moves: total change = $0 + 0 = 0$ (even). Up/down moves: total change = $\Delta N + \Delta R = \text{odd} + \text{odd} = \mathbf{even}$.

Any legal move in the 15-puzzle preserves the parity of the sum of the total inversions and the blank space row number, thereby strictly partitioning the $16!$ full permutation state space into two equal-sized, disconnected components.

Use $O(1)$ time for parity pre-check; if it is an unsolvable state, directly output -1.

P2324 [SCOI2005] Knight's Spirit

Problem Description: On a 5x5 board, there are black and white knights and one blank space. Knights move in an "L" shape. Determine whether the current board can be transferred to the given target board within 15 moves. Core Idea: Design $h(x)$ as the number of knights not in their target positions (Hamming distance). Since one move can correct at most one knight's position, $h(x)$ perfectly satisfies admissibility.

int a[6][6];
// Target board state (according to the given final configuration)
const int target[6][6] = {
    {0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 1},
    {0, 0, 1, 1, 1, 1},
    {0, 0, 0, 2, 1, 1},
    {0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0}
};
// 8 directions for the knight's L-shaped move
const int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

inline int get_h() {
    int res = 0;
    for (int i = 1; i <= 5; ++i)
        for (int j = 1; j <= 5; ++j)
            if (a[i][j] != target[i][j]) res++;
    return res;
}

bool dfs(int dep, int bound, int zx, int zy) {
    int hv = get_h();
    // When the knight moves, the blank space also participates in the swap, so the evaluation tolerance is relaxed to bound + 1
    if (dep + hv > bound + 1) return false; 
    if (hv == 0) return true;

    for (int i = 0; i < 8; ++i) {
        int nx = zx + dx[i], ny = zy + dy[i];
        if (nx < 1 || nx > 5 || ny < 1 || ny > 5) continue;

        swap(a[zx][zy], a[nx][ny]);
        if (dfs(dep + 1, bound, nx, ny)) return true;
        swap(a[zx][zy], a[nx][ny]);
    }
    return false;
}

Total state space: $25! / (12! \cdot 12! \cdot 1!) \approx 4.4 \times 10^{11}$.

If all 25 pieces were distinct, it would be $25!$. Divide by the repeated factors: $/ (12! \cdot 12! \cdot 1!)$.

[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS