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;

}

}