八数码难题
题目描述
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入格式
输入初始状态,一行九个数字,空格用0表示
输出格式
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例 #1
样例输入 #1
283104765
样例输出 #1
4
题解
这题是适用于A*算法的一个比较经典的题目,问题在于如何定义估价函数。这里我定义的$h(x)$为当前各个数字到目标位置的曼哈顿距离之和,即
在搜索时不要想着去直接移动数字,不好写代码,可以去移动空位来实现数字的移动。
代码&&注释
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
int final[] = {-1, 0, 1, 2, 5, 8, 7, 6, 3};
struct node
{
int state, g, h;
node(int _state, int _g) // _state状态 _g实际的走的步数
{
state = _state;
g = _g;
h = 0;
int tmp = state;
for (int i = 8; i >= 0; i--) // 算h(x)函数
{
int a = tmp % 10; // 分离每一位数字
tmp /= 10;
if (a != 0)
h += abs((i / 3) - (final[a] / 3)) + abs((i % 3) - (final[a] % 3));
// 算每一位数字到目标位置的曼哈顿距离
}
}
};
bool operator<(node x, node y) // A*算法的priority_queue用的
{
return x.g + x.h > y.g + y.h;
}
priority_queue<node> q;
map<int, bool> vis; // 将9!种排列映射到布尔变量
int main()
{
int n;
cin >> n;
q.push(node(n, 0));
vis[n] = 1; // 初始状态是一定被访问了的
while (!q.empty())
{
node u = q.top();
int c[3][3], f = 0, g = 0, n = u.state;
q.pop();
if (u.state == 123804765) // 目标状态
{
cout << u.g << endl; // 输出步数
return 0;
}
for (int i = 2; i >= 0; i--)
for (int j = 2; j >= 0; j--) // 把当前的一维状态化为二维矩阵
{
c[i][j] = n % 10, n /= 10;
if (!c[i][j])
f = i, g = j; // 找到空位
}
for (int i = 0; i < 4; i++) // 上下左右移动空位
{
int nx = f + dx[i], ny = g + dy[i], ns = 0;
if (nx < 0 || ny < 0 || nx > 2 || ny > 2) // 判边界
continue;
swap(c[nx][ny], c[f][g]); // 尝试移动空位
for (int i = 0; i < 3; i++) // // 把当前的二维矩阵化为一维状态
for (int j = 0; j < 3; j++)
ns = ns * 10 + c[i][j];
if (!vis.count(ns)) // 查找当前状态是否被遍历过
{
vis[ns] = 1; // 标记
q.push(node(ns, u.g + 1)); // 扔到priority_queue中
}
swap(c[nx][ny], c[f][g]); //把空位再移回来
}
}
}
Comments NOTHING