<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script><style type="text/css">em{font-size: large;font-weight: bold;}</style>
洛谷P2324 [SCOI2005] 骑士精神
题目在P2324 [SCOI2005] 骑士精神
初步分析
输入棋盘当前的状态，要求出从当前状态转移到目标状态所需要的最少变换次数。将每种状态作为无向图的一个节点，能通过走“马”字相互转换的两种状态对应图上的两个相邻节点。
此时问题就转变成求从某结点A到目标节点B的最短路径的长度。
棋盘的状态不同，即棋盘上黑白子的位置、空白的位置不同；棋盘不同状态的转换通过能移动到空白处的棋子移动（改变位置）完成。
算法选用
假设大师在这题会用IDA*。棋盘的状态非常多，而题目有15的路径长度限制，饱学之士将能使用启发式搜索进行剪枝。对于图中的任意点M，经过该点的路径长\(l=AM+MB \leq 15\)。从始点开始绘制路径到\(M\)时\(MA\)已经有值，则在搜索树上剪去\(MB>15-AM\)的结点。
可以不严谨地证明当棋盘在M状态下有n个位置的状态不同时，最少需要n-1步来达到相同，计算两个状态间不同的个数为\(n = h(M,B)\) ，则在搜索树上剪去\(n-1+AM \geq 15\)的结点。这是启发式搜索的估值函数。
常用求最短路径的广度优先搜索由于不好储存节点状态（可能超内存）而不能实行，深度优先搜索由于连续两次搜索的状态相邻可以避免这一问题。为避免深度过大超时需要最大深度常量，在递归函数中能访问，与当前深度做判断是否剪枝
一般使用此方法会让深度递增到最大值，每个深度都重新搜索，叫限制深度的（迭代加深）深度优先搜索。
代码实现
- 创建一些全局量
这题的终点是个常量。走“马”也很常规。
//最后目标
int goal[5][5] = {
{1,1,1,1,1},
{0,1,1,1,1},
{0,0,2,1,1},
{0,0,0,0,1},
{0,0,0,0,0}
};
//用于走马
int dx[8] = { 1,1,2,2,-1,-1,-2,-2 };
//用于走马
int dy[8] = { 2,-2,1,-1,2,-2,1,-1 };
- 输入储存数据
没有什么特别，注意输入数据的字符中间没有空格。
char c;
for (int i = 0; i < 5; ++i)
{
for (int j = 0; j < 5; ++j)
{
cin >> c;
if (c == '*') {
blank[0] = i;
blank[1] = j;
chessboard[i][j] = 2;
}
else chessboard[i][j] = c - '0';
}
}//输入了棋盘
- “ID”部分
终止条件是深度depth、估值函数eval满足\(depth>maxdepth\)、\(eval+depth-1>maxdepth\)回溯；或\(eval=0\)跳出递归，将depth赋给能在main()中被访问的变量。
这里选择当前节点的空白处位置x和y、棋子位置chessboard（放在了全局）、当前深度depth和本轮的最大深度maxdepth作为递归dfs()的参数。
//储存棋盘
int chessboard[5][5];
//标记是否成功了
bool succ = false;
//限制深度的深搜
void dfs(int depth,int x,int y, int maxdepth) {
if (depth > maxdepth) {
return;
}//步数超过了限制的最大步数
int count = eval();
if (count == 0) {
succ = true;
return;
}//达成目标
if (depth + count - 1 > maxdepth)
{
return;
}//未来不能满足条件了
for (int i = 0; i lt; 8; ++i) {
int a = x + dx[i], b = y + dy[i];
if (0 <= a && a < 5 && 0 <= b && b < 5) {
swap(chessboard[a][b], chessboard[x][y]);
dfs(depth + 1, a, b, maxdepth);
if (succ)return;
swap(chessboard[a][b], chessboard[x][y]);//回溯
}
}
}
int main(){
...
int ans = -1;
for (int i = 1; i <= 15; ++i) {
dfs(0, x, y, i);
if (succ) {
ans = i;
break;
}
}
cout << ans << endl;
...
}
- 估值函数
根据前面的分析，估值函数只需要统计两个状态的不同处的个数并返回就可以。
//估值函数
int eval() {
int ans = 0;
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (chessboard[i][j] != goal[i][j]) {
ans++;
}
}
}
return ans;
}
最终代码
#include<iostream>
using namespace std;
//储存棋盘
int chessboard[5][5];
//最后目标
int goal[5][5] = {
{1,1,1,1,1},
{0,1,1,1,1},
{0,0,2,1,1},
{0,0,0,0,1},
{0,0,0,0,0}
};
//用于走马
int dx[8] = { 1,1,2,2,-1,-1,-2,-2 };
//用于走马
int dy[8] = { 2,-2,1,-1,2,-2,1,-1 };
//空白坐标
int blank[2];
//标记是否成功了
bool succ = false;
//估值函数
int eval() {
int ans = 0;
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (chessboard[i][j] != goal[i][j]) {
ans++;
}
}
}
return ans;
}
//限制深度的深搜
void dfs(int depth,int x,int y, int maxdepth) {
//if (maxdepth == 7)cout << depth << endl;
if (depth > maxdepth) {
return;
}//步数超过了限制的最大步数
int count = eval();
if (count == 0) {
succ = true;
return;
}//达成目标
if (depth + count - 1 > maxdepth)
{
return;
}//未来不能满足条件了
for (int i = 0; i < 8; ++i) {
int a = x + dx[i], b = y + dy[i];
if (0 <= a && a < 5 && 0 <= b && b < 5) {
swap(chessboard[a][b], chessboard[x][y]);
dfs(depth + 1, a, b, maxdepth);
if (succ)return;
swap(chessboard[a][b], chessboard[x][y]);//回溯
}
}
}
int main() {
int t; cin >> t;
while (t--)
{
succ = false;
char c;
for (int i = 0; i < 5; ++i)
{
for (int j = 0; j < 5; ++j)
{
cin >> c;
if (c == '*') {
blank[0] = i;
blank[1] = j;
chessboard[i][j] = 2;
}
else chessboard[i][j] = c - '0';
}
}//输入了棋盘
int ans = -1;
for (int i = 1; i <= 15; ++i) {
dfs(0, blank[0], blank[1], i);
if (succ) {
ans = i;
break;
}
}
cout << ans << endl;
}
}
附加内容
对于没见过迭代加深DFS的菜的人，可以通过构造一个小的数据结构来储存状态，避免超出内存。使用广度优先搜索和A*。
广度优先搜索中，对每个结点的搜索（直接写在了main()中）选用描述当前棋盘状态的board、当前深度depth作为隐式的参数，最大深度15可以看作常量参数。由于难以回溯而采取用队列queue<pack>储存信息的方式。
添加该状态的前一个状态的空白处坐标在pack结构内，可以减去重复枝；应该也可以用unordered_map来储存搜索过的所有状态来减少重复。代码使用了priority_queue来提速。
#include<iostream>
#include<bitset>
#include<queue>
#include<chrono>
using namespace std;
typedef bitset<25> bs;
//用于走马
int dx[8] = { 1,1,2,2,-1,-1,-2,-2 };
//用于走马
int dy[8] = { 2,-2,1,-1,2,-2,1,-1 };
//记录棋盘状态
struct chessboard {
bs pieces;
int blank;
//空白位置的坐标
const pair cdntBlank() const {
return make_pair(blank / 5, blank % 5);
}
//将(x,y)转换成pos
static int castPos(const pair& p) {
if (0 <= p.first && p.first < 5 && 0 <= p.second && p.second < 5) {
return p.first * 5 + p.second;
}
else return -1;
}
};
const chessboard goal = { 549855 ,12 };
//返回移动后的棋盘状态
chessboard moveReturn(const chessboard& c, int pos) {
bs temp = c.pieces;
temp[c.blank] = c.pieces[pos];
temp[pos] = 0;
return chessboard{ move(temp) ,pos };
}
//估值函数
int evaluateDistance(const chessboard& crt_board, const chessboard& goal) {
int ans = 0;
for (int i = 0; i < 25; ++i) {
ans = (crt_board.pieces ^ goal.pieces).count();
}
if (!crt_board.pieces[goal.blank])ans++;
if (!goal.pieces[crt_board.blank])ans++;
if (goal.blank == crt_board.blank)ans -= 2;
return ans;
}
//用于队列的类
struct pack
{
chessboard board;
int last_blank;
int depth;
int eval;
class less {
public:
int operator()(const pack& a, const pack& b) {
return a.depth + a.eval > b.depth + b.eval;
}
};
};
//queue bfs_queue;
int main() {
int t; cin >> t;
const int MAXDEPTH = 15;
while (t--)
{
chessboard board{ 0,0 };
bs temppieces;
for (int i = 0; i < 25; ++i) {
static char c;
cin >> c;
if (c == '1')temppieces[i] = 1;
else if (c == '*')board.blank = i;
//else temppieces[i] = 0;
}
board.pieces = move(temppieces);//输入棋盘
//bfs_queue = queue();
int ans = -1;
priority_queue,pack::less> bfs_queue;
bfs_queue.push({ board,-1,0,evaluateDistance(board,goal) });
int pos;
do
{
pack front = bfs_queue.top();
bfs_queue.pop();
if (front.eval == 0) {
ans = front.depth;
break;
}
else if (front.depth >= MAXDEPTH) {
continue;
}
if (front.depth + front.eval - 1 > MAXDEPTH) {
continue;
}
auto x_y = front.board.cdntBlank();
int cx_y = chessboard::castPos(x_y);
for (int i = 0; i < 8; ++i) {
pos = chessboard::castPos(make_pair(x_y.first + dx[i], x_y.second + dy[i]));
if (pos == front.last_blank)continue;
if (pos != -1) {
chessboard newboard = move(moveReturn(front.board, pos));
bfs_queue.push({ newboard,
cx_y,
front.depth + 1,
evaluateDistance(newboard,goal) });
}
}
} while (!bfs_queue.empty());
cout << ans << endl;
}
}