1 剩余步数下界
迭代加深 依次增加深度上限,用 DFS 寻找最少步数。如果已经走了
若还能计算当前状态到目标至少需要多少步,记作
这种按
估价函数必须满足:
它可以低估,但不能高估。低估只会多搜一些状态;高估则可能把最优解剪掉。
2 骑士精神
题目:luogu P2324: [SCOI2005] 骑士精神。
在
骑士走法为横向移动 -1。
11111
01111
00*11
00001
00000
1 表示黑棋,0 表示白棋,* 表示空格。直接枚举所有移动时,每层最多产生
3 错位棋子
把“当前非空,且内容与目标格不同”的格子数记作
一次移动只让一枚非空棋子换了位置,其余棋子原地不动。因此,
如果当前有
棋子可能需要绕行,也可能先把正确棋子移开,因此真实步数可以更大。这不影响下界的正确性。
3.1 不统计空格
若把空格也算作一个错位对象,一次交换可能同时让棋子和空格归位,使错位数减少
下面两个棋盘只差一次合法交换:左图第二列第一行的空格,与第三列第三行的黑棋交换后,就得到目标。
左图若包含空格,错位数为
这里
4 搜索上限
从初始棋盘的
递归中已走
- 若
,返回失败。 - 若到达目标,返回成功。
- 否则枚举合法交换,递归后恢复棋盘。
注意剪枝条件是 >,不是 >=。当
4.1 最优性
设最优解需要
因此,当上限达到
4.2 避免立即返回
若本次交换后,下一次立刻与原来的空位交换,就会回到相同棋盘,白走两步。删除这两步仍能接上原路径,因此最短路不会包含这种操作,可以直接跳过。
这只是消除一步撤销。它不等于全局判重,也不会消除所有较长的环。
5 代码实现
代码每次重新统计
#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;
}
棋盘固定为
完整题解:pcs2:骑士精神。
6 与迭代加深的关系
普通迭代加深相当于取
加成序列中的翻倍剪枝也在判断“剩余次数够不够”。两者的共同点是使用乐观估计排除无解分支;IDA* 则明确以
7 相关题解
暂无相关题解