By

启发式搜索

A*算法：优先走估值函数的分支

估值函数可以为 \(f^*(x)=g(x)+h^*(x)\) \(g(x)\)表示从起点到 \(x\) 的代价，\(h(x)\)表示 \(x\) 到终点的代价的估计值。

当 \(h(x)=0\) 时，A*算法就退化成了普通的BFS。

当 \(h^*(x)\) 越大，算法效率越高。

但 \(h^*(x)\) 的值超过了实际到达终点的代价 \(h(x)\)，就可能得到错误的答案。

P5507 机关 - 洛谷

题意：一个机关，上面一共有12个旋钮，每个旋钮有4个状态，将旋钮的状态用数字\(1\)到\(4\)表示

每个旋钮只能向一个方向旋转（状态：1->2->3->4->1），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出）

当所有旋钮都旋转到状态1时，机关就打开了

请输出打开机关的最少步数和依次旋转的旋钮编号。

题解：妙啊，12个数，每个数有4个状态怎么存储？4个状态可以为0,1,2,3用2位二进制存储，12个数就是24位二进制也就是2\^24次方的大小，众所周知int是2\^31，所以用int类型存储没问题，用桶也可以开这么大，或者用map也没问题。

每个状态使用位运算来拆解状态、更改状态、分解状态。

运用结构体的构造函数，直接求出 \(h(x)\)函数，至于 \(g(x)\)，每次更新即可。

输出操作步骤，可以采用链式前向星的思想，存储上一步，然后递归输出即可。存储下一步也没问题，可以直接循环输出或者递归。

至于 \(h(x)\) 所占比例，有的题解说每次两个点变，所以要除2，但其实没关系。

关键的还有 \(h(x)\) 求解时，\((4-((s>>(i*2))\&3))\&3\) ，去掉后面 \(\&3\) 会超时，因为估值函数不会正确的求解，当状态为 0 时，也就是已经到达目标状态，就会出现 \(h+=4-0\) 的情况，但是加上 \(\&3\) 后，当状态为 0 时，就会出现 \(h+=0\) 的情况，就不会破坏估值函数的正确性。不加 \(\&3\) 也可以，特判状态 0 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){
	char op = getchar(); int x = 0, f = 1;
	while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
	while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
	return x * f;
}
const int N=1<<24;
int g[N],nxt[12][4];
bool vis[N];//记录状态是否出现过
int pre[N],but[N];//从哪个状态过来，用的什么按钮
struct node{
	int st;//状态
	double f;//状态对应估价函数值
	node(int s){//构造函数
		double h=0;
		st=s;
		for(int i=0;i<12;i++)
			h+=(4-((s>>(i*2))&3))&3;//计算第i旋钮状态到0需要几次
		h/=2;//都可以
		f=h+g[s];//计算估值函数
	}
	friend bool operator <(node y,node x){
		return x.f<y.f;//估值函数小的优先
	}
};
int stzt;
void Astar(){
	priority_queue<node> q;
	q.push(node(stzt)),vis[stzt]=true;
	while(!q.empty()){
		int st=q.top().st;//状态
		q.pop();
		if(st==0) break;//等同于全是1
		for(int i=0;i<12;i++){
			int sti=(st>>(i*2))&3;//第i旋钮对应状态
			int di=nxt[i][sti];//对应旋钮对应状态相连的旋钮
			int stdi=(st>>(di*2))&3;//相连旋钮对应状态
			//将第i旋钮对应地方使用^清空,再放入扭一次的状态
			int dst=st^(sti<<(i*2))^(((sti+1)&3)<<(i*2));
			//将相连旋钮对应地方使用^清空,再放入扭一次的状态
			dst=dst^(stdi<<(di*2))^(((stdi+1)&3)<<(di*2));
			if(!vis[dst]){//如果未出现过
				g[dst]=g[st]+1;//次数+1
				vis[dst]=true;//记录出现
				pre[dst]=st;//记录从哪个状态转移而来
				but[dst]=i+1;//使用的是第几个旋钮
				q.push(node(dst));
			}
		}
	}
}
void output(int x){
	if(x==stzt) return ;
	output(pre[x]);
	printf("%d ",but[x]);
}
int main(){
	for(int i=0,x;i<12;i++){
		x=read()-1;
		stzt|=(x<<(i*2));//运用二进制存储12个旋钮的状态
		for(int j=0;j<4;j++){
			nxt[i][j]=read()-1;
		}
	}
	Astar();
	printf("%d\n",g[0]);
	output(0);
	return 0;
}

IDA*算法：启发式迭代加深搜索=A*思想+迭代加深搜索IDDFS

使用迭代加深搜索所枚举的搜索上界 dep 即为总的代价 \(f(x)\) 的最大值；

而从起点到状态 x 的代价 \(g(x)\)，即走的步数恰好对应着搜索层数。

而只有 \(f^*(x)=g(x)+h^*(x)≤dep\) 时，该状态才会被本轮搜索拓展。

P2324 骑士精神

题意：5*5的棋盘，给定初始状态和目标状态，只能安装规则移动，最少几步？15步内不行输出-1。

题解：从本状态到终点代价的估计值 \(h^*(x)\) 可以设计为尚未归位的棋子数量，因为每个尚未归位的棋子一定得让开，走至少一步，相当保守的估计。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int m[7][7],flag,dep,sx,sy;
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
string goa="1111101111002110000100000";//目标状态
int h(){//到目标状态的估值
	int cnt=0;
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			if(m[i][j]!=goa[i*5+j]-'0') cnt++;
	return cnt;
}
void dfs(int g,int x,int y){//第g层，起点为(x,y)
	if(g==dep){
		if(!h()) flag=1;//已经到达目标状态
		return ;
	}
	for(int i=0;i<8;i++){//8个方向
		int xx=x+dx[i],yy=y+dy[i];//下一步的位置
		if(xx<0||xx>=5||yy<0||yy>=5) continue;
		swap(m[x][y],m[xx][yy]);//记录现场
		if(g+h()<=dep)//启发式搜索关键
			dfs(g+1,xx,yy);
		swap(m[x][y],m[xx][yy]);//恢复现场
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		flag=0;
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				char c;
				cin>>c;
				if(c=='*')//记录起点
					m[i][j]=2,sx=i,sy=j;
				else m[i][j]=c-'0';
			}
		}
		for(dep=0;dep<=15;dep++){//迭代加深
			dfs(0,sx,sy);
			if(flag){//找到了
				cout<<dep<<"\n";
				break;
			}
		}
		if(!flag) cout<<"-1\n";
	}
	return 0;
}

总结：两种算法的比较

  A*算法 IDA*算法
概括 在BFS的基础加上估价函数 在IDDFS基础加上估价函数
应用 适用于总体BFS的题目 适用于需要迭代加深类的题目