背景
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
格式
输入格式
输入初试状态，一行九个数字，空格用0表示
输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例1
样例输入1
283104765
样例输出1
4
这题直接广搜是可以的，不过非常地耗费内存和时间，所以这里用到了A*算法
股价函数是以它和目标节点的差作股价，不过单用股价函数是不可以的（全W的教训）
还要有现在所走的步数，把两者相加，得到优先级，优先级越低的越先搜索
priority = h(x) + step;
如何说明这个的正确性呢？假设有有一个节点x，h(x) = 2，如果它不能尽快地达到目标状态，以至于优先级超过排在第二的节点y，那么y就会被取出队列进行更新。要使股价函数h(x)的值要减少1（当h（x）=2时是特例），至少需要移动一步，这样就能够保证第一次搜到目标节点一定步数是最少的。如果还不明白，就这么再说一下个人的理解,(h[x]+step)是按照最优的情况移动一次h(x)就减少了1的步数加1进行预算，如果最优的情况下x都不比y优，那么就应当先搜索y。
Code:
/**
* Vijos.org
* Problem#1360
* Accepted
* Time:76ms
* Memory:996k
**/
#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef bool boolean;
typedef class MyData{
public:
char datas[][];
void in(){
for(int i=;i<=;i++){
for(int j=;j<=;j++){
cin>>datas[i][j];
}
}
}
MyData(){}
MyData(string str){
for(int i=;i<=;i++){
this->datas[i/][i%] = str[i];
}
}
boolean equals(MyData another){
for(int i=;i<=;i++){
for(int j=;j<=;j++){
if(this->datas[i][j]!=another.datas[i][j]) return false;
}
}
return true;
}
boolean operator <(MyData another) const{ for(int i=;i<=;i++){
for(int j=;j<=;j++){
if(this->datas[i][j]!=another.datas[i][j]) return this->datas[i][j]<another.datas[i][j];
}
}
return false;
}
}MyData;
typedef class Node{
public:
int pro;
int step;
MyData d;
int x;
int y;
Node():pro(),step(){}
Node(int pro,int step,MyData d):pro(pro),step(step),d(d){}
boolean operator <(Node another) const{
return this->pro>another.pro;
}
}Node;
int fstep = -;
priority_queue<Node> que;
set<MyData> s;
int m[][]={{,,-,},{,,,-}};
MyData aim("");
int h(Node node){
int result = ;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
if(node.d.datas[i][j]!=aim.datas[i][j]) result++;
}
}
return result;
}
void swap(Node* node,int x,int y,int x1,int y1){
char a=node->d.datas[x][y];
node->d.datas[x][y]=node->d.datas[x1][y1];
node->d.datas[x1][y1]=a;
}
void find(Node start){
start.step = ;
start.pro=h(start);
for(int a=;a<=;a++){
for(int b=;b<=;b++){
if(start.d.datas[a][b]==''){
start.x=a;
start.y=b;
break;
}
}
}
s.insert(start.d);
que.push(start);
while(!que.empty()){
Node e = que.top();
que.pop();
if(fstep != -&&e.step >= fstep) continue;
if(e.d.equals(aim)) fstep = e.step;
for(int i=;i<=;i++){
Node eu = e;
int x=eu.x,y=eu.y;
eu.x += m[][i];
eu.y += m[][i];
if(eu.x>=&&eu.x<=&&eu.y>=&&eu.y<=){
swap(&eu,x,y,eu.x,eu.y);
eu.pro = h(eu) + eu.step + ;
eu.step++;
if(!s.count(eu.d)){
s.insert(eu.d);
que.push(eu);
}
}
}
}
}
int main(){
MyData d;
d.in();
find(Node(,,d));
cout<<fstep;
return ;
}