A* & IDA*

iChen · 2026-01-15 17:32:25 · 算法·理论

本文使用尽可能通俗易懂的语言讲解 A 算法和 IDA 算法。

感谢 @xuezhiyu 对例题板块做出的贡献。

前置芝士：BFS 广度优先搜索，DFS 深度优先搜索，迭代加深算法。

A*

引入

A* 算法是一种在有向带权图上找给定起点和终点间最短路径的算法。是对广度优先搜索的改进，属于启发式搜索。

回顾 BFS 求两点间最短距离，比如我们需要在空旷的平面上求起点 \textrm S 到终点 \textrm T 的最短距离：

如果我们使用 BFS 算法，逐步各个方向往外拓展，那么会是这样：

（天蓝色区域代表已搜索区域）

直到搜索到 \textrm T。

我们发现，向右下方搜索的这些区域完全是徒劳的。因为我们走到这里发现偏离了正确的方向，再往下搜只会一条死路走到底，不撞南墙不回头。

所以我们需要判断当前状态是否大概在向正确的方向前进以剪枝掉大量无用状态，大概可以理解为一个简陋的导航系统。

那我们怎么给程序也装上这样的导航系统呢？

实现

我们在 BFS 中，使用了堆存储当前需要搜索的状态，并按照从起点搜到当前结点代价 \textrm{cost(S, now)} 排序，优先搜索代价小的状态。

如果我们在向正确的方向前进，那么显然我们当前状态距离终点的距离会越来越小。所以可以考虑在排序的关键字中加入对这个距离的考虑，在原来的当前以花费代价上再综合考虑优先尝试更新离终点更近的状态，也就是所说的向着正确方向前进的状态，以达到一个导航的效果。

我们将排序的关键字改变，变成 \textrm{cost(S, now) + cost(now,T)}，也就是从起点到当前结点的代价和当前结点到终点的代价。\textrm{cost(S, now)} 是我们可以在搜索过程中记录，直接得到精确值的。但是我们不知道 \textrm{cost(now, T)} 啊，所以我们需要估计这个值的大小。所以需要设计一个估价函数 \textrm{heuristic(now, T)}，估计当前结点到终点的代价即可。

那么在上面的例子中，当此状态向错误方向偏离时，\textrm{heuristic(now, T)} 会变大，导致这种错误状态的 \textrm{cost(S, now) + heuristic(now,T)} 更大，被排序到队伍后端，不会被优先更新和处理。

而反之，正确的状态的会向正确的方向前进，其距离终点的代价 \textrm{heuristic(now, T)} 会越来越小，导致它的 \textrm{cost(S, now) + heuristic(now,T)} 偏小，被排在队伍前端，会被优先考虑更新。

由此，通过估计当前状态到终点的代价，我们完成了一个类似于导航的功能，或者可以说是优化。

听起来是不是很玄学？这里有一个显然的问题：既然是我们估计的值，肯定不精确，那如何保证正确性呢？

我们只需要保证估价函数一定不大于真实的代价即可，即 \textrm{heuristic(now, T)}\leqslant \textrm{cost(now, T)}。

如何证明？若在保证估价函数小于真实代价的情况下，一个错误的路径上的一个错解状态 \textrm{WA} 一直排在了队头，一直将其取出并搜索更新，直到它的当前结点到达了终点，得到的错误答案为 \textrm{WA\_ans}。设此时正解路径上的状态为 \textrm{AC}，它的当前结点为 \textrm{now}，如果将此正解状态一路更新到终点将会得到的正确答案为 \textrm{AC\_ans}。

由于错解是错解，所以正解一定优于错解，也就是：

\textrm{AC\_ans < WA\_ans}

由于我们的估价函数满足：

\textrm{heuristic(now, T)}\leqslant \textrm{cost(now, T)}

而：

\textrm{cost(S, now) + cost(now, T) = AC\_ans}

所以：

\textrm{cost(S, now) + heuristic(now, T)} \leqslant \textrm{AC\_ans}

所以：

\textrm{cost(S, now) + heuristic(now, T)}<\textrm{WA\_ans}

那么这个错解状态到达终点后一定会被还没到终点的正解状态压在队伍后面出不来，我们会优先去更新正解状态而不是让错解状态出队得到错误答案。因此正解一定会成为第一个出队的到达了终点的状态。

那如何设计估价函数呢？这个要视具体题目而定。一定要保证估价函数的值小于真实代价，并且估价函数越接近真实代价，剪枝效果更好，代码更快。后面会着重讲这一部分。

以上即为对于 A* 算法的原理解析。接下来结合例题感受其在题目中的运用。

例题

:::info[P1379 八数码难题]{open}

在 3\times 3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

样例：

输入：

283104765

输出：

样例解释

图中标有 0 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。 :::

:::success[分析]{open} 显然直接搜索会超时。考虑使用 IDA* 算法优化。估价函数如何定义？

不难发现每当进行一次 0 与其相邻数字的交换后，会使两个格子上的数值发生变化，那么按照最乐观的情况下，每次操作会使至多一个非零格子得到正确数值，而 0 会在最后一次操作后回到自己的正确位置上。那么最佳情况下的操作数为当前状态与目标状态格子数字不匹配的格子数减一，以此作为估价函数进行 IDA* 搜索即可，再加上记忆化优化。

#include <iostream>
#include <queue>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

constexpr int tag[3][3] = {
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5}
};
constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};

struct Situation {
    int g[3][3];
    int x0, y0;
    int cost, h;
    inline const bool operator > (const Situation &A) const {
        return cost + h > A.cost + A.h;
    }
} stt;
priority_queue <Situation, vector <Situation>, greater <Situation>> q;
inline int heuristic (Situation x) {
    int res = 0;
    for (int i = 0; i < 3; ++ i) {
        for (int j = 0; j < 3; ++ j) {
            res += (tag[i][j] != x.g[i][j]);
        }
    }
    return res ? res - 1 : res;
}
inline ll getid (Situation x) {
    ll res = 0;
    for (int i = 0; i < 3; ++ i) {
        for (int j = 0; j < 3; ++ j) {
            res += pow(10, i * 3 + j) * x.g[i][j];
        }
    }
    return res;
}

map <ll, bool> mem;

int main () {
    char inp;
    for (int i = 0; i < 3; ++ i) {
        for (int j = 0; j < 3; ++ j) {
            cin >> inp;
            stt.g[i][j] = inp - 48;
            if (inp == '0') stt.x0 = i, stt.y0 = j;
        }
    }
    stt.h = heuristic(stt);
    q.push(stt);
    Situation tmp;
    while (!q.empty()) {
        Situation o = q.top();
        q.pop();
        if (!o.h) {
            cout << o.cost;
            return 0;
        }
        if (mem[getid(o)]) continue;
        mem[getid(o)] = true;
        for (int k = 0; k < 4; ++ k) {
            int nx = o.x0 + dx[k], ny = o.y0 + dy[k];
            if (nx < 0 or nx >= 3 or ny < 0 or ny >= 3) continue;
            tmp = o;
            swap(tmp.g[o.x0][o.y0], tmp.g[nx][ny]);
            tmp.x0 = nx, tmp.y0 = ny;
            tmp.h = heuristic(tmp);
            tmp.cost ++;
            q.push(tmp);
        }
    }
    return 0;
}

:::

:::info[P2901 [USACO08MAR] Cow Jogging G]{open} 给出有 N 个结点 M 条边的有向正权图，每条边给出 X_i, Y_i, D_i，表示结点 X_i 到结点 Y_i 有一条长度为 D_i 的路径。

问从结点 n 到结点 1 的前 K 段路径长度，若路径数量不足则用 -1 补齐。

保证 1 \leqslant N \leqslant 1,000，1 \leqslant M \leqslant 1\times10^4，1 \leqslant K \leqslant 100，1 \leqslant Y_i < X_i\leqslant N，1 \leqslant D_i \leqslant 1\times 10^6。 :::

:::success[分析]{open} 图上找 k 短路模板题。

考虑搜索，直接 BFS，没找到当前最短路就输出，将 k 减一，直到 k = 1 结束。会爆空间，考虑 A* 用估价函数剪枝优化。

思考估价函数，可以将给出的边建反边，从终点开始跑一遍 dijkstra 得到每个结点到终点的最短路径，那么从此结点向终点得到的所有路径一定不优于此路径，可以作为估价函数。

然后就是实现了，难度不大。

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
#define int long long

using namespace std;

constexpr int N = 1e3 + 5, M = 1e4 + 5, inf = 1e18;
int n, m, k;

int head[N], nxt[M], ver[M], spd[M], tot;
inline void add (int a, int b, int c) {
    ver[++ tot] = b, spd[tot] = c;
    nxt[tot] = head[a], head[a] = tot;
}
vector <pair <int, int>> back[N];

struct Node {
    int pos, cost;
    inline const bool operator > (const Node &oth) const {
        return cost > oth.cost;
    }
};
bool vis[N];
int dis[N];
inline void dijkstra () {
    priority_queue <Node, vector <Node>, greater <Node>> q;
    q.push(Node{1, 0});
    for (int i = 1; i <= n; ++ i) dis[i] = inf;
    dis[1] = 0;
    while (!q.empty()) {
        Node o = q.top();
        q.pop();
        if (vis[o.pos]) continue;
        vis[o.pos] = true;
        for (int i = 0; i < back[o.pos].size(); ++ i) {
            pair <int, int> to = back[o.pos][i];
            if (vis[to.first]) continue;
            if (dis[to.first] > o.cost + to.second) {
                dis[to.first] = o.cost + to.second;
                q.push(Node{to.first, dis[to.first]});
            }
        }
    }
}

struct State {
    int pos, cost;
    inline const bool operator > (const State &oth) const {
        return cost + dis[pos] > oth.cost + dis[oth.pos];
    }
};
inline void Astar () {
    priority_queue <State, vector <State>, greater <State>> q;
    q.push(State{n, 0});
    while (!q.empty()) {
        State o = q.top();
        q.pop();
        if (o.pos == 1) {
            cout << o.cost << '\n';
            if (!(-- k)) exit(0);
            continue;
        }
        for (int i = head[o.pos]; i; i = nxt[i]) {
            q.push(State{ver[i], o.cost + spd[i]});
        }
    }
    while (k --) cout << "-1\n";
}

signed main () {
    cin >> n >> m >> k;
    while (m --) {
        int x, y, d;
        cin >> x >> y >> d;
        add(x, y, d);
        back[y].push_back(make_pair(x, d));
    }
    dijkstra();
    Astar();
    return 0;
}

:::

IDA*

引入

如果要一句话说明白：IDA = A + 迭代加深。

回顾迭代加深，就是多次 DFS，每次限制向下搜索的层数。如果当前限制层数下没有找到答案，那就再放大限制，再搜索......直到找到答案，实现了和 BFS 一样的效果。

我们发现，在每次扩大限制之后，之前搜索过的内容还需要再搜索一次，干了很多重复的工作。那为什么我们不用 BFS 呢？

原因就是：空间。再 BFS 中，我们需要使用一个队列维护当前待处理的所有状态，当我们的剪枝力度不够或题目数据范围太大导致状态过多，就会 MLE。而 DFS 呢？我们只需要维护一份状态，也就是当前所处的状态，在搜索完成此分支后回溯即可。所以使用迭代加深代替 BFS 是一种时间换空间的操作。

同样的，IDA* 的基本思想也是 BFS。当状态过多，我们就可以使用迭代加深来代替 BFS。那搭配使用 DFS 与估价函数？

实现

设当前的搜索深度限制为 \textrm{lim}，当前状态已经付出的代价为 \textrm{cost}，当前状态搜索到终点的估价函数为 \textrm h，当前状态搜索到终点实际上需要付出代价 \textrm{real}。我们依然保证估价函数的值不大于真实代价，那么：

\textrm h\leqslant \textrm{real}

在此时，如果我们发现按照估计出来的代价无法让我们在限制内到达终点，即：

\textrm{cost + h > lim}

那么有：

\textrm{cost + real > lim}

那么当前状态一定无法在限制内到达终点，直接舍弃，不往下继续搜。

感性理解就是，我乐观地估计还需要多少代价能到达终点，而在最乐观的状态下，我还是无法在限制内到达终点，那么实际上就更无法在限制内到达终点了。

以上即为 IDA 算法的原理解析，接下来还是通过一些例题来熟悉 IDA 算法的运用。

例题

:::info[P2324 [SCOI2005] 骑士精神]{open}

在一个 5\times 5 的棋盘上有 12 个白色的骑士和 12 个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和他横坐标相差为 1，纵坐标相差为 2 或者横坐标相差为 2，纵坐标相差为 1 的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘

为了体现出骑士精神，他们必须以最小的步数完成任务。

输入第一行有一个正整数 T（T \le 10），表示一共有 T 组数据。

接下来有 T 个 5 \times 5 的矩阵，0 表示白色骑士，1 表示黑色骑士，* 表示空位。两组数据之间没有空行。

对于每组数据都输出一行。如果能在 15 步以内（包括 15 步）到达目标状态，则输出步数，否则输出 -1。

样例：

输入：

输出：

7
-1

:::

:::success[分析]{open} 显然一眼有暴搜做法，DFS 不好找最优解，BFS 依旧空间有毛病，考虑 IDA*。考虑如何设计估价函数。

发现我们每做一次操作后，会使最多一个棋子到达正确位置。那么和前面的八数码难题思路一样，估价函数为当前棋盘上与目标棋盘棋子颜色不同的格子数量，接下来就是实现了。

#include <iostream>
#include <algorithm>

using namespace std;

char tar[5][5] = {
    {'1', '1', '1', '1', '1'},
    {'0', '1', '1', '1', '1'},
    {'0', '0', '*', '1', '1'},
    {'0', '0', '0', '0', '1'},
    {'0', '0', '0', '0', '0'}
};
char stt[5][5], now[5][5];
int stx, sty, _x, _y;

constexpr int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
constexpr int dy[8] = {-2, -1, 1, 2, -2, -1, 1, 2};

int lim;

inline int heuristic () {
    int res = -1;
    for (int i = 0; i < 5; ++ i) {
        for (int j = 0; j < 5; ++ j) {
            res += (now[i][j] != tar[i][j]);
        }
    }
    return max(0, res);
}

bool IDAstar (int step) {
    if (step + heuristic() > lim) return false;
    if (!heuristic()) return true;
    for (int i = 0; i < 8; ++ i) {
        int nx = _x + dx[i], ny = _y + dy[i];
        if (nx < 0 or nx >= 5 or ny < 0 or ny >= 5) continue;
        swap(now[_x][_y], now[nx][ny]);
        swap(_x, nx), swap(_y, ny);
        if (IDAstar(step + 1)) return true;
        swap(_x, nx), swap(_y, ny);
        swap(now[_x][_y], now[nx][ny]);
    }
    return false;
}

inline void solve () {
    for (int i = 0; i < 5; ++ i) {
        for (int j = 0; j < 5; ++ j) {
            cin >> stt[i][j];
            if (stt[i][j] == '*') stx = i, sty = j;
        }
    }
    lim = -1;
    while (++ lim <= 15) {
        for (int i = 0; i < 5; ++ i) {
            for (int j = 0; j < 5; ++ j) now[i][j] = stt[i][j];
        }
        _x = stx, _y = sty;
        if (IDAstar(0)) {
            cout << lim << '\n';
            return;
        }
    }
    cout << "-1\n";
}

int main () {
    int T; cin >> T;
    while (T --) solve();
    return 0;
}

:::

:::info[P2540 [NOIP 2015 提高组] 斗地主加强版]{open}

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{小王}<\text{大王}，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

在此题中认为两个王不能组成对子牌。

输入第一行包含用空格隔开的 2 个正整数 T,n，表示手牌的组数以及每组手牌的张数。

接下来 T 组数据，每组数据 n 行，每行一个非负整数对 a_i,b_i，表示一张牌，其中 a_i 表示牌的数码，b_i 表示牌的花色，中间用空格隔开。特别的，我们用 1 来表示数码 A，11 表示数码 J，12 表示数码 Q，13 表示数码 K；黑桃、红心、梅花、方片分别用 1-4 来表示；小王的表示方法为 0 1，大王的表示方法为 0 2。

输出共 T 行，每行一个整数，表示打光第 i 手牌的最少次数。

样例：

输入：

输出：

样例解释

共有 1 组手牌，包含 8 张牌：方片 7，方片 8，黑桃 9，方片 10，黑桃 J，黑桃 5，方片 A 以及黑桃 A。可以通过打单顺子（方片 7，方片 8，黑桃 9，方片 10，黑桃 J），单张牌（黑桃 5）以及对子牌（黑桃 A 以及方片 A）在 3 次内打光。 :::

:::success[分析]{open} （by @xuezhiyu）

先抛开如何模拟这依托的问题，考虑如何优化暴力搜索。首先可以钦定出牌顺序，并且枚举时优先出一次出牌更多的方案。然后观察到答案很小，而且 A 容易炸空间，因此可以使用 IDA。考虑如何写估价函数，如果上述出牌顺序满足出牌张数单调不降，那么记录上次出牌张数 l，假设现在有 n 张牌，那么最优还需要出 \left\lceil \frac{n}{l}\right\rceil 次，可以用这个作估价函数。

下面讲如何模拟出牌过程并优化常数。先把所有出牌方案整理出来，接下来就要快速判断能否出牌。可以用一个二进制串来表示可重集合（因为我们知道每张牌最多有多少张），于是直接二进制判属于就好了。

思路很简单，代码很【数据删除】。

#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
#define endl '\n'
#define GETSTATE(_L_, _R_) (((INT64_C(1) << ((_R_) + 1)) - 1) ^ ((INT64_C(1) << (_L_)) - 1))

using namespace std;

constexpr int N = 15, M = 13, S = 12, K = 1 << S;

enum { C3, C4, C5, C6, C7, C8, C9, C0, CJ, CQ, CK, CA, C2, CB, Cb };
constexpr int trans[] = {-1, CA, C2, C3, C4, C5, C6, C7, C8, C9, C0, CJ, CQ, CK };
constexpr int cardspos[] = {0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 53};

struct Card {
    int cnt[N], tot;
    int64_t state;
    Card() : cnt{0}, tot(0), state(0) {}
    bool operator<=(const Card& other) const {
        if (tot != other.tot) return tot < other.tot;
        for (int i = 0; i < N; i++)
            if (cnt[i] != other.cnt[i])
                return cnt[i] < other.cnt[i];
        return true;
    }
    void operator-=(const Card& other) {
        tot -= other.tot;
        for (int i = 0; i < N; i++) {
            cnt[i] -= other.cnt[i];
            state ^= GETSTATE(cardspos[i] + cnt[i], cardspos[i] + cnt[i] + other.cnt[i] - 1);
        }
    }
    void operator+=(const Card& other) {
        tot += other.tot;
        for (int i = 0; i < N; i++) {
            state |= GETSTATE(cardspos[i] + cnt[i], cardspos[i] + cnt[i] + other.cnt[i] - 1);
            cnt[i] += other.cnt[i];
        }
    }
    bool check(const Card& other) const {
        return (state | other.state) == state;
    }

    Card& sa(int _pos, int _cnt = 1) {
        state |= GETSTATE(cardspos[_pos] + cnt[_pos], cardspos[_pos] + cnt[_pos] + _cnt - 1);
        cnt[_pos] += _cnt, tot += _cnt;
        return *this;
    }
};

ostream& operator<<(ostream& output, const Card& card) {
    output << "{[";
    vector<string> v;
    for (int i = 0; i < card.cnt[C3]; i++) v.push_back("3");
    for (int i = 0; i < card.cnt[C4]; i++) v.push_back("4");
    for (int i = 0; i < card.cnt[C5]; i++) v.push_back("5");
    for (int i = 0; i < card.cnt[C6]; i++) v.push_back("6");
    for (int i = 0; i < card.cnt[C7]; i++) v.push_back("7");
    for (int i = 0; i < card.cnt[C8]; i++) v.push_back("8");
    for (int i = 0; i < card.cnt[C9]; i++) v.push_back("9");
    for (int i = 0; i < card.cnt[C0]; i++) v.push_back("10");
    for (int i = 0; i < card.cnt[CJ]; i++) v.push_back("J");
    for (int i = 0; i < card.cnt[CQ]; i++) v.push_back("Q");
    for (int i = 0; i < card.cnt[CK]; i++) v.push_back("K");
    for (int i = 0; i < card.cnt[CA]; i++) v.push_back("A");
    for (int i = 0; i < card.cnt[C2]; i++) v.push_back("2");
    for (int i = 0; i < card.cnt[CB]; i++) v.push_back("King");
    for (int i = 0; i < card.cnt[Cb]; i++) v.push_back("king");
    for (vector<string>::iterator it = v.begin(); it != v.end(); it++) {
        output << *it;
        if (it + 1 != v.end()) output << ' ';
    }
    output << "], tot=" << card.tot << ", state=";
    for (int i = 0; i < 54; i++) output << (card.state >> i & 1);
    output << '}';
    return output;
}

struct {
    Card all;
    Card rock;          // 火箭
    Card boom[M];       // 炸弹
    Card sing[N];       // 单张
    Card doub[M];       // 对子
    Card trib[M];       // 三张
    Card tone[M][N];    // 三带一
    Card ttwo[M][M];    // 三带二
    Card sflu[K];       // 单顺
    Card dflu[K];       // 双顺
    Card tflu[K];       // 三顺
    Card ftwo[M][N][N]; // 四带二
    Card ftdb[M][M][M]; // 四带两对

    void init() {
        for (int i = 0; i < M; i++) all.sa(i, 4);
        all.sa(CB).sa(Cb);
        rock.sa(CB).sa(Cb);
        for (int i = 0; i < M; i++) boom[i].sa(i, 4);
        for (int i = 0; i < N; i++) sing[i].sa(i, 1);
        for (int i = 0; i < M; i++) doub[i].sa(i, 2);
        for (int i = 0; i < M; i++) trib[i].sa(i, 3);
        for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) if (i != j) tone[i][j].sa(i, 3).sa(j);
        for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) if (i != j) ttwo[i][j].sa(i, 3).sa(j, 2);
        for (int i = 0; i < S; i++) for (int j = i + 4; j < S; j++)
            for (int k = i; k <= j; k++) sflu[GETSTATE(i, j)].sa(k);
        for (int i = 0; i < S; i++) for (int j = i + 2; j < S; j++)
            for (int k = i; k <= j; k++) dflu[GETSTATE(i, j)].sa(k, 2);
        for (int i = 0; i < S; i++) for (int j = i + 1; j < S; j++)
            for (int k = i; k <= j; k++) tflu[GETSTATE(i, j)].sa(k, 3);
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++) if (i != j)
                for (int k = j; k < N; k++) if (i != k)
                    if (!(j == k && j == CB))
                        ftwo[i][j][k].sa(i, 4).sa(j, 1).sa(k, 1);
        for (int i = 0; i < M; i++)
            for (int j = 0; j < M; j++) if (i != j)
                for (int k = j; k < M; k++) if (i != k)
                    ftdb[i][j][k].sa(i, 4).sa(j, 2).sa(k, 2);
    }
} cards;

int lim;
Card card;

bool dfstar(int dep, const Card& lst) {
    std::function<bool(const Card&)> trycard = [&](const Card& _try) -> bool {
        if (!card.check(_try) || !(_try <= lst)) return false;
        card -= _try;
        if (dfstar(dep + 1, _try))
            return card += _try, true;
        card += _try;
        return false;
    };

    if (dep + (card.tot + lst.tot - 1) / lst.tot > lim) return false;
    if (!card.tot) return true;
    // 三顺
    for (int len = 2; len <= S; len++) if (lst.tot >= len * 3)
        for (int l = 0, r = len - 1; r < S; l++, r++)
            if (trycard(cards.tflu[GETSTATE(l, r)])) return true;
    // 双顺
    for (int len = 3; len <= S; len++) if (lst.tot >= len * 2)
        for (int l = 0, r = len - 1; r < S; l++, r++)
            if (trycard(cards.dflu[GETSTATE(l, r)])) return true;
    // 单顺
    for (int len = 5; len <= S; len++) if (lst.tot >= len)
        for (int l = 0, r = len - 1; r < S; l++, r++)
            if (trycard(cards.sflu[GETSTATE(l, r)])) return true;
    // 四带两对
    if (lst.tot >= 8)
        for (int i = 0; i < M; i++) if (card.cnt[i] >= 4)
            for (int j = 0; j < M; j++) if (i != j && card.cnt[j] >= 2)
                for (int k = j; k < M; k++) if (i != k && card.cnt[k] >= 2)
                    if (trycard(cards.ftdb[i][j][k])) return true;
    // 四带二
    if (lst.tot >= 6)
        for (int i = 0; i < M; i++) if (card.cnt[i] >= 4)
            for (int j = 0; j < N; j++) if (i != j)
                for (int k = j; k < N; k++) if (i != k)
                    if (!(j == k && j == CB))
                        if (trycard(cards.ftwo[i][j][k])) return true;
    // 三带二
    if (lst.tot >= 5)
        for (int i = 0; i < M; i++) if (card.cnt[i] >= 3)
            for (int j = 0; j < M; j++) if (i != j)
                if (trycard(cards.ttwo[i][j])) return true;
    // 三带一
    if (lst.tot >= 4)
        for (int i = 0; i < M; i++) if (card.cnt[i] >= 3)
            for (int j = 0; j < N; j++) if (i != j)
                if (trycard(cards.tone[i][j])) return true;
    // 炸弹
    if (lst.tot >= 4)
        for (int i = 0; i < M; i++)
            if (trycard(cards.boom[i])) return true;
    // 三张牌
    if (lst.tot >= 3)
        for (int i = 0; i < M; i++)
            if (trycard(cards.trib[i])) return true;
    // 对子
    if (lst.tot >= 2)
        for (int i = 0; i < M; i++)
            if (trycard(cards.doub[i])) return true;
    // 火箭
    if (lst.tot >= 2)
        if (trycard(cards.rock)) return true;
    // 单张牌
    for (int i = 0; i < N; i++)
        if (trycard(cards.sing[i])) return true;
    return false;
}

int solve() {
    for (lim = 1; !(dfstar(0, cards.all)); lim++);
    return lim;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cards.init();
    int T, n;
    cin >> T >> n;
    while (T --> 0) {
        card.tot = card.state = 0;
        for (int i = 0; i < N; i++) card.cnt[i] = 0;
        for (int i = 0; i < n; i++) {
            int u, v; cin >> u >> v;
            if (u) card.sa(trans[u]);
            else card.sa(v == 1 ? Cb : CB);
        }
        cout << solve() << endl;
    }
    return 0;
}

:::

估价函数

A 和 IDA 的思想是很好理解的，做题的时候难点在于如何设计一个优秀的估价函数以剪枝掉更多状态，使导航系统更精确。

在设计估价函数时，一定要确保可采纳性，既其值永远要不劣于真实情况。宁可低估不可高估！

luogu 的 A 和 IDA 题真的不是很多。根据笔者目前的刷题经验并与 deepseek 的激烈对线后，总结出以下常用的设计估价函数的 Tricks，欢迎补充！

放宽约束

在问题中会有一些限制，若是放宽或去掉这些限制后，得到的答案一定会更优，并很容易快速计算出来。那么可以将去掉这些限制后计算到终点的代价。比如：

障碍物限制：在带有障碍物的地图中找最短路，显然障碍物就是一个限制。那么考虑在可以“穿墙”的情况下，显然最优解为曼哈顿距离或欧拉距离。可以以此作为估价函数。

资源限制：部分题目中，我们需要安排花费一些资源完成一些任务。那么可以在不考虑时间、燃料等资源不足的限制下，当前还需要多久能达成目标，作为估价函数。

......

分解子问题

将问题分为多个互相独立子问题，比如：

在前面的例题八数码难题和骑士精神中，我们把复原整个棋盘的大问题分解为分别将每个小的棋子或数值放回原位，就是在将问题分解为子问题。再视具体情况累加子问题代价或者取子问题代价最大值。

......

预处理

比如在前面的 k 短路问题中，我们将终点建反边跑，本质上是一个放宽约束的行为，而考虑到这里不好在每次一个新状态中都快速算出来，所以先跑一遍 dijkstra 把这个值预处理出来作为估价函数。

......

A 和 IDA 的变形

最佳优先搜索：只关注估价函数的值，按照估价函数值排序搜搜，不能保证正确性，但可以在很快的时间内求得较优解。
**加权 A***：在排序时，适当放大估价函数侧重的比例，排序关键字变为 \textrm{cost(S, now) + } \alpha \times \textrm{heuristic(now,T)}，\alpha > 1。这样做绝大部分情况下对时间有优化，但并不能完全保证正确性。
双向启发式搜索：从起点和终点同时发起 A* 搜索，相遇时停止，可以大幅减少搜索空间。

启发式搜索的核心思想是：利用问题领域的特定知识（即“启发信息”）来引导搜索过程，从而减少搜索范围，更快地找到目标。而 A 和 IDA 是其中最常用最具有代表性的两个算法。

还有以下启发式搜索，如果学有余力推荐自行拓展学习：

递归最佳优先搜索：一种优化内存的 RBFS 算法，在有限内存下模拟 A* 的行为。
束搜索：只保留每个阶段最优的 K 个节点进行扩展，是一种受限的启发式搜索。
实时启发式搜索算法：如 LRTA*，用于在计算时间有限、需要立即行动的场景（如游戏AI）。
更广义的启发式搜索：甚至可以将模拟退火、遗传算法、蚁群算法等也视为启发式搜索的范畴，因为它们都利用某种启发信息来指导解空间的探索。

完成 练习题 以巩固新知。

完结撒花！