帮同学写的八数码，启发式搜索
创建两个表open，close,分别用的stl中的优先队列priority_queue和map,好久没写过代码了，bug调了半天
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <time.h>
using namespace std;
struct Item //每一个状态
{
int state[][];
int Pre; //父状态在path中的下标
int F,G,H; //估计函数 F=G+H
Item(int state[][],int Pre,int G,int H) //构造函数
{
this->Pre=Pre;
this->G=G;
this->H=H;
this->F=G+H;
for(int i=;i<;i++)
for(int j=;j<;j++)
this->state[i][j]=state[i][j];
}
bool operator <(const Item temp) const //运算符重载，用于priority_queue中元素的比较
{
return F>temp.F;
}
bool operator ==(const Item temp) const
{
for(int i=;i<;i++)
for(int j=;j<;j++)
if(state[i][j]!=temp.state[i][j]) return ;
return ;
}
}; priority_queue<Item> Open; //存储扩展出但还没有访问的表
map<int,bool> Close; //存储已经访问过的节点
vector<Item> path; //保存路径
int arrays[][]={,,,,,,,,},arraye[][]={,,,,,,,,}; //八数码初始状态和目标状态
int dx[]={,,-,},dy[]={,-,,}; //四个方向扩展
int CalcuH(const int a0[][],const int a1[][]) //CalcuH（当前状态，目标状态）计算 H，如果目标状态和当前状态某个位置数字不同，dis自加1
{
int dis=;
for(int i=;i<;i++)
for(int j=;j<;j++)
if(a0[i][j]!=a1[i][j]) dis++;
return dis;
}
bool Judge(const int p0[][],const int p1[][]) //两者逆序数奇偶性相等,看八数码是否有解
{
int ss = , ee = ;
for(int i=; i<; ++i)
for(int j=; j<i; ++j) {
if(p0[j/][j%] != && p0[j/][j%] < p0[i/][i%]) ++ss;
if(p1[j/][j%] != && p1[j/][j%] < p1[i/][i%]) ++ee;
}
return (ss&) == (ee&);
}
int GetIndex(const int a[][]) //获取hash值，将Close[t]设置为1，表示已经访问过
{
int t=;
for(int i=;i<;i++)
for(int j=;j<;j++)
t=t*+a[i][j];
return t;
}
int PrintPath(const Item p) //递归打印路径
{
if(p.Pre==-)
{
for(int i=;i<;i++)
{
for(int j=;j<;j++)
cout<<" "<<p.state[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return ;
}
PrintPath(path[p.Pre]);
cout<<p.G<<" ==>"<<endl;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
cout<<" "<<p.state[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return ;
}
/*search()函数中的思路：
1.将初始节点放入open。（open是优先队列，f最小的节点排在队列的最前面）
2.从open中取出f最小的节点p,放入到path中，如果为目标节点，则递归打印路径。否则将该状态放入到close中，并生成他的扩展节点集P(就是将空白点往四个方向移动)。
3.对于扩展出的每个子节点 temp：
temp.calcuf()，计算f,pre,
如果temp不在close，就把它放入open中,否则不管
4.回到步骤2; 八数码无解情况判断：
初始状态和目标状态的逆序数奇偶性相同，则可到达
*/
void Search(Item s,int end[][])
{
int x,y,mx,my;
path.clear();
Open.push(s);
while()
{
Item e=Open.top();
Open.pop();
path.push_back(e);
int in=GetIndex(e.state);
Close[in]=; //标记表示已经访问过
int len=path.end()-path.begin()-; //获取e节点在path中的位置，他是扩展出的节点的父节点。
if(CalcuH(e.state,end)==)
{
//cout<<e.G<<endl;
cout<<"一共需要"<<e.G<<"步"<<endl;
PrintPath(e);
return;
}
for(int i=;i<;i++) //找到0的位置，0表示空白
for(int j=;j<;j++)
if(e.state[i][j]==)
x=i,y=j;
for(int i=;i<;i++) //向四个方向扩展
{
mx=x+dx[i],my=y+dy[i];
if(mx>||mx<||my<||my>) //判断是否跑出3*3的数组
continue;
swap(e.state[mx][my],e.state[x][y]); //将空白点与周围点交换位置
Item temp(e.state,len,e.G+,CalcuH(e.state,arraye)); //构造出新的状态节点
swap(e.state[mx][my],e.state[x][y]); //再交换回来
int index=GetIndex(temp.state); //获取hash值
if(!Close.count(index))
{
Open.push(temp);
}
}
}
return;
}
int main()
{
clock_t t=clock(),e;
Item s(arrays,-,,CalcuH(arrays,arraye));
if(Judge(arrays,arraye)) //判断是否有解
Search(s,arraye);
else
cout<<"no path"<<endl;
e=clock();
cout<<"run time : "<<e-t<<" ms"<<endl;
return ;
}