首先我们想要学习 A star 就得先了解它的前置芝士。
前置芝士
BFS
普通 BFS
BFS 中文称广度优先搜索，是对于每个已经扩张的点继续能扩张就扩张，如：
S123456
1234567
2345678
3456789
456789E
图中 
代表起点，
代表终点，数字代表从 到这最少要走多少步。
很容易写出代码，
code：
void bfs(int sx,int sy){
memset(b,false,sizeof(b)),memset(a,255,sizeof(a)),a[sx][sy]=0;
q[1][0]=sx,q[1][1]=sy;
while(front<=rear){
int x=q[front][0],y=q[front][1];
++front;
for(int i=0;i<4;i++){
int xx=x+D[i][0],yy=y+D[i][1];
if(xx<1||xx>n||yy<1||yy>m||s[xx][yy]=='#')
continue;
if(a[xx][yy]==-1)
a[xx][yy]=a[x][y]+1,q[++rear][0]=xx,q[rear][1]=yy;
}
}
}
其中 
代表未扩张队列，
用来记录答案，
代表方向的预处理，
代表地图。
双向 BFS
其实就是从刚开始将重点也遍历进去，速度快一倍！
code：
只要在初始化时加上：
q[2][0]=ex,q[2][1]=ey;//记得处理 front 和 rear
即可。
多元 BFS
就是有多个起点和终点，在预处理时加进去即可。
DFS
DFS 中文称深度优先搜索，是对于每个已经扩张的点继续扩张一个点，不行了就回溯，但是它不能用来求最短路径。
code：
void dfs(int x,int cnt){
a[x]=cnt;
for(auto i:edge[x])
dfs(i,++cnt);
}
A star
它可以说是 BFS 的进化版。
它对于求解答案增加了了一个估价函数：
它一般等于：
欧氏距离，曼哈顿距离，切比雪夫距离。
较少用我搜到的这些距离闵可夫斯基距离、标准化欧氏距离、马氏距离、夹角余弦、汉明距离、杰卡德距离 & 杰卡德相似系数、相关系数 & 相关距离、信息熵（这都是啥玩儿）。
让后我们采用一种贪心的思想：
还要走多远？你迷路是肯定会这样想。
于是他也这样想，只不过你是凭直觉，它是凭数据，还要走多远用估价函数来估计，但是这种估计几乎很准，除了这种情况：
…..
.###.
..S#.
.###.
….E
只不过这也不会卡住脖子，因为一边运行完后还有其他地方。
code：
priority_queue<pair<pair<int,int>,int>>q;
void Astar(int sx,int sy){
memset(b,false,sizeof(b)),memset(a,255,sizeof(a)),a[sx][sy]=0;
q.push(make_pair(make_pair(sx,sy),G(sx,sy)));
while(front<=rear){
int x=q.top().first,y=q.top().second;
q.pop();
for(int i=0;i<4;i++){
int xx=x+D[i][0],yy=y+D[i][1];
if(xx<1||xx>n||yy<1||yy>m||s[xx][yy]=='#')
continue;
if(a[xx][yy]==-1)
a[xx][yy]=a[x][y]+1,q.push(make_pair(make_pair(xx,yy),G(xx,yy)));
}
}
}
很好打吧。
题目
可怜的 A star 算法只有几道题。
P1379
P1491
P2324
P2534
这几道题差不多都和模板差不多，这里我只讲 P1379。
P1379
他其实只需要你以八数码每个数字距离正确位置的距离为估价函数来求。
code：
cin>>n,q.push(n),m[n]=0;
while(!q.empty()){
u=q.front(),f=0,g=0,t=u,q.pop();
if(u==123804765)
break;
for(ll i=2;i>=0;i–)
for(ll j=2;j>=0;j–){
c[i][j]=t%10,t/=10;
if(!c[i][j])
f=i,g=j;
}
for(ll i=0;i<4;i++){
nx=f+dx[i],ny=g+dy[i],ns=0;
if(nx<0||ny<0||nx>2||ny>2)
continue;
swap(c[nx][ny],c[f][g]);
for(ll i=0;i<3;i++)
for(ll j=0;j<3;j++)
ns=ns*10+c[i][j];
if(!m.count(ns))
m[ns]=m[u]+1,q.push(ns);
swap(c[nx][ny],c[f][g]);
}
}
cout<<m[123804765];//这里我是把他的状态按从上到下，从左到右的顺序记录的
后记
A star 这玩意儿不咋难，你只要知道它的状态即可是啥，估价函数怎么求一切就容易了。
上面那几道题也是关于这个的考点。
这个可以看作 BFS 的优化吧。
