/*
八数码问题求解
输入输出都是随机生成
open表为优先队列pQueue
close表为键值对容器hashx
八数码状态有解的情况为起始和目标状态的排成一行后的逆序数的奇偶性相同
启发函数采用计算当前状态和目标状态的哈夫曼距离
*/
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<string.h>
using namespace std;
#define abs(x) ((x)>0?(x):-(x))
int direction[4][2]={-1,0,0,1,1,0,0,-1};
int cost[9][2];//代价
bool inverse=false;
struct Eight
{
int num[3][3];//状态
int hash;//哈希值
int deep;//深度
int hValue;//估价值
int pre;//父亲节点
bool inQueue;
bool operator < (const struct Eight &a) const//比较函数
{
return a.hValue<hValue;
}
void value()//计算估价值
{
hValue=deep;
for(int i=0;i<9;++i)
{
hValue+=abs(i/3-cost[num[i/3][i%3]][0]);
hValue+=abs(i%3-cost[num[i/3][i%3]][1]);
}
}
void getHash()//计算哈希值
{
hash=num[0][0];
for(int i=1;i<9;++i)
{
hash*=10;
hash+=(num[i/3][i%3]);
}
}
}eightBegin,eightEnd;//起始和目标
struct qElement
{
int hash;
int hValue;
bool operator < (const struct qElement &a) const//比较函数
{
return (a.hValue==hValue)?(a.hash<hash):(a.hValue<hValue);
}
};
priority_queue<struct qElement>pQueue;//优先队列
map<int,struct Eight>hashx;
stack<struct Eight>path;
bool checkInverse(struct Eight &a)//计算状态逆序数的奇偶性 true为奇数 false为偶数
{
int summ=0;
for(int i=1;i<9;++i)
{
if(a.num[i/3][i%3]==0) continue;
for(int j=i;j>=0;--j)
{
if(a.num[j/3][j%3]==0) continue;
if(a.num[j/3][j%3]>a.num[i/3][i%3])
summ++;
}
}
return (summ%2==1?true:false);
}
void randInput()//生成随机起始状态
{
int i,j;
bool numUsed[9];
int temp;
memset(numUsed,false,sizeof(numUsed));
for(i=0;i<9;++i)
{
for(;;)
{
temp=rand()%10;
if(!numUsed[temp])
break;
}
eightBegin.num[i/3][i%3]=temp;
numUsed[temp]=true;
}
eightBegin.deep=0;
eightBegin.inQueue=false;
inverse=checkInverse(eightBegin);
printf("起始状态:\n");
for(i=0;i<3;++i)
{
for(j=0;j<3;++j)
printf("%d ",eightBegin.num[i][j]);
printf("\n");
}
}
void randOutput()//生成随机目标状态
{
int i,j;
bool numUsed[9];
int temp;
for(;;)
{
memset(numUsed,false,sizeof(numUsed));
for(i=0;i<9;++i)
{
for(;;)
{
temp=rand()%10;
if(!numUsed[temp])
break;
}
eightEnd.num[i/3][i%3]=temp;
numUsed[temp]=true;
}
if(inverse==checkInverse(eightEnd))
break;
}
printf("目标状态:\n");
for(i=0;i<3;++i)
{
for(j=0;j<3;++j)
printf("%d ",eightEnd.num[i][j]);
printf("\n");
}
}
void output(struct Eight &a)//输出状态
{
int i,j;
for(i=0;i<3;++i)
{
for(j=0;j<3;++j)
printf("%d ",a.num[i][j]);
printf("\n");
}
printf("-------------------\n");
}
bool checkEqual(struct Eight &a)//判断是否是目标状态
{
int i,j;
for(i=0;i<3;++i)
{
for(j=0;j<3;++j)
{
if(a.num[i][j]!=eightEnd.num[i][j])
return false;
}
}
return true;
}
void getOutputCost()
{
int i,j;
for(i=0;i<3;++i)
for(j=0;j<3;++j)
{
cost[eightEnd.num[i][j]][0]=i;
cost[eightEnd.num[i][j]][1]=j;
}
}
bool checkError(int x,int y)//计算是否出界
{
if(x<0||x>2||y<0||y>2) return true;
return false;
}
int Astar()//A*算法
{
struct Eight temp,now,change;
struct qElement id,ans;
id.hash=eightBegin.hash;
id.hValue=eightBegin.hValue;
pQueue.push(id);
int i,idx,idy;
for(int c=0;!pQueue.empty();++c)
{
if(c>15678) break;//防止无限死循环
//printf("%d\n",c);
id=pQueue.top();
pQueue.pop();
now=hashx.find(id.hash)->second;
hashx.find(id.hash)->second.inQueue=false;
if(checkEqual(now))
{
printf("Found!\n");
return now.hash;
}
for(i=0;i<9;++i)
{
if(now.num[i/3][i%3]==0)
{
idx=i/3;
idy=i%3;
break;
}
}
for(i=0;i<4;++i)
{
if(checkError(idx+direction[i][0],idy+direction[i][1])) continue;
temp=now;
swap(temp.num[idx][idy],temp.num[idx+direction[i][0]][idy+direction[i][1]]);
temp.deep++;
temp.pre=now.hash;
temp.value();
temp.getHash();
if(hashx.count(temp.hash)==0)
{
hashx.insert(make_pair(temp.hash,temp));
//output(temp);
ans.hash=temp.hash;
ans.hValue=temp.hValue;
pQueue.push(ans);
}
else
{
change=hashx.find(temp.hash)->second;
if(temp.hValue<change.hValue)
{
hashx.find(temp.hash)->second=temp;
if(!change.inQueue)
{
//output(temp);
ans.hash=temp.hash;
ans.hValue=temp.hValue;
pQueue.push(ans);
}
}
}
}
}
printf("Not found!\n");
return -1;
}
void outPath(int idx)
{
struct Eight temp;
for(;idx!=eightBegin.hash;)
{
temp=hashx.find(idx)->second;
path.push(temp);
idx=temp.pre;
}
printf("一共需要%d步~\n",path.size());
output(eightBegin);
for(;!path.empty();)
{
output(path.top());
path.pop();
}
printf("结束\n");
}
int main()
{
int ans;
//freopen("out.txt","w",stdout);
srand((unsigned)time(NULL));//设置随机种子
randInput();
randOutput();
getOutputCost();
eightBegin.value();
eightBegin.getHash();
hashx.insert(make_pair(eightBegin.hash,eightBegin));
ans=Astar();
if(ans!=-1)
outPath(ans);
system("pause");
return 0;
}
来源：http://blog.csdn.net/acm_ted/article/details/8881231