A*算法

例题：洛谷P1379 八数码难题

给定初始状态和终止状态，要求给出最少的移动次数。我们考虑利用搜索算法来进行解决。考虑通过移动空格0来进行记录一种搜索情况。不过是dfs?还是bfs?这里的搜索域很深但是答案的搜索深度却不深。可以采用A*算法。

A*算法对搜索算法的一种优化，我们平时采取进行答案搜索，会采取一个或多个限制条件来对递归搜索函数进行剪枝，而在A*算法中则采取了评估函数来进行是否剪枝的判断。

1.迭代加深搜索

每次限制一个搜索深度，让搜索函数在这个深度里面尽可能的遍历所有情况。这里就是限制移动步数，比如可以1步完成，2步及以上的搜索就没必要进行了。

2.评估函数

f(n)=g(n)+h(n)

其中f(n)是节点的估价函数，g(n)是现在的实际步数，h(n)是对未来步数的最完美估价。

简单来说就是，你现在走了a步，然后你离完成目标最少还要走b步，那么你现在的f(n)=a+b。

bool test(int step)//step表示你现在已经走的步数 
{
	int num=0;//num表示你现在的棋盘有多少个的数字与答案的不一样，每有一个数字不一样说明你至少要花一步去修正。所以f(n)=g(n)+h(n)=step+num; 
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			if(a[i][j]!=ans[i][j])
			{
				num++;//统计 
				if(num+step>tot)//tot表示搜索深度，f(n)大于搜索深度了，就说明这种情况已经不可能在搜索深度里面完成了，直接返回false 
				return false;
			}
		}
	return true;
}

 

代码参考：

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#include<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#define ll long long
#define lowbit(x)  (x)&(-x)
using namespace std;
const ll N=1000000+10;
int ans[4][4]=
{{0,0,0,0},
 {0,1,2,3},
 {0,8,0,4},
 {0,7,6,5}};//记录答案棋盘 
int a[4][4],k[][2]={{},{0,1},{-1,0},{1,0},{0,-1}},tot,judge=0,sx,sy;//k表示移动的方向，tot表示搜索深度，sx,sy表示棋盘开始时空格0的起始位置 
bool check()//判断当前棋盘是否与答案棋盘一样。 
{
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			if(a[i][j]!=ans[i][j])
				return false;
		}
		return true;
}
bool test(int step)//step表示你现在已经走的步数 
{
	int num=0;//num表示你现在的棋盘有多少个的数字与答案的不一样，每有一个数字不一样说明你至少要花一步去修正。所以f(n)=g(n)+h(n)=step+num; 
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			if(a[i][j]!=ans[i][j])
			{
				num++;//统计 
				if(num+step>tot)//tot表示搜索深度，f(n)大于搜索深度了，就说明这种情况已经不可能在搜索深度里面完成了，直接返回false 
				return false;
			}
		}
	return true;
}
void A_star(int x,int y,int step,int pre)//A*算法 
{
	if(step==tot)//达到搜索深度返回 
	{
		if(check())
		judge=1;//记录已经搜索到了答案 
		return;
	}
	if(judge)//有答案了就直接返回 
	return;
	for(int i=1;i<=4;i++)
	{
		int dx=x+k[i][0];//移动 
		int dy=y+k[i][1];
		if(dx<1||dx>3||dy<1||dy>3||pre+i==5)continue;//空格移出去了，pre+i==5说明空格重复走了，比如上一步是向上的，然后这一步向下了。或者前一步是向左，这一步是向右的 
		swap(a[x][y],a[dx][dy]);
		if(test(step)&&!judge)A_star(dx,dy,step+1,i);
		swap(a[x][y],a[dx][dy]);
	}
}
int main()
{
	//ios::sync_with_stdio(false);
	#ifndef ONLINE_JUDGE
    //freopen("129.txt","r",stdin);
	#endif // ONLINE_JUDGE
	for(int i=0;i<9;i++)//读取数据 
	{
		char c;
		scanf("%c",&c);
		a[i/3+1][i%3+1]=(c-'0');
		if(a[i/3+1][i%3+1]==0)
		{
			sx=i/3+1;
			sy=i%3+1;
		}
	}
	if(test(0))//特判是否不用移动 
	{
		printf("%d",0);
		return 0;
	}
	while(++tot)//每次搜索深度加1.(和bfs有点像) 
	{
		A_star(sx,sy,0,-1);
		if(judge)
		{
		printf("%d",tot);
		break;	
		}
		
	}
 	return 0;
}

练习参考：

洛谷P2324 [SCOI2005]骑士精神

洛谷P4467 [SCOI2007]k短路