谨以此文向人工智能先驱，\(A\)*算法发明者致敬
推，而本文更多是粗略理解和习题吧。
\(A\)*算法是什么？它是启发式搜索的一种，即广度搜索算法\(bfs\)加上估价函数。
而\(IDA\)*则是另一种类似的启发式搜索，是迭代加深\(dfs\)加上估价函数。
迭代加深搜索是什么？就是每次限制\(dfs\)的深度进行搜索。
然后我们来讨论该算法的核心部分：估价函数
估价函数假设用\(h(x)\)表示，到达目前状态的代价用\(g(x)\)表示，那么估计的完成代价为\(f(x)=g(x)+h(x)\)。如果\(f(x)\)大于题目所需，那么可以进行剪枝。
需要注意的是，\(h(x)\)必须小于等于实际最优代价，满足此条件下越接近实际代价该估价函数越优。
一道例题：
对于一种状态，最佳的方案（运气最好时）是每次都能使一个骑士到达预定位置，最后一次能使一个骑士和一个空格到达预定位置，所以估价函数\(h(x)=\)棋盘上与目标状态不同的位置数\(+1\)。
然后搜索，注意每次改变空格的位置即可。
提供一份\(IDA\)*的代码
#includeusing namespace std;const int dx[]={-2,-2,-1,-1,1,1,2,2}, dy[]={-1,1,-2,2,-2,2,-1,1};const int tar[5][5]={ {2, 2, 2, 2, 2}, {1, 2, 2, 2, 2}, {1, 1, 0, 2, 2}, {1, 1, 1, 1, 2}, {1, 1, 1, 1, 1}};int sta[5][5];inline int read(){ int x=0,f=1;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0'; return x*f;}int evoluate(){ int res=0; for (int i=0; i<5; i++) for (int j=0; j<5; j++) if (tar[i][j]^sta[i][j]) res++; return res;}bool IDA(int x, int y, int dep, int maxdep){ int evo=evoluate(); if (dep+evo>maxdep+1) return false; if (!evo) return true; for (int i=0; i<8; i++) { int nx=x+dx[i], ny=y+dy[i]; if (nx>=0 && nx<5 && ny>=0 && ny<5) { swap(sta[x][y], sta[nx][ny]); if (IDA(nx, ny, dep+1, maxdep)) return true; swap(sta[x][y], sta[nx][ny]); } } return false;}int main(){ int T=read(); while (T--) { char s[5][5]; int X, Y; for (int i=0; i<5; i++) scanf("%s", s[i]); for (int i=0; i<5; i++) for (int j=0; j<5; j++) { char c=s[i][j]; if (c=='0') sta[i][j]=1; if (c=='1') sta[i][j]=2; if (c=='*') X=i, Y=j, sta[i][j]=0; } int ans=-1; for (int i=1; i<=15; i++) if (IDA(X, Y, 0, i)) {ans=i; break;} printf("%d\n", ans); } return 0;}
一道类似的题：
本题可以用\(IDA\)*和双向\(bfs\)通过，甚至\(map\)去重的\(bfs\)也可通过。作为一道练手题还是不错的。
代码不放了，和上题大体一致(我才不会说是我懒）
再看一个\(A\)*经典应用：
（洛谷的模板题\(A\)*只能得到\(92pts\)，标算是可持久化可并堆，所以这里就当是理性愉悦了吧）
说一下\(A\)*算法的思路。
先在反向图中\(Dijkstra\)得到估价函数\(dis(i)\)。
然后\(bfs\)，用堆维护一下目前距离\(f(i)+dis(i)\)就可以了。
有一个没有什么用的优化，遍历每个点的次数不会超过\(\frac{w}{dis(1)}\)，可以剪枝。
\(92pts\)代码
#includeusing namespace std;const int N=5005, M=200005;struct node{int to, nxt; double w;}edge1[M], edge2[M];struct Node{int id; double w;};struct NODE{int id; double w, f;};bool operator < (Node a, Node b){return a.w>b.w;}bool operator < (NODE a, NODE b){return a.f>b.f;}int head1[N], head2[N], vis[N], cnt[N], cnt1, cnt2, n, m, ans;double W, dis[N];inline int read(){ int x=0,f=1;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0'; return x*f;}void add(int u, int v, double w){ edge1[++cnt1]=(node){v, head1[u], w}; head1[u]=cnt1; edge2[++cnt2]=(node){u, head2[v], w}; head2[v]=cnt2;}void Dijkstra(int S){ priority_queue q; q.push((Node){S, 0}); for (int i=1; i<=S; i++) dis[i]=1e12; dis[S]=0.0; memset(vis, 0, sizeof(vis)); while (!q.empty()) { int u=q.top().id; q.pop(); if (vis[u]) continue; vis[u]=1; for (int i=head2[u]; i; i=edge2[i].nxt) { int v=edge2[i].to; double w=edge2[i].w; if (dis[v]>dis[u]+w) { dis[v]=dis[u]+w; q.push((Node){v, dis[v]}); } } }}void A_star(int S, int Max_cnt){ priority_queue q; q.push((NODE){S, 0, 0}); while (!q.empty()) { NODE u=q.top(); q.pop(); int x=u.id; if (u.w>W) return; cnt[x]++; if (x==n) {ans++; W-=u.f; continue;} if (cnt[x]>Max_cnt) continue; for (int i=head1[x]; i; i=edge1[i].nxt) { int v=edge1[i].to; q.push((NODE){v, u.w+edge1[i].w, u.w+edge1[i].w+dis[v]}); } }}int main(){ n=read(); m=read(); scanf("%lf", &W); for (int i=1; i<=m; i++) { int u=read(), v=read(); double w; scanf("%lf", &w); add(u, v, w); } Dijkstra(n); A_star(1, W/dis[1]); printf("%d\n", ans); return 0;}