IDA*

1 剩余步数下界

迭代加深 依次增加深度上限,用 DFS 寻找最少步数。如果已经走了 gg 步,上限为 DD,普通限深搜索只知道剩余步数不超过 D−gD-g。

若还能计算当前状态到目标至少需要多少步,记作 h(s)h(s),就得到更早的剪枝条件:

g+h(s)>D⟹在当前上限内不可能完成. g+h(s)>D\quad\Longrightarrow\quad\text{在当前上限内不可能完成}.

这种按 f(s)=g+h(s)f(s)=g+h(s) 的上限进行迭代加深的方法称为 IDA*(Iterative Deepening A*)。本文只讨论每步代价为 11 的情形。

估价函数必须满足:

0≤h(s)≤从 s 到目标的真实最少步数. 0\le h(s)\le\text{从 }s\text{ 到目标的真实最少步数}.

它可以低估,但不能高估。低估只会多搜一些状态;高估则可能把最优解剪掉。

2 骑士精神

题目:luogu P2324: [SCOI2005] 骑士精神。

在 5×55\times5 棋盘上放置 1212 枚黑棋、1212 枚白棋和一个空格。每次选择一枚能按国际象棋中骑士走法到达空格的棋子,与空格交换位置。

骑士走法为横向移动 11 格、纵向移动 22 格,或横向移动 22 格、纵向移动 11 格,共 88 个方向。求到达以下目标棋盘的最少步数,超过 1515 步则输出 -1。

11111
01111
00*11
00001
00000

1 表示黑棋,0 表示白棋,* 表示空格。直接枚举所有移动时,每层最多产生 88 个分支;需要利用当前棋盘与目标的差异估计剩余步数。

3 错位棋子

把“当前非空,且内容与目标格不同”的格子数记作 hh。目标应为空格、当前却有棋子的格子,也要计入。

一次移动只让一枚非空棋子换了位置,其余棋子原地不动。因此,hh 至多减少 11。即使这枚棋子一步就能归位,也只能修正它自己的一处错位。

如果当前有 hh 枚棋子错位,至少还要移动 hh 次才能让错位数降到 00,所以:

剩余最少步数≥h. \text{剩余最少步数}\ge h.

棋子可能需要绕行,也可能先把正确棋子移开,因此真实步数可以更大。这不影响下界的正确性。

3.1 不统计空格

若把空格也算作一个错位对象,一次交换可能同时让棋子和空格归位,使错位数减少 22。直接用这个总数估计剩余步数,就可能高估。

下面两个棋盘只差一次合法交换:左图第二列第一行的空格,与第三列第三行的黑棋交换后,就得到目标。

一次移动同时修正棋子和空格,只统计非空棋子时下界为 1

左图若包含空格,错位数为 22;但真实距离只有 11。只统计非空棋子时 h=1h=1,符合下界要求。

这里 h=0h=0 可以作为成功条件:若所有非空格都与目标相同,则目标空格位置不可能被棋子占据,唯一的空格也必然在正确位置。一般的估价函数未必有这个性质,不能一概把 h=0h=0 当作到达目标。

4 搜索上限

从初始棋盘的 hh 开始,依次尝试上限 D=h,h+1,…,15D=h,h+1,\ldots,15。每轮都从初始棋盘重新 DFS。

递归中已走 gg 步时:

  1. 若 g+h>Dg+h>D,返回失败。
  2. 若到达目标,返回成功。
  3. 否则枚举合法交换,递归后恢复棋盘。

注意剪枝条件是 >,不是 >=。当 g+h=Dg+h=D 时,仍可能恰好在上限内完成。

4.1 最优性

设最优解需要 dd 步。沿着这条路径,到任意中间状态已经走了 gg 步,路径上还剩 d−gd-g 步。由于 hh 不高估:

g+h≤g+(d−g)=d. g+h\le g+(d-g)=d.

因此,当上限达到 dd 时,最优路径上的状态都不会被估价剪掉,DFS 必定能够找到解。小于 dd 的上限不可能成功,所以第一轮成功的上限就是最少步数。

4.2 避免立即返回

若本次交换后,下一次立刻与原来的空位交换,就会回到相同棋盘,白走两步。删除这两步仍能接上原路径,因此最短路不会包含这种操作,可以直接跳过。

这只是消除一步撤销。它不等于全局判重,也不会消除所有较长的环。

5 代码实现

代码每次重新统计 2525 个格子的错位数,使用普通数组保存棋盘和移动方向。交换之后无论是否找到解,都恢复棋盘,保证每一轮从相同初始状态开始。

#include <bits/stdc++.h>
using namespace std;

char board[5][5];
const char goal[5][6] = {
    "11111", "01111", "00*11", "00001", "00000"
};
const int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

// 只统计非空棋子;一次交换至多让一枚错位棋子归位。
int estimate() {
    int h = 0;
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            if (board[i][j] != '*' && board[i][j] != goal[i][j]) ++h;
        }
    }
    return h;
}

// (x,y) 是当前空位;(px,py) 是上一次空位,用于避免立即走回头路。
bool dfs(int x, int y, int px, int py, int depth, int limit) {
    int h = estimate();
    if (depth + h > limit) return false;
    if (h == 0) return true;  // 本题中 h=0 恰好意味着整个棋盘已到达目标

    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        if (nx == px && ny == py) continue;
        swap(board[x][y], board[nx][ny]);
        bool found = dfs(nx, ny, x, y, depth + 1, limit);
        swap(board[x][y], board[nx][ny]);  // 无论成功与否,都恢复棋盘
        if (found) return true;
    }
    return false;
}

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

    int T;
    cin >> T;
    while (T--) {
        int x = -1, y = -1;
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                cin >> board[i][j];
                if (board[i][j] == '*') x = i, y = j;
            }
        }
        int answer = -1;
        for (int limit = estimate(); limit <= 15; ++limit) {
            if (dfs(x, y, -1, -1, 0, limit)) {
                answer = limit;
                break;
            }
        }
        cout << answer << '\n';
    }
    return 0;
}

棋盘固定为 2525 格,每个节点的估价与转移开销是常数。搜索时间仍可能随步数上限指数增长,不能把估价剪枝视为多项式复杂度保证。递归深度至多 D≤15D\le15,辅助空间为 O(D)O(D)。

完整题解:pcs2:骑士精神。

6 与迭代加深的关系

普通迭代加深相当于取 h=0h=0,只按已走步数限制搜索。IDA* 在此基础上加入剩余代价下界:仍按 DFS 顺序访问,但会提前舍弃无法在当前上限内完成的分支。

加成序列中的翻倍剪枝也在判断“剩余次数够不够”。两者的共同点是使用乐观估计排除无解分支;IDA* 则明确以 g+hg+h 为阈值组织搜索。估价函数是否可靠,应先证明,再写入剪枝条件。

7 相关题解

暂无相关题解