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*是真正优秀的算法。这不仅体现在它的运行时间上，而是说这种算法是最贴近人类行为的。作为人类，我们在解决问题中面临多种方式时，一定会略作估计并选取最优的方式进行尝试。可能这也是启发式算法被广泛运用到人工智能里的原因，毕竟我们人类定义的人工智能就是与人类智能所相似的机器。