欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

A*算法在OI中的应用

程序员文章站 2022-12-10 22:34:42
1.A*算法 我们普通的搜索算法往往复杂度都是指数级,OI中这样的复杂度无法满足我们的要求。这时我们一般都会进行一些剪枝优化,但在有些题目中却可以有更加巧妙的方法—&...
1.A*算法

我们普通的搜索算法往往复杂度都是指数级,OI中这样的复杂度无法满足我们的要求。这时我们一般都会进行一些剪枝优化,但在有些题目中却可以有更加巧妙的方法——A*算法。

A*算法作为一种基础的启发式搜索,它不同于DFS和BFS将所有情况进行遍历,它能从所有情况中选出较优的再进行遍历。因此,它让搜索从“瞎搜”转化到了“有目标的搜索”。那么如何确定较优的情况便是关键所在。

A*算法中核心是一个估值函数,我们可以通过它来得到每种情况的优劣。用公式表示便是:

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

当中g(n)是从初始状态到当前状态是实际代价,可以通过计算得出,h(n)便是估值函数,估计当前状态到结束状态的代价,f(n)便是估计出来的总代价。由此我们将每一个状态估价,我们便可以选出f(n)更优的状态进行遍历。不难看出,这个估值函数可以有不同的选择,同时也直接影响到了算法的效率,因此这个函数的选取是极为重要的。

2.h(n)的选取

下面所说的h(n)即为估值函数,d(n)为实际值(当前状态到结束状态的实际代价)

如果h(n)

如果h(n)=d(n),估算代价等于实际值,估计结果等于实际结果,因此搜索按照实际的最优情况经行,效率最高。

如果h(n)>d(n),估算代价大于实际值,估计结果更优的较少,因此搜索的范围更小,效率高,但是不一定得出最优解。

在OI中,为了保证答案最优,我们往往选择h(n)$<$d(n)。

我们看两个例子:

第一个是SCOI2005 骑士精神(BZOJ 1085),这道题目似乎没有其他的技巧,只能进行搜索,数据范围也确实不大。但是普通的搜索肯定会超时的,于是很自然的想到了A*算法。这道题中h(n)不难想出,就是当前状态有多少个需要移动的骑士。虽然有可能h(n)较小实际值却偏大,但我们这里是偏优的估计,即是h(n)$<$d(n),所以可以保证答案的准确性。估值函数代码如下:

int h()

{

int sum=0;

for(int i=1; i<=5; i++)

for(int j=1; j<=5; j++)

if(map[i][j]!=aim[i][j]){ //map为当前状态,aim为目标状态

sum++;

}

return sum;

}

第二个是比较有名的八数码问题(不清楚的可以百度一下),这道题一般容易想到搜索。这道题目h(n)选取有两种方法,第一种便是同上一题相似,h(n)是有多少个数字需要移动。但还有一种更为巧妙(当然也更精确)的选取方式:便是每一个数字到目标位置的曼哈顿距离(就是到目标位置要走多少个格子)之和。不难看出,这样的估计也是偏优的。估值函数代码如下:

const int aimx[9]={2,1,1,1,2,3,3,3,2},aimy[9]={2,1,2,3,3,3,2,1,1};

//aimx[i]表示目标状态数字i的纵坐标,aimy表示横坐标

int h()

{

int sum=0;

int nx[9],ny[9]; //nx[i]表示数字i的纵坐标,ny表示横坐标

for(int i=1; i<=3; i++)

for(int j=1; j<=3; j++){

nx[map[i][j]]=i; //map为当前状态

ny[map[i][j]]=j;

}

for(int i=1; i<9; i++)

sum+=abs(nx[i]-aimx[i])+abs(ny[i]-aimy[i]); //到目标位置曼哈顿距离

return sum;

}

现在我们对估值函数的选取有了一定的了解,写题时灵活准确的选取h(n)是关键。

3.IDA*算法

A* 算法在实现过程中往往是在获得的子节点中选取f(n)最小的子节点进行扩展(一般用堆或优先队列选出f(n)最小的子节点),通过维护关闭列表和开放列表,对扩展出来的节点进行检测(判重,为提高效率有时使用hash)。详细的实现步骤可以参考其他博客,这里偏向于思想和应用层面。我们可以看出,普通A*将大部分时间消耗在了将f(n)排序和情况判重上,同时类似于BFS将状态储存到节点中,这也往往需要很大的空间。

而IDA* 综合了A* 算法和迭代加深搜索(一种DFS),有着空间消耗少的特点。同时不需要储存节点,也不用将状态排序和判重,在时间和空间上都优于普通的A* 算法。它是在f(n)>预定的最大搜索深度时进行剪枝。这样的代码难度往往会小很多,在OI中IDA* 算法比A* 算法实用很多。

举个例子,还是上一题的八数码问题,IDA*的代码就很简洁:(部分核心代码)

void dfs(int x, int y, int g) //g便是公式中g(n)

{

if(g+h()>ans || flag) return; //g+h()便是f(n),ans为预定最大搜索深度

if(h()==0) {flag=1; return;} //h(n)==0时便是与目标状态完全相同

for(int i=0; i<4; i++) {

int rx=x+dx[i];

int ry=y+dy[i]; //遍历四个方向

if(rx<1 || ry<1 || rx>3 || ry>3) continue; //判断是否出界

swap(map[x][y], map[rx][ry]); //交换位置

dfs(rx, ry, g+1); //下一步搜索

swap(map[x][y], map[rx][ry]);

}

return ;

}

for(ans=0; ;ans++){ //迭代加深

dfs(sx, sy, 0); //IDA*搜索

if(flag) {

printf("%d\n",ans); //最优解

break;

}

}