启发式搜索与 A* 算法：深度解析及实现

核心逻辑与数学原理

启发式搜索（Heuristic Search）的核心在于引入外部先验知识，对未知的搜索空间进行定量评估，从而打破盲目搜索的无序性。其数学基石是估价函数（Evaluation Function）：

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

$g(x)$：从初始状态到当前状态 $x$ 的 实际代价（已知、确定）。
$h(x)$：从当前状态 $x$ 到目标状态的 估计代价（未知、预测）。

A 算法与 IDA 算法的对位关系

*A 算法**：基于广度优先搜索（BFS）框架。利用优先队列（堆）维护状态，每次弹出 $f(x)$ 最小的节点进行扩展。
*IDA 算法**：基于迭代加深搜索（IDS）框架。用深度优先搜索（DFS）进行遍历，当当前节点的 $f(x) > max\text{_}dep$ 时直接截断回溯。

估价函数 $h(x)$ 的设计铁律：可采纳性（Admissibility）

设从状态 $x$ 到达目标的真正最短距离为 $h^*(x)$。为了保证算法能搜到最优解，$h(x)$ 必须满足：

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

即 $h(x)$ 必须是 乐观的，绝不能超过实际代价（绝不夸大）。

若 $h(x) = 0$：算法退化为普通的 Dijkstra 或 IDS，毫无启发效果，状态空间爆炸。
若 $h(x) = h^*(x)$：算法将化身为“上帝视角”，笔直走向目标状态，零盲目分支。
若 $h(x) > h^*(x)$：剪枝过狠，虽然搜索速度极快，但会错失最优解，导致算法正确性崩溃。

状态设计与算法推导

以经典的网格图/数码变换为例，推导 $h(x)$ 的设计艺术与 IDA* 的状态转移。

1. 经典估价函数设计模型

曼哈顿距离（Manhattan Distance）：若只能在网格中上下左右移动，状态 $x$ 与目标状态 $T$ 之间的各个点坐标差的绝对值之和。

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

海明距离 / 错位点数（Hamming Distance）：当前状态中与目标状态位置不符的元素个数。常用于状态变换步数恒定为 $1$ 的图论模型。

2. IDA* 状态转移与剪枝推导

定义函数 bool dfs(int dep, int max_dep, int prev_op)，状态隐式记录在全局或位运算中。

核心剪枝方程：在 DFS 的每一步，实时计算：

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

增量式 $h(x)$ 维护（关键优化）：若每一步转移都重新遍历整个状态去计算 $h(x)$，复杂度将恶化为 $O(Size)$。高效的实现是计算转移带来的 差值变动（Delta 维护）：

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

例如：将一个错位元素移回正确位置，$\text{Delta } h = -1$；移向更错位置，$\text{Delta } h = +1$。

C++ 标准源码

以下为 IDA* 算法解决网格路径/状态变换问题的标准工业级模板，包含增量式估价函数和严格的限界剪枝。

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

struct Point {
    int x, y;
};

// 假设目标坐标
const Point target = {3, 3};
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 极致精简且严格可采纳的曼哈顿距离估价函数
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; // 记录下一轮迭代的最小越界代价

// dep: 当前深度, bound: 当前轮次最大 $f(x)$ 限制, px/py: 当前坐标, pre_dir: 上一步的方向（用于去重）
void idastar_dfs(int dep, int bound, int cx, int cy, int pre_dir) {
    int h = get_heuristic(cx, cy);
    int f = dep + h;

    // 核心启发式剪枝：当前实际代价 + 乐观估计代价超过阈值
    if (f > bound) {
        next_bound = std::min(next_bound, f); // 动态更新下一轮迭代的更紧凑上界
        return;
    }

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

    for (int i = 0; i < 4; ++i) {
        // 逻辑剪枝：禁止原地打转（排除正反向抵消的操作）
        if ((i ^ 1) == pre_dir && dep > 0) continue; 

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

        // 可行性剪枝：边界检查（假设网格大小为 4x4）
        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

        idastar_dfs(dep + 1, bound, nx, ny, i);
        if (success) return; // 瞬间击穿递归树，拒绝多余回溯
    }
}

int solve(int start_x, int start_y) {
    // 初始限界直接设为初始状态的启发值
    int bound = get_heuristic(start_x, start_y);

    while (!success && bound <= 100) { // 100 为安全搜索深度上界限制
        next_bound = 2e9;
        idastar_dfs(0, bound, start_x, start_y, -1);
        if (success) return bound;
        if (next_bound == 2e9) break; // 整个连通块已搜完，无解
        bound = next_bound; // 迭代加深限界值
    }
    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 实战避坑指南

估价函数不满足可采纳性（$h(x) > h^*(x)$）导致答案非最优 在设计复杂图论或组合优化题目的 $h(x)$ 时，有些选手为了追求极速剪枝，错误地放大了估计值。例如：在求最短路时将估价函数设为“曼哈顿距离的平方”。这直接破坏了 $h(x) \le h^*(x)$ 铁律，导致 IDA* 在拉起第一条通路时，由于该通路被过度乐观地判定为“符合限界”，而真正最优但前段代价稍高的路径被直接错杀，最终喜提 WA（答案错误）。
*IDA 迭代限界更新错误导致死循环或 TLE** 在 DFS 触发 f > bound 剪枝回溯时，下一轮的 bound 不能简单地执行 bound++。如果题目步数是非连续的（例如每次变换代价不为 1），机械地 bound++ 会引发无数次无用搜索。必须引入一个全局变量 next_bound = min(next_bound, f)，将下一轮限界精确对准当前所有越界分支中代价最小的那一个。若忘记重置 next_bound 为无穷大，会导致限界无法递增，直接卡死在首层死循环。

经典 NOIP/洛谷真题

1. 洛谷 P1379 八数码难题

题意描述：在 $3 \times 3$ 的棋盘上，摆有八个棋子（1-8）和一个空位（0）。给定初始状态，允许空位与相邻棋子交换，求最少多少步能交换到目标状态。
问题本质：排列空间的单源最短路。
核心解题思路：
状态设计：使用结构体或 string 存储九宫格布局。
估价函数设计：设计 $h(x)$ 值为当前状态中所有非 0 数字当前坐标与最终目标坐标的 曼哈顿距离总和。因为每次交换最多让一个数字靠近目标一步，此 $h(x)$ 严格满足 $h(x) \le h^*(x)$，配合 IDA* 可秒杀此题。

2. 洛谷 P2324 [SCOI2005] 骑士精神

题意描述：在一个 $5 \times 5$ 的棋盘上，有 12 个白骑士、12 个黑骑士和一个空位。要求在 15 步以内，通过骑士的“马走日”移动，达到指定的棋盘最终布局。
问题本质：有步数限制的高维约束启发式搜索。
核心解题思路：
估价函数设计：统计当前棋盘与目标棋盘的 错位点数。由于每次马走日移动最多让一个骑士归位，因此剩余所需步数至少为错位点数。即 $h(x) = \text{错位点数}$。
限界剪枝：若 $dep + h(x) > 15$ 或 $> max\text{_}dep$，直接回溯。15 步的强力限制使得 IDA* 的搜索树被死死锁死在极小的规模内。