UVA439 骑士的移动

UVA439 骑士的移动

之所以这道题我要写题解,是因为解题的过程中我采用了多种方法(不严谨的说,基本写完了搜索里的所有技巧)——BFS,IDA* ,A*,双向DFS。

这个过程很值得品味参考,于我来说也是一次不可多得的学习。

BFS

这道题的BFS思路是比较显然的,代码实现上也不算特别难。

#include<bits/stdc++.h>

int max_dep;
int f[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
}s,t;


namespace WalkerV {
	void Init() {
		max_dep=0;
		memset(f,0,sizeof(f));
		return;
	}

	double Estimate_Function(int x1,int y1,int x2,int y2) {
		return std::ceil((std::abs(x1-x2)+std::abs(y1-y2))/3.0);
	}

	bool IDDFS(int x,int y,int dep) {
		if(dep==max_dep) {
			if(x==t.x&&y==t.y) {
				f[x][y]=dep;
				return true;
			}
			else {
				return false;
			}
		}
		//printf("x:%d y:%d g(x):%d f(x):%.1f\n",x,y,dep,Estimate_Function(x,y,t.x,t.y));
		for(int i=1;i<=8;i++) {
			if(x+dx[i]>=1&&x+dx[i]<=8&&y+dy[i]>=1&&y+dy[i]<=8&&!f[x+dx[i]][y+dy[i]]) {
				//printf("move to %d %d, g:%d f:%.1f max_dep:%d\n",x+dx[i],y+dy[i],dep+1,Estimate_Function(x+dx[i],y+dy[i],t.x,t.y),max_dep);
				if(dep+1+Estimate_Function(x+dx[i],y+dy[i],t.x,t.y)>max_dep) { //g(x):dep+1 f(x):ceil(M_Dis/3)
					//printf("cut\n");
					continue;
				}
				if(IDDFS(x+dx[i],y+dy[i],dep+1)) {
					return true;
				}
			}
		}
		return false;
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘};
		while(!IDDFS(s.x,s.y,0)) {
			memset(f,0,sizeof(f));
			max_dep++;
			//printf("max_dep:%d\n",max_dep);
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.\n",op,ed,f[t.x][t.y]);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}

}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

IDA*

然后便是IDA*。

如果你问我为什么不先写A*,因为这份代码的重点是迭代加深,也就是ID(Iterative Deepening)。但单打一份迭代加深的DFS意义不大,所以就选择用IDA*。而且从各种角度来说,IDA*都比A*要优秀一些。

但是这份代码应该说是几份代码我调得最痛苦的一份(大概前前后后修了三四个小时左右),最后的关键错误还是落在了估价函数上。

有必要说一下估价函数的设计:因为是马在棋盘上的移动,所以考虑曼哈顿距离。我们知道马每次移动的曼和顿距离为$3$,所以乐观估计应当是当前位置到终点的曼哈顿距离除以$3$并向上取整。

#include<bits/stdc++.h>

int max_dep;
int f[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
}s,t;


namespace WalkerV {
	void Init() {
		max_dep=0;
		memset(f,0,sizeof(f));
		return;
	}

	double Estimate_Function(int x1,int y1,int x2,int y2) {
		return std::ceil((std::abs(x1-x2)+std::abs(y1-y2))/3.0);
	}

	bool IDDFS(int x,int y,int dep) {
		if(dep==max_dep) {
			if(x==t.x&&y==t.y) {
				f[x][y]=dep;
				return true;
			}
			else {
				return false;
			}
		}
		//printf("x:%d y:%d g(x):%d f(x):%.1f\n",x,y,dep,Estimate_Function(x,y,t.x,t.y));
		for(int i=1;i<=8;i++) {
			if(x+dx[i]>=1&&x+dx[i]<=8&&y+dy[i]>=1&&y+dy[i]<=8&&!f[x+dx[i]][y+dy[i]]) {
				//printf("move to %d %d, g:%d f:%.1f max_dep:%d\n",x+dx[i],y+dy[i],dep+1,Estimate_Function(x+dx[i],y+dy[i],t.x,t.y),max_dep);
				if(dep+1+Estimate_Function(x+dx[i],y+dy[i],t.x,t.y)>max_dep) { //g(x):dep+1 f(x):ceil(M_Dis/3)
					//printf("cut\n");
					continue;
				}
				if(IDDFS(x+dx[i],y+dy[i],dep+1)) {
					return true;
				}
			}
		}
		return false;
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘};
		while(!IDDFS(s.x,s.y,0)) {
			memset(f,0,sizeof(f));
			max_dep++;
			//printf("max_dep:%d\n",max_dep);
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.\n",op,ed,f[t.x][t.y]);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}

}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

A*

在有了BFS和IDA*的基础上,A*就显得非常容易了。

估价函数的设计与IDA*是一致的。

#include<bits/stdc++.h>

int f[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
	double est;
	friend bool operator < (node a,node b) {
		return a.est>b.est;
	}
}s,t;

namespace WalkerV {
	void Init() {
		memset(f,0,sizeof(f));
		return;
	}
	
	double Estimate_Function(int x,int y) {
		return std::ceil((std::abs(x-t.x)+std::abs(y-t.y))/3.0);
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘,0},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘,0};
		s.est=Estimate_Function(s.x,s.y);
		std::priority_queue<node> q;
		q.push(s),f[s.x][s.y]=0;
		while(q.size()) {
			node k=q.top();
			q.pop();
			if(k.x==t.x&&k.y==t.y) {
				return;
			}
			for(int i=1;i<=8;i++) {
				if(k.x+dx[i]>=1&&k.x+dx[i]<=8&&k.y+dy[i]>=1&&k.y+dy[i]<=8&&!f[k.x+dx[i]][k.y+dy[i]]) {
					f[k.x+dx[i]][k.y+dy[i]]=f[k.x][k.y]+1;
					q.push((node){k.x+dx[i],k.y+dy[i],f[k.x+dx[i]][k.y+dy[i]]+Estimate_Function(k.x+dx[i],k.y+dy[i])});
				}
			}
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.\n",op,ed,f[t.x][t.y]);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}
}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

双向BFS

对于这题,由于我们已经知道搜索的初态和末态,所以既可以从初态搜到末态,也可以从末态搜到初态。

在此基础上,双向BFS的思路也就呼之欲出了——从初态和末态同时往中间搜索(具体实现应当是正反各搜一轮)。

由于我们使用的是BFS,所以在轮流搜索的时候但凡有一个状态被两边都搜索到了(也就是说第一个被两边都搜索到的状态),那么这个状态到初态和末态的路径和就是答案(正确性显然)。

此外,在代码中需要注意的有如下两点:

  • 末态的初值应赋为$1$,因为在实际的移动中,是需要$1$步才能走到终点的。

  • 起点和终点重合需要特判,不然程序就会处理为需要$2$步才能到(反复横跳一次)。

说句闲话,其实中间两个队列的实现那里,如果用typedef写会更好看一些,但是可读性会大大降低(逃

#include<bits/stdc++.h>

int ans;
int f1[10][10],f2[10][10],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,2,1,-1,-2,-2,-1,1,2};
char op[5],ed[5];

struct node {
	int x,y;
}s,t;

namespace WalkerV {
	void Init() {
		memset(f1,0,sizeof(f1));
		memset(f2,0,sizeof(f2));
		return;
	}

	void Solve() {
		s=(node){op[0]-‘a‘+1,op[1]-‘0‘},t=(node){ed[0]-‘a‘+1,ed[1]-‘0‘};
		if(s.x==t.x&&s.y==t.y) {
			ans=0;
			return;
		}
		std::queue<node> q1,q2;
		q1.push(s),f1[s.x][s.y]=0;
		q2.push(t),f2[t.x][t.y]=1;
		while(q1.size()||q2.size()) {
			bool flag;
			node k;
			if(q1.size()<=q2.size()) { //edit q1
				k=q1.front();
				q1.pop();
				flag=true;
			}
			else { //edit q2
				k=q2.front();
				q2.pop();
				flag=false;
			}
			for(int i=1;i<=8;i++) {
				if(k.x+dx[i]>=1&&k.x+dx[i]<=8&&k.y+dy[i]>=1&&k.y+dy[i]<=8) {
					switch(flag) {
						case true:
							if(f2[k.x+dx[i]][k.y+dy[i]]) {
								ans=f1[k.x][k.y]+f2[k.x+dx[i]][k.y+dy[i]];
								return;
							}
							f1[k.x+dx[i]][k.y+dy[i]]=f1[k.x][k.y]+1;
							q1.push((node){k.x+dx[i],k.y+dy[i]});
							break;
						case false:
							if(f1[k.x+dx[i]][k.y+dy[i]]) {
								ans=f2[k.x][k.y]+f1[k.x+dx[i]][k.y+dy[i]];
								return;
							}
							f2[k.x+dx[i]][k.y+dy[i]]=f2[k.x][k.y]+1;
							q2.push((node){k.x+dx[i],k.y+dy[i]});
							break;
					}				
				}
			}
		}
		return;
	}

	void Print() {
		printf("To get from %s to %s takes %d knight moves.\n",op,ed,ans);
		memset(op,0,sizeof(op));
		memset(ed,0,sizeof(ed));
		return;
	}
}

int main()
{
	while(std::cin>>op>>ed) {
		WalkerV::Init();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}

说点别的

这次这道题码下来,还算是收获颇丰。谁会想到,一个学了两年多OI的人,直到这道题才算是摸透了上面四种算法(包括BFS)。

此外,在写代码的时候,感觉到(ID)A*是真正优秀的算法。这不仅体现在它的运行时间上,而是说这种算法是最贴近人类行为的。作为人类,我们在解决问题中面临多种方式时,一定会略作估计并选取最优的方式进行尝试。可能这也是启发式算法被广泛运用到人工智能里的原因,毕竟我们人类定义的人工智能就是与人类智能所相似的机器。

UVA439 骑士的移动

上一篇:ssm架构里mybatis为什么使用通用mapper


下一篇:HDU 1564 + 证明