一.A*算法
A*算法与普通的BFS不同的点在于，BFS始终是以当前节点到初始节点的距离为基准，每次都选取较小值进行扩展。而A*算法则是通过一个估价函数F(x) = G(x) + H(X)，每次都已这个值为基准，选取较小的值进行扩展。
二.估价函数
F(x) = G(x) + H(X)
F(x)是我们最后估计出来的值，不是真实值，这个值越小说明我们从当前状态进行扩展就会更快地到达目标状态
G(x)是当前节点到初始节点的距离，也就是BFS中的那个值，这个值是真实值，是我们通过一步一步扩展出来的值
H(x)是从当前节点到目标节点的距离（估计值），这个我们通过预估可以帮助我们在选择下一步扩展的节点的时候有一个偏向，会让我们更加偏向于更快地更直接地找到目标节点
从这个式子当中我们可以看出，普通的BFS也是A*算法的一种，他的H(x) = 0.
三.估价函数的影响
设H(X)为我们的估计函数，H'(x)为实际从当前节点到目标节点的值。
如果满足H(x) < H'(x)的话，我们的搜索范围大，效率慢，但是一定能找到最优解法。BFS的估价函数是0，永远都小于H'(x)，但是由于这个估价函数太小，所以没有任何指导作用。所以很慢。
如果满足H(x) = H'(x)的话，我们的搜索过程会按照最优解的路径来走，这时我们一定能找到最优解，而且搜索效率是最高的。当两个函数永远相等的时候我们可以发现我们的搜索变成了具有准确性的搜索，而不再是具有某一偏向的搜索，他会直接指示我们找到答案，当然这也只是最理想状态，如果我们知道这个函数之后就能直接推理出答案。
如果满足H(x) <= H'(x)的话，某些情况下效率要比单纯小于快很多。
如果满足H(x) > H'(x)的话，这时搜索范围很小，效率非常高， 但是最后的结果不一定能找到最有解。
H(x)相当于对于我们的决策提供了有价值的信息，当我们掌握一部分信息的时候(<的情况)，可以一定程度上帮助我们找到最优解，当我们准确地掌握所有信息的时候(=的情况)，我们就可以很准却地推理出来最优的解。当我们准确地掌握了一些信息的时候，还掌握了一些错误的信息(>的情况)，这就导致我们可能会做出错误的决定(认为搜索出来的解始终为最优解)，但是有一点是肯定的，不管我们获得的信息当中有无错误信息，信息越多我们作出决策就越快。这也就是为什么A*比较快。所以算法的重点全部都再估价函数当中。
四.常用估价函数
常用图搜索的估价函数，曼哈顿距离(常用)，使用代价常数修正的欧几里得距离，对角距离(先通过一个对角线移动到和目标点在同一条平行于坐标轴的直线，再进行欧几里得距离)。
五.例题说明
题目链接：Eight
解题思路：这里的估价函数为：
1.当前状态下不在本位的数字数量
2 1 3
4 5 6
7 8
这时不在本位的数量为2
2.当前状态下每一个数字当前位置距离原本位置的曼哈顿距离的和
8 2 3
4 5 6
7 1
其中第二个估价函数更加好，应为对于估价函数来说每一个状态都对应这一个估价函数值，那么相当于你把所有的状态散列在了这个函数的值域当中，首先第一个函数的值域较小，第二个函数的值域较大，散列更加充分，说明在第一个函数那里状态A和状态B的函数值相等，表示提供了相等的信息量，而在第二个函数的时候，A比B的信息量可能更高。也就是对于同一个估价函数值来说，里面包含的状态中最后解的差异的个数越小越好。
上代码，如果上面那一段话不懂的话可能就是我表述不太好。。。。。
我这里用十进制进行了压缩，有点开脑洞。。也有人用康托展开进行散列，个人感觉也不错。
#include<cstdio>
#include<map>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
struct node{
int s, idx;
string seq;
node(){}
node(int ss, int iidx, string sseq){
s = ss, seq = sseq, idx = iidx;
}
};
int pp[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
map<int, string> ans;
string put[4] = {"d","u","r","l"};
int dir[9][4] = {{-1,3,-1,1},{-1,4,0,2},{-1,5,1,-1},{0,6,-1,4},{1,7,3,5},{2,8,4,-1},{3,-1,-1,7},{4,-1,6,8},{5,-1,7,-1}};
int getA(int s, int idx){
return s / pp[idx] % 10;
}
int change(int s, int a, int b){
a = 8 - a;
b = 8 - b;
int tem = getA(s, a);
s -= tem * pp[a];
s += getA(s, b) * pp[a];
s -= getA(s, b) * pp[b];
s += tem * pp[b];
return s;
}
void bfs(){
int i, j, k;
queue<node> mq;
mq.push(node(123456789, 8, ""));
ans[123456789] = "YES";
while(!mq.empty()){
node s = mq.front();
//cout << s.s << " " << s.idx << " " << s.seq << endl;
mq.pop();
for(i = 0; i < 4; i++){
int ss = s.s;
int ii = s.idx;
string qq = s.seq;
qq += put[i];
int tem = dir[ii][i];
if(tem == -1) continue;
ss = change(ss, tem, ii);
if(ans[ss] == ""){
ans[ss] = qq;
mq.push(node(ss, tem, qq));
}
}
}
}
char ac[100];
int main(){
int i, j, k;
// freopen("1.out", "w", stdout);
//freopen("1.in", "r", stdin);
bfs();
/*for(map<int, string>::iterator it = ans.begin(); it != ans.end(); it++){
cout << it->first << " " << it->second << endl;
}*/
while(gets(ac)){
int s = 0, tot = 0;
for(i = 0; tot < 9; i++){
if(ac[i] >= '1' && ac[i] <= '8'){
s = s * 10 + ac[i] - '0';
tot++;
}
if(ac[i] == 'x'){
s = s * 10 + 9;
tot++;
}
}
if(ans[s] == "YES"){
puts("");
}
else if(ans[s] == ""){
puts("unsolvable");
}
else{
string tem = ans[s];
for(i = tem.length() - 1; i >= 0; i--){
printf("%c", tem[i]);
}
printf("\n");
}
}
return 0;
}