一、实验内容
编写九宫重排问题的启发式搜索（A*算法）求解程序。在3х3组成的九宫棋盘上，放置数码为1~8的8个棋子，棋盘中留有一个空格，空格周围的棋子可以移动到空格中，从而改变棋盘的布局。根据给定初始布局和目标布局，编程给出一个最优的走法序列。
二、实验提示
对于九宫重排问题的解决，首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵，问题即通过矩阵的变换，可以变换为目标状态对应的矩阵。由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。
如果初始状态可以到达目标状态，那么采取什么样的方法呢？常用的状态空间搜索有深度优先和广度优先。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。由于九宫重排问题状态空间共有9!个状态，如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里要求采用A*算法求解。
A*算法是启发式搜索算法，启发式搜索就是在状态空间中对每一个搜索分支进行评估，得到最好的分支，再从这个分支进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，利用当前与问题有关的信息作为启发式信息指导搜索，这些信息能够有效省略大量无谓的搜索路径，大大提高了搜索效率。
启发式搜索算法定义了一个估价函数f(n)，与问题相关的启发式信息都被计算为一定的 f(n) 的值，引入到搜索过程中。f(n) = g(n) +h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到节点n的实际代价，h(n)是从节点n到目标节点最佳路径的估计代价。 在九宫重排问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数h(n)估计的是节点n到目标节点的距离，我们可以用欧几里德距离、曼哈顿距离或是两节的状态中数字的错位数来估计。
三、存储结构的定义
typedef struct node//八数码结构体
{
int nine[N][N];//数码状态
int f;//估价值
int direct;//空格移动方向
struct node *parent;//父节点
}pNode;
//----------------------------------顺序表结构体----------------------------------//
typedef struct list
{
p_node a[MAX_NODESIZE];
long length;
}list, *p_list;
//------------------------------------声明函数------------------------------------//
int w(p_node s); //启发函数，再次设置为曼哈顿距离
int f(p_node s); //估价函数
void init_node(); //初始化
void out_node(p_node s); //输出八数码
void list_reverse(p_node &p); //将链表逆序
void out_list(p_list &l); //输出OPEN表
bool search_list(p_list &l, p_node s);//对表进行查找，成功返回true
void sort_list(p_list &l); //对OPEN表进行排序（按f从小到大）
void add_list(p_list &l, p_node s); //加入结点到OPEN表中或CLOSE表中
void copy_node(p_node s1, p_node &s2);//生成新的结点（将s2赋值给s1）
void delete_list(p_list &l); //从OPEN表或CLOSE中删除结点
bool is_equal(p_node s1, p_node s2); //判断两节点是否相等
bool up_mov(p_node &s); //空格上移
bool down_mov(p_node &s); //空格下移
bool left_mov(p_node &s); //空格左移
bool right_mov(p_node &s); //空格右移
void move(p_node s); //移动父节点并加入未探索表中（扩展结点）
int find_i(int a);
int find_j(int a);
四、算法的描述
（1）把初始节点S0 放入Open表中，f(S0)=g(S0)+h(S0);
（2）如果Open表为空，则问题无解，失败退出；
（3）把Open表的第一个节点取出放入Closed表，并记该节点为n;
（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；
（5）若节点n不可扩展，则转到第（2)步；
（6）扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni) (i=1,2,……)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；
（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；
（8）转到第（2）步。
五、实现的功能
测试数据：初始状态：123456780 目标状态：012345678
【输入格式】
输入包含三行，每行3各整数，分别为0-8这九个数字，以空格符号隔开，标识问题的初始状态。0表示空格，例如：
2 0 3
1 8 4
7 6 5
六、伪代码
bool check(Node a)
{
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
if(a.map[i][j]!=owali[i][j])
return false;
return true;
}
bool getvis(Node a)
{
string tmp="";
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
{
tmp+=a.map[i][j];
}
if(hsh.find(tmp)!=hsh.end())
return false;
hsh.insert(tmp);
return true;
}
int geth(Node a)
{
int ans=0;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
if(a.map[i][j]!=owali[i][j])
ans++;
return ans;
}
bool bfs(int x,int y)
{
Node start;
start.x=x,start.y=y;
start.pre='X';
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
start.map[i][j]=hajime[i][j];
start.g=0;
start.h=geth(start);
start.f=start.g+start.h;
priority_queue<Node,vector<Node>,cmp> open;
open.push(start);
while(!open.empty())
{
Node tmp=open.top(),tmp1;
open.pop();
if(check(tmp))
{
cout<<tmp.g<<endl;
return true;
}
tmp1=tmp;
if(tmp1.pre!='U'&&tmp1.x+1<3)
{
tmp1.g++;
tmp1.pre='D';
swap(tmp1.map[tmp1.x][tmp1.y],tmp1.map[tmp1.x+1][tmp1.y]);
tmp1.x++;
if(getvis(tmp1))
{
tmp1.h=geth(tmp1);
tmp1.f=tmp1.g+tmp1.h;
open.push(tmp1);
}
}
tmp1=tmp;
if(tmp1.pre!='D'&&tmp1.x-1>=0)
{
tmp1.g++;
tmp1.pre='U';
swap(tmp1.map[tmp1.x][tmp1.y],tmp1.map[tmp1.x-1][tmp1.y]);
tmp1.x--;
if(getvis(tmp1))
{
tmp1.h=geth(tmp1);
tmp1.f=tmp1.g+tmp1.h;
open.push(tmp1);
}
}
tmp1=tmp;
if(tmp1.pre!='L'&&tmp1.y+1<3)
{
tmp1.g++;
tmp1.pre='R';
swap(tmp1.map[tmp1.x][tmp1.y],tmp1.map[tmp1.x][tmp1.y+1]);
tmp1.y++;
if(getvis(tmp1))
{
tmp1.h=geth(tmp1);
tmp1.f=tmp1.g+tmp1.h;
open.push(tmp1);
}
}
tmp1=tmp;
if(tmp1.pre!='R'&&tmp1.y-1>=0)
{
tmp1.g++;
tmp1.pre='L';
swap(tmp1.map[tmp1.x][tmp1.y],tmp1.map[tmp1.x][tmp1.y-1]);
tmp1.y--;
if(getvis(tmp1))
{
tmp1.h=geth(tmp1);
tmp1.f=tmp1.g+tmp1.h;
open.push(tmp1);
}
}
}
return false;
}