【模板】A*

A* 就是给普通的搜索加了一个估价函数 \(\operatorname{f}\)。

定义比较简单：

\(\operatorname{f}(n) = \operatorname{g}(n)+\operatorname{h}(n)\)

其中 \(\operatorname{g}(n)\) 表示当前节点 \(n\) 已经花费的步数，\(\operatorname{h}(n)\) 表示将来需要花费的最小代价（或者说是一个可望而不可及的完美情况所需的步数）。

那么 \(\operatorname{f}(n)\) 表示在现有状态下到达终态最少需要的步数。

例子：\(\textrm{luogu P2324 [SCOI2005]骑士精神}\)

本题估价函数一旦超过 \(15\)，那肯定无了，就不必往下搜了。

这也是一种剪枝吧。

#include <iostream>
char aim[6][6] = {
	{0,0,0,0,0,0},
	{0,1,1,1,1,1},
	{0,0,1,1,1,1},
	{0,0,0,2,1,1},
	{0,0,0,0,0,1},
	{0,0,0,0,0,0},
};
char con[6][6];
int evaluate() {
	int res = 0;
	for(int i = 1;i <= 5;++i) 
		for(int j = 1;j <= 5;++j) 
			if(con[i][j] != aim[i][j]) 
				++res;
	return res;
}
int x_move[8] = {1,1,2,2,-1,-1,-2,-2};
int y_move[8] = {2,-2,1,-1,2,-2,1,-1};
int max_depth;
bool IDA_star(int u_x,int u_y,int depth) {
	int perfect = evaluate();
	if(perfect+depth > max_depth+1) 
		return false;
	if(perfect == 0) 
		return true;
	for(int i = 0;i < 8;++i) {
		int v_x = u_x+x_move[i];
		int v_y = u_y+y_move[i];
		if(v_x < 1||v_x > 5||v_y < 1||v_y > 5) 
			continue;
		std :: swap(con[u_x][u_y],con[v_x][v_y]);
		if(IDA_star(v_x,v_y,depth+1)) {
			std :: swap(con[u_x][u_y],con[v_x][v_y]);
			return true;
		}
		std :: swap(con[u_x][u_y],con[v_x][v_y]);
	}
	return false;
}
int T, ans;
int u_x, u_y;
int main() {
	scanf("%d",&T);
	while(T--) {
		for(int i = 1;i <= 5;++i) {
			scanf("%s",con[i]+1);
			for(int j = 1;j <= 5;++j) 
				if(con[i][j] >= '0') 
					con[i][j] -= '0';
				else {
					con[i][j] = 2;
					u_x = i, u_y = j;
				}
		}
		int begin = evaluate();
		if(begin > 15) {
			printf("-1\n");
			continue; 
		}
		ans = -1;
		for(int i = begin-1;i <= 15;++i) {
			max_depth = i;
			if(IDA_star(u_x,u_y,0)) {
				ans = i;
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

还有一个经典应用事 k短路。

不过时间是假的，因为有更优秀的可并堆做法。