1.资料请参考刘汝佳的黑书，组合数学。
A*使用了h(s)做为在结点s下的代价下界值，转移时有h(s1)>=h(s2)+c(s1+s2),其中c(s1,s2)为状态s1转移到状态s2时所花费的代价！大家仔细揣摩一下这个方程，这个方程保证了A*算法的正确性（个人理解）
当s1,s2为相邻状态时有h(s1)>=h(s2)+1
然后用一个优先队列维护待扩展的结点，优先级判断的依据是f(s),f(s)=g(s)+h(s),g(s)表示从根结点到s结点花费的代价，h(s)为s结点的代价下界估计值。
个人感觉IDA*还好理解一些，它的核心思想就是用了一个变量pathLimit限制了搜索的深度，若成功则肯定是最优的，若不成功，则增加pathLimit直到有解！
2.A*实现
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
int p[9]= {1,1,2,6,24,120,720,5040,40320};
int encode(int *perm)//n=9
{
//八数码问题，九个格子，相当于总的排列数为9！
int sum=0;
for(int i=0; i<9; i++)
{
int count=0;
for(int j=0; j<i; j++)
{
if(perm[j]>perm[i])count++;
}
sum+=count*p[9-perm[i]];
}
return sum;
}
void decode(int sum,int *perm)
{
for(int i=0; i<9; i++)perm[i]=0;
for(int i=1; i<=9; i++)
{
int tot=sum/p[9-i]+1;
sum%=p[9-i];
int loc,count=0;
for(loc=0; loc<9; loc++)
{
if(!perm[loc])
{
count++;
if(count==tot)break;//!!找到空第tot个空位置
}
}
perm[loc]=i;
}
}
void initial(int *maze,int &space)
{
char grid;
for(int i=0; i<9; i++)
{
cin>>grid;
if(grid!='x')maze[i]=grid-'1'+1;
else
{
space=i;
maze[i]=9;
}
}
}
#define STATE 362890
struct Node
{
int preState;
int step;
int space;
int h;
} node[STATE];
bool vis[STATE];
bool isResolve(int *maze,int space)
{
int s=abs(double(2-space/3))+abs(double(2-space%3));
for(int i=0; i<9; i++)
{
for(int j=0; j<i; j++)
{
if(maze[i]>maze[j])s++;
}
}
if(s&1)return false;
else return true;
}
int h(int *maze)
{
int h=0;
for(int i=0; i<9; i++)
{
if(maze[i]!=9)h+=abs(double((maze[i]-1)/3-i/3))+abs(double( (maze[i]-1)%3-i%3));
}
return h;
}
int next[9][4]=
{
{-1,3,1,-1},
{0,4,2,-1},
{1,5,-1,-1},
{-1,6,4,0},
{3,7,5,1},
{4,8,-1,2},
{-1,-1,7,3},
{6,-1,8,4},
{7,-1,-1,5}
};
class cmp
{
public:
bool operator()(int sa,int sb)
{
return node[sa].h+node[sa].step>node[sb].h+node[sb].step;
}
};
bool AStar(int *maze,int space)
{
if(!isResolve(maze,space))return false;
memset(vis,0,sizeof(vis));
priority_queue<int,vector<int>,cmp> que;
int curState=encode(maze),nextState;
node[curState].preState=-1;
node[curState].step=0;
node[curState].space=space;
node[curState].h=h(maze);
que.push(curState);
while(!que.empty())
{
curState=que.top();
que.pop();
if(!curState)break;//目标状态
if(vis[curState])continue;
vis[curState]=true;
decode(curState,maze);
int cur=node[curState].space;
for(int i=0; i<4; i++)
{
if(next[cur][i]==-1)continue;
swap(maze[cur],maze[ next[cur][i] ] );
nextState=encode(maze);
if(!vis[nextState] || node[nextState].step>node[curState].step+1)
{
node[nextState].preState=curState;
node[nextState].space=next[cur][i];
node[nextState].step=node[curState].step+1;
node[nextState].h=h(maze);
que.push(nextState);
}
swap(maze[cur],maze[ next[cur][i] ] );
}
}
return true;
}
char dir[4]=
{
'l','d','r','u'
};
void output(int curState,int *maze)
{
decode(curState,maze);
int preState=node[curState].preState;
if(preState==-1)return;
output(preState,maze);
for(int i=0; i<4; i++)
{
if(next[node[preState].space][i]==node[curState].space)
{
cout<<dir[i];
break;
}
}
}
int main()
{
int maze[9],space;
initial(maze,space);
if(AStar(maze,space))output(0,maze);
else cout<<"unsolvable";
cout<<endl;
return 0;
}
3.IDA*（其实这个算法比我们想像中的要简单得多，我猜大家直接看代码就能看懂！！！）
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
void initial(int *maze,int &space)
{
char grid;
for(int i=0; i<9; i++)
{
cin>>grid;
if(grid!='x')maze[i]=grid-'1'+1;
else
{
space=i;
maze[i]=9;
}
}
}
bool isResolve(int *maze,int space)
{
int s=abs(double(2-space/3))+abs(double(2-space%3));
for(int i=0; i<9; i++)
{
for(int j=0; j<i; j++)
{
if(maze[i]>maze[j])s++;
}
}
if(s&1)return false;
else return true;
}
int h(int *maze)
{
int h=0;
for(int i=0; i<9; i++)
{
if(maze[i]!=9) h+=abs(double((maze[i]-1)/3-i/3))+abs(double( (maze[i]-1)%3-i%3));
}
return h;
}
int next[9][4]=
{
{-1,3,1,-1},
{0,4,2,-1},
{1,5,-1,-1},
{-1,6,4,0},
{3,7,5,1},
{4,8,-1,2},
{-1,-1,7,3},
{6,-1,8,4},
{7,-1,-1,5}
};
bool isAns(int *maze)
{
for(int i=0; i<8; i++)if(maze[i+1]-maze[i]!=1)return false;
return true;
}
int pathLimit;
int path[362890],pathLen;
bool IDAStar(int *maze,int len,int space)
{
if(len==pathLimit)
{
if(isAns(maze))
{
pathLen=len;
return true;
}
return false;
}
for(int i=0; i<4; i++)
{
if(next[space][i]!=-1)
{
if(len>0&&abs(double(i-path[len-1]))==2)continue;//!!不考虑相反的方向
swap(maze[space],maze[next[space][i]]);
path[len]=i;
if(h(maze)+len<=pathLimit&&IDAStar(maze,len+1,next[space][i]))
return true;
swap(maze[space],maze[next[space][i]]);
}
}
return false;
}
char dir[4]= {'l','d','r','u'};
void output()
{
for(int i=0; i<pathLen; i++)
{
switch(path[i])
{
case 0:
cout<<'l';
break;
case 1:
cout<<'d';
break;
case 2:
cout<<'r';
break;
case 3:
cout<<'u';
}
}
}
int main()
{
int maze[9],space;
initial(maze,space);
pathLimit=h(maze);
if(isResolve(maze,space))
{
while(!IDAStar(maze,0,space))pathLimit++;
output();
}
else cout<<"unsolvable";
cout<<endl;
return 0;
}