1312 : 搜索三·启发式搜索
时间限制:
10000ms
单点时限:
1000ms
内存限制:
256MB
描述
在小Ho的手机上有一款叫作八数码的游戏，小Ho在坐车或者等人的时候常用这个游戏来打发时间。html
游戏的棋盘被分割成3x3的区域，上面放着标记有1~8八个数字的方形棋子，剩下一个区域为空。ios
游戏过程当中，小Ho只能移动棋子到相邻的空区域上。当小Ho将8个棋子都移动到以下图所示的位置时，游戏就结束了。spa
小Hi：小Ho，你以为若是用计算机来玩这个游戏应该怎么作？3d
小Ho：用计算机来玩么？我以为应该是搜索吧，让我想想。code
提示：启发式搜索htm
输入
第1行：1个正整数t，表示数据组数。1≤t≤8。blog
接下来有t组数据，每组数据有3行，每行3个整数，包含0~8，每一个数字只出现一次，其中0表示空位。游戏
输出
第1..t行：每行1个整数，表示该组数据解的步数。若无解输出"No Solution!"内存
3 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 8 7 0 8 0 1 5 7 4 3 6 2样例输出
0 No Solution! 25
求最少多少步能够解决八数码问题。按照题目的指导，用康托展开的方法将一个状态映射到一个数，用这个数表明状态。而后用启发式搜索方法求出最少须要多少步能够解决问题。了解启发式搜索相关知识能够点击启发式搜索技术。
ci
代码：
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int factor[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
vector<int> statnum(9);
vector<int> des({1, 2, 3, 4, 5, 6, 7, 8, 9});
int destination;
struct state
{
int f;
int g;
int h;
int x;
state(int f, int g, int h, int x):f(f), g(g), h(h), x(x){};
friend bool operator<(const state& a, const state& b)
{
if(a.f != b.f) return a.f > b.f;
else return a.g > b.g;
}
};
int cantor(const vector<int>& num)
{
int x = 0;
for(int i = 0; i < 9; ++i)
{
int tp = 0;
for(int j = i+1; j < 9; ++j)
{
if(num[i] > num[j]) tp++;
}
x += tp * factor[8-i];
}
return x;
}
vector<int> decantor(int x)
{
vector<int> num;
int a[9] = {0};
int used[9] = {0};
for(int i = 0; i < 9; ++i)
{
a[i] = x / factor[8-i];
x %= factor[8-i];
int cnt = 0;
for(int j = 0; j < 9; ++j)
{
if(!used[j])
{
cnt++;
if(a[i] + 1 == cnt)
{
num.push_back(j+1);
used[j] = 1;
break;
}
}
}
}
return num;
}
int getDist(int a, int b)
{
return (abs(a/3-b/3) + abs(a%3-b%3));
}
int getEvalution(vector<int> num)
{
int h = 0;
for(int i = 0; i < 9; ++i)
{
h += getDist(i, num[i]-1);
}
return h;
}
void solve()
{
priority_queue<state>openlist;
set<int>closelist;
int h = getEvalution(statnum);
openlist.push(state(h, 0, h, cantor(statnum)));
int step = 0;
bool hasSolution = false;
while(!openlist.empty())
{
state cur = openlist.top();
openlist.pop();
int x = cur.x;
closelist.insert(x);
if(destination == x)
{
hasSolution = true;
step = cur.g;
break;
}
vector<int> curstate = decantor(x);
for(int i = 0; i < 9; ++i)
{
if(curstate[i] == 9)
{
if(i % 3 != 2)
{
swap(curstate[i], curstate[i+1]);
int g = cur.g + 1;
int h = getEvalution(curstate);
int f = g + h;
int x = cantor(curstate);
if(closelist.find(x) == closelist.end())
{
openlist.push(state(f, g, h, x));
}
swap(curstate[i], curstate[i+1]);
}
if(i % 3 != 0)
{
swap(curstate[i], curstate[i-1]);
int g = cur.g + 1;
int h = getEvalution(curstate);
int f = g + h;
int x = cantor(curstate);
if(closelist.find(x) == closelist.end())
{
openlist.push(state(f, g, h, x));
}
swap(curstate[i], curstate[i-1]);
}
if(i / 3 != 2)
{
swap(curstate[i], curstate[i+3]);
int g = cur.g + 1;
int h = getEvalution(curstate);
int f = g + h;
int x = cantor(curstate);
if(closelist.find(x) == closelist.end())
{
openlist.push(state(f, g, h, x));
}
swap(curstate[i], curstate[i+3]);
}
if(i / 3 != 0)
{
swap(curstate[i], curstate[i-3]);
int g = cur.g + 1;
int h = getEvalution(curstate);
int f = g + h;
int x = cantor(curstate);
if(closelist.find(x) == closelist.end())
{
openlist.push(state(f, g, h, x));
}
swap(curstate[i], curstate[i-3]);
}
}
}
}
if(!hasSolution) cout << "No Solution!" << endl;
else cout << step << endl;
}
int main()
{
int n;
cin >> n;
destination = cantor(des);
while(n--)
{
for(int i = 0; i < 9; ++i)
{
cin >> statnum[i];
if(statnum[i] == 0) statnum[i] = 9;
}
solve();
}
return 0;
}