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-06-10 09:23
#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)$$

The Correspondence between A Algorithm and IDA Algorithm

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, never exceeding the actual cost (never overestimating).

State Design and Algorithm Derivation

Taking the classic grid graph/puzzle transformation as an example, we derive the art of designing $h(x)$ and the state transitions of IDA*.

1. Classic Evaluation Function Design Models

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

2. IDA* State Transition and Pruning Derivation

Define the function bool dfs(int dep, int max_dep, int prev_op), with the state implicitly recorded in global or bitwise operations.

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

$$h(next) = h(current) + \text{Delta } h$$

For example: moving a misplaced element back to its correct position results in $\text{Delta } h = -1$; moving towards a more misaligned position results in $\text{Delta } h = +1$.

C++ Standard Source Code

Below is the standard industrial-grade template for the IDA* algorithm solving grid path/state transformation problems, which includes incremental evaluation functions and strict boundary pruning.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

struct Point {
    int x, y;
};

// Assume target coordinates
const Point target = {3, 3};
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// Extremely concise and strictly admissible Manhattan distance heuristic function
inline int get_heuristic(int cx, int cy) {
    return std::abs(cx - target.x) + std::abs(cy - target.y);
}

bool success = false;
int next_bound = 2e9; // Record the minimum out-of-bounds cost for the next iteration

// dep: current depth, bound: maximum $f(x)$ limit for the current round, px/py: current coordinates, pre_dir: previous direction (for deduplication)
void idastar_dfs(int dep, int bound, int cx, int cy, int pre_dir) {
    int h = get_heuristic(cx, cy);
    int f = dep + h;

    // Core heuristic pruning: current actual cost + optimistic estimated cost exceeds threshold
    if (f > bound) {
        next_bound = std::min(next_bound, f); // Dynamically update the tighter upper bound for the next iteration
        return;
    }

    if (cx == target.x && cy == target.y) {
        success = true;
        return;
    }

    for (int i = 0; i < 4; ++i) {
        // Logical pruning: prevent moving back to the same spot (exclude operations that cancel each other)
        if ((i ^ 1) == pre_dir && dep > 0) continue; 

        int nx = cx + dx[i];
        int ny = cy + dy[i];

        // Feasibility pruning: boundary check (assuming grid size is 4x4)
        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

        idastar_dfs(dep + 1, bound, nx, ny, i);
        if (success) return; // Instantly break the recursion tree, refusing unnecessary backtracking
    }
}

int solve(int start_x, int start_y) {
    // Set the initial bound directly to the heuristic value of the initial state
    int bound = get_heuristic(start_x, start_y);

    while (!success && bound <= 100) { // 100 is a safe search depth upper limit
        next_bound = 2e9;
        idastar_dfs(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; // Iteratively deepen the bound value
    }
    return -1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int sx, sy;
    if (std::cin >> sx >> sy) {
        int ans = solve(sx, sy);
        std::cout << ans << "\n";
    }
    return 0;
}

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, in seeking the shortest path, setting the evaluation function to "the square of the Manhattan distance" directly violates the $h(x) \le h^*(x)$ principle, causing IDA* to prematurely prune the truly optimal path due to over-optimistic evaluation of the first path taken, ultimately resulting in a WA (wrong answer).
  2. *Incorrect updates to IDA iterative bounds leading to infinite loops or TLE** When backtracking is triggered by f > bound pruning in DFS, the next round's bound cannot simply be incremented with bound++. If the problem's steps are non-continuous (e.g., each transformation costs more than 1), mechanically executing bound++ will lead to countless useless searches. It is essential to introduce a global variable next_bound = min(next_bound, f), precisely aligning the next round's bound with the minimum cost among all out-of-bounds branches. Forgetting to reset next_bound to infinity will prevent the bound from increasing, leading to a deadlock in the first layer loop.

Classic NOIP/Luogu Problems

1. Luogu P1379 Eight Puzzle Problem

2. Luogu P2324 [SCOI2005] Knight's Spirit

Original Source: local://4.3
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS