举个栗子:用A*做的八数码难题
#include<map> #include<queue> #include<iostream> #include<algorithm> using namespace std; int dx[]={-1,0,0,1},dy[]={0,-1,1,0}; int final[]={-1,0,1,2,5,8,7,6,3}; struct node { int state,g,h; node(int _state,int _g) { state=_state; g=_g; h=0; int tmp=state; for(int i=8;i>=0;i--) { int a=tmp%10;tmp/=10; if(a!=0)h+=abs((i/3)-(final[a]/3))+abs((i%3)-(final[a]%3)); } } }; bool operator<(node x,node y) { return x.g+x.h>y.g+y.h; } priority_queue<node>q; map<int,bool>vis; int main() { int n; cin>>n; q.push(node(n,0)); vis[n]=1; while(!q.empty()) { node u=q.top(); int c[3][3],f=0,g=0,n=u.state;q.pop(); if(u.state==123804765) { cout<<u.g<<endl; return 0; } for(int i=2;i>=0;i--) for(int j=2;j>=0;j--) { c[i][j]=n%10,n/=10; if(!c[i][j])f=i,g=j; } for(int i=0;i<4;i++) { int 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(int i=0;i<3;i++) for(int j=0;j<3;j++) ns=ns*10+c[i][j]; if(!vis.count(ns)) { vis[ns]=1; q.push(node(ns,u.g+1)); } swap(c[nx][ny],c[f][g]); } } }这是bfs做法
这是A*做法
很明显，A*比bfs快多了
值得注意的是，A*只能在有解的情况下使用
IDA在进行IDFS的时候，我们也可以用A进行搜索
如果在当前深度限制下搜到了结束状态，我们就可以直接输出答案
代码大体框架:
//1代表墙，0代表空地，2代表终点 int G[maxn][maxn]; int n, m; int endx, endy; int maxd; const int dx[4] = { -1, 1, 0, 0 }; const int dy[4] = { 0, 0, -1, 1 }; namespace ida { bool dfs(int x, int y, int d); inline int h(int x, int y); bool ida_star(int x, int y, int d) { if (d == maxd) //是否搜到答案 { if (G[x][y] == 2) return true; return false; } int f = h(x, y) + d; //评估函数 if (f > maxd) //maxd为最大深度 return false; //尝试向左，向右,向上，向下走 for (int i = 0; i < 4; i++) { int next_x = x + dx[i]; int next_y = y + dy[i]; if (next_x > n || next_x < 1 || next_y > m || next_y < 1 || G[next_x][next_y] == 1) continue; if (ida_star(next_x, next_y, d + 1)) return true; } return false; } inline int h(int x, int y) { return abs(x - endx) + abs(y - endy); } }