A*算法在OI中的应用

2018-01-31 08:03:58来源:cnblogs.com作者:CrazyDave人点击

分享

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)为实际值(当前状态到结束状态的实际代价)

  1. 如果h(n)<d(n),估算代价比实际值小,估计结果更优,因此搜索的范围更大,效率低。但往往能得出最优解。
  2. 如果h(n)=d(n),估算代价等于实际值,估计结果等于实际结果,因此搜索按照实际的最优情况经行,效率最高。
  3. 如果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;        }    }

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台