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

核心逻辑与数学原理

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

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

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

A*和IDA*

从图论与状态空间搜索的角度来看，A和IDA\的底层控制流与空间拓扑模型存在本质不同：

• A* 算法：基于显式图搜索（Explicit Graph Search）拓扑框架。 它将搜索空间视为一个显式有向图。利用全局维护的开放列表（Open List，小根堆）与闭合列表（Closed List，哈希表/动态数组），在每一步通过波前扩散（Wavefront Propagation）的方式，强制按全局总估价代价 $f(x) = g(x) + h(x)$ 的单调递增顺序进行状态扩展。
• IDA* 算法：基于隐式树搜索（Implicit Tree Search）空间遍历。 它将搜索空间强行投影为一棵高度等效的搜索树。利用递归调用栈（Stack）隐式维护当前路径，不保存全局历史状态。通过迭代加深（Iterative Deepening）的算力回溯，配合代价限界（Cost Bound）对树的生长深度进行截断。

A 的本质是基于显式图空间的“启发式堆优化广搜”（用全局队列与闭合表以空间换时间），而 IDA 的本质是基于隐式树空间的“带代价限界剪枝的迭代加深深搜”（用回溯栈与动态阈值以时间换空间）。

A 算法与 IDA 算法的关系

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

IDA* 算法的引擎是迭代加深搜索（IDS）：它本质上就是最朴素的深度优先搜索

二者都是为了找到“最优解”（即代价最低、深度最浅的解）。 A 第一次从优先队列里弹出的终点状态，必然是最优解； IDA 在某一轮迭代中第一次触碰到的终点状态，也必然是最优解。

A 需要极快的响应速度，且内存要相对宽裕。 IDA 优化空间，用时间换空间，解的深度通常可控，如果使用A*内存可能会爆。

估价函数 $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* 的状态转移。

• 网格路径问题：给定一个二维矩阵网格，存在障碍物，允许在此空间内沿上下左右方向移动，求从起点坐标到终点坐标的最短移动步数。
• 数码变换问题：在一个由数字方块和唯一空格组成的棋盘上（如 15 数码），每次只能将空格与其相邻的方块交换，求将当前乱序状态还原为给定目标状态的最少交换次数。

估价函数 $h(x)$ 的构造模型

• 曼哈顿距离：此处需严格区分两类模型的计算差异。
• 在网格路径问题中，仅需计算当前所在坐标 $x$ 与目标坐标 $T$ 的绝对距离：

$$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|)$$

• 海明距离：适用于状态变换步数恒定为 1，且单次操作仅能纠正一个元素状态的模型。即当前状态中与目标状态位置不符的非空元素总数（通常排除空格，因为空格的移动是为了服务数字归位）。

可采纳性（Admissibility）的逻辑证明 估价函数必须满足 $0 \le h(x) \le h^*(x)$。在数码问题中，单次合法的交换操作只移动一个数字滑块。因此，单次操作对海明距离的修复效率上限为 1。 设当前错位元素个数为 $k$，即 $h(x) = k$。由于每次操作最多只能让一个错位滑块回到正确位置，想把这 $k$ 个错位元素全部复位，真实的最少操作步数 $h^*(x)$ 必然大于或等于 $k$。由此推导 $h(x) \le h^*(x)$ 成立，满足对剩余代价的低估，保证了算法的正确性。

在数码问题中， $$h_{Hamming}(x) \le h_{Manhattan}(x) \le h^*(x)$$ 所以使用曼哈顿距离作为估价函数

IDA* 状态转移与剪枝推导

定义函数 DFS 进行递归，状态隐式记录在全局数组或位运算中。

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

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

剪枝的安全性质明 方程中的 $dep$ 等价于当前路径已付出的实际代价 $g(x)$。 因为估价函数满足可采纳性 $h(current) \le h^*(current)$，所以当前分支能达到的真实总代价下界为 $dep + h(current)$。 若该下界已经超越当前迭代的深度限界（$dep + h(current) > bound$），由于真实的剩余代价只会更大或相等，必然有 $dep + h^*(current) > bound$。这在数学上证明了在当前限界内，沿着该分支绝对不可能搜到最优解，因此触发剪枝是绝对安全的。

• 增量式 $h(x)$ 维护：在每次状态转移后，若通过重新遍历整个盘面去计算新状态的 $h(x)$，单步时间复杂度将达到 $O(Size)$，导致深层递归耗时恶化。高效的实现是仅计算转移带来的局部差值变动：

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

增量维护的数学原理 状态转移通常具有高度的局部性。以数码问题为例，每一次合法移动本质上只是一个具体的数字滑块与空格交换了位置，盘面中其余所有滑块的相对坐标均保持不变。 设在本次转移中发生移动的滑块为 $v$，其移动前的曼哈顿距离为 $dist_{old}(v)$，移动到新位置后的曼哈顿距离为 $dist_{new}(v)$。 此时，全局估价的差值变动量可被精确量化为局部变动：$\Delta h = dist_{new}(v) - dist_{old}(v)$。算法仅需 $O(1)$ 的时间计算此变动并叠加到当前估价上，即可完成 $h(x)$ 的高效转移。

IDA* 核心代码模板

这段代码解决的是在 $4 \times 4$ 的网格矩阵中，求解从任意指定起点 $(start\_x, start\_y)$ 到固定终点 $(3, 3)$ 的最短移动步数（最短路径）问题。虽然这段代码的场景中没有加入障碍物（空旷网格的最短路径本来等于曼哈顿距离），但它提供了一个标准且 IDA* 算法核心模板，可以直接平移扩展到带有复杂障碍物的迷宫寻路、15数码问题或其它状态空间变换问题中。

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// 注意 dx, dy 的顺序：0和1对应上下，2和3对应左右，保证异或1 (i ^ 1) 能正确表示反方向

int target_x = 3, target_y = 3;
int next_bound; // 记录下一轮迭代的最小越界代价
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);

    // 启发式剪枝：f(x) 大于当前深度限制，更新下一轮的放宽界限并回溯
    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) {
        // 逻辑剪枝：利用位运算 (i ^ 1) 排除走回头路
        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);

        // 击穿递归树：一旦找到解，立刻向上返回，拒绝多余的回溯搜索
        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; // 整个连通块已搜完，彻底无解
        bound = next_bound; // 迭代加深：精确将上界提升至被剪枝节点中的最小代价
    }
    return -1;
}

next_bound 优化 if (f > bound) { next_bound = min(next_bound, f); return; } 在很多非网格图（比如复杂的图论最短路、或者单步代价不为 1 的模型）中，状态转移的代价可能是离散的、不连续的。 如果下一轮我们机械地执行 bound++（变成 6），但可能盘面上根本不存在总代价恰好为 6 的合法状态，这一轮搜索就会瞬间进去又瞬间全部被剪枝出来，白白浪费一次完整的 DFS 盘面遍历。 通过 min(next_bound, f)，算法能够精准踩点，直接把上界提升到“下一轮真正有可能探寻到的最近台阶”。

NOIP 实战避坑指南

1. 估价函数不满足可采纳性导致答案非最优：在设计复杂图论或组合优化题目的 $h(x)$ 时，为了追求极速剪枝，错误地放大了估计值。例如将估价函数设为曼哈顿距离的平方。这破坏了 $h(x) \le h^*(x)$ 铁律，导致真正最优但前段代价稍高的路径被错杀，最终得到 WA。
2. IDA* 迭代限界更新错误导致死循环或 TLE：在 DFS 触发回溯时，下一轮的 bound 不能简单地执行自增。如果题目步数代价不是恒定的 1，机械地自增会引发无数次无用搜索。必须引入全局变量精确对准当前所有越界分支中代价最小的那一个。若忘记重置限界变量为无穷大，会导致限界无法递增，卡死在首层。

经典题目解析与核心代码

UVA10181：15数码问题

在一个 4x4 的棋盘上，有 1-15 的数字滑块和一个空位。求将乱序状态移动到有序状态的最少步数。限制最大步数为45步. 核心思路：估价函数设计为所有非空滑块当前位置与其目标位置的曼哈顿距离之和。若某一步使得距离变大则相当于 $f(x)$ 增加。

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

// 计算曼哈顿距离和，忽略空格 (数字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;
            // 通过 (val-1) 将 1-15 映射到坐标系求目标位置
            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; // 估价为0说明所有方块均在目标位置

    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]); // 回溯恢复现场
    }
    return false;
}

$N$（逆序对总数）：序列中满足 $i < j$ 且 $a_i > a_j$ 的数字对数（不计 0）。$R$（空格所在的行数）：规定顶行 $R=1$，底行 $R=4$。

左右移：总变化量 = $0 + 0 = 0$（偶数）。上下移：总变化量 = $\Delta N + \Delta R = \text{奇数} + \text{奇数} = \mathbf{偶数}$。

15数码的任意合法移动都会保持“逆序对总数与空格行数之和”的奇偶性守恒，从而将 16! 的全排列状态空间严格割裂为两个大小相等、互不相通的连通分支。

先用 $O(1)$ 的时间进行奇偶性预判，如果是无解状态直接输出 -1

P2324 [SCOI2005] 骑士精神

题意提炼：在一个 5x5 的棋盘上，有黑白两色骑士和一个空位。马走日字。求在 15 步内能否将当前盘面转移到给定的目标盘面。 核心思路：$h(x)$ 设计为不在目标位置的骑士数量（海明距离）。因为一次移动最多纠正一个骑士的位置，所以 $h(x)$ 完美满足可采纳性。

int a[6][6];
// 目标盘面状态 (按题目给定的最终形态)
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个方向
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();
    // 骑士移动时，空格也参与交换，因此估价容差放宽至 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;
}

状态总空间：$25! / (12! \cdot 12! \cdot 1!) \approx 4.4 \times 10^{11}$。

如果这 25 个棋子全部长得不一样，$25!$ 再把重复的因数扣除掉，$/ (12! \cdot 12! \cdot 1!) $