A*与IDA*算法

只要启发函数写得好，IDA*能当DP跑……

注：上面那句话是假的。IDA*再快也跑不过DP的。

一 启发式搜索

启发式搜索（Heuristically Search），顾名思义，它不像朴素DFS或BFS那样“盲目地”搜索（或称枚举所有状态），而是“有目的地”进行搜索。它通过启发函数$f(x)$来对每个状态（State）$x$进行估价，进而确定搜索的优先级。这样做的好处是能避免在一些与目的状态毫不相关的状态上浪费过多时间，但是难点也就在于启发函数的设计上。

---

二 A*算法

1 引入

A*（A-star）算法是一种启发式搜索算法，也称A*寻路算法。该算法的启发函数定义为$f(x)=g(x)+h(x)$。其中$g(x)$为距离函数，定义为从初始状态转移到当前状态所消耗的代价；$h(x)$为估价函数，定义为从当前状态转移到目标状态的理想代价。

A*算法每次从若干状态$x_1,x_2,…,x_n$中挑选一个$f(x)$值最小的状态进行转移，这也是它“启发式搜索”的根源。设$h’(x)$为从当前状态$x$转移到目标状态的实际代价，若有$\forall x,h(x)\leqslant h’(x)$，则A*算法可以找到代价最小的转移方法。当$h()$函数满足三角形不等式时，A*算法不会将重复遍历节点。

2 优势

我们看这样一道题：

「LG-T35414」又梦回

如下图，有一个n*m的矩阵。您站在绿色点上，想要去到橙色点。您每次只能上下左右移动一个方格，且不能移动到黑色的方格上。请求出最小移动步数。

此题显然可以用BFS解。但是我们来看一下朴素BFS算法的搜索范围（深蓝色）。

不难发现，从绿色节点向左走的部分都是在做无用功，因为这永远不是最优。而启发式搜索A*就能避免遍历这些节点。

定义$h(x)$为当前节点$x$到目标节点的曼哈顿距离，因为这是理想状态下当前节点到终点所需要走的步数。定义$g(x)$为从起点走到当前节点$x$的步数。设$f(x)=g(x)+h(x)$为节点$x$的启发函数。

该算法的流程如下：

将初始节点加入队列：

1. 在队列中找到f(x)值最小的节点；

2. 遍历该节点四个方向上的节点，判断是(T)否(F)已经访问(最优性剪枝)；若F，则计算它们的启发函数，并将节点放入队列；

3. repeat 1. 直到到达目标节点；

那么答案就是目标节点的$g()$值。看起来是不是非常像BFS？其实可以把它看成改进版的BFS（Improved BFS,IMBFS）。

我们来看一下这种算法的搜索范围：

比BFS高到不知道哪里去了！
但是！实际上，A*的应用范围非常有限。与之相比，下面讲的要IDA*更为实用。

3 代码

上题的求解代码：

const int CN=3010;

const int dx[4]={0,0,1,-1}; //方位数组
const int dy[4]={1,-1,0,0};

class locat{ //坐标
  public: int x,y;
  bool exm(int n,int m){
      return (x>=1&&x<=n&&y>=1&&y<=m);
  }
};

//v deifne
int n,m,p;
bool vis[CN][CN]; //标记位

int abs(int a) {return a>0 ? a:-a;}

//A*
int dist(locat a,locat b){ //返回曼哈顿距离
    return abs(a.x-b.x)+abs(a.y-b.y);
}
class state{ //每个状态（节点）
  public: 
    int g,h; //距离函数和估价函数
    locat pos; //坐标
    bool operator < (const state &a)const 
    {return g+h > a.g+a.h;} //为了用priority_queue
}cur,fin; //当前状态和最终状态
priority_queue<state> Q;
int A_star(){
    cur.h = dist(cur.pos, fin.pos); //计算估价
    Q.push(cur);
    
    while(!Q.empty()){
        cur = Q.top(); //取最小
        Q.pop();
        
        if(vis[cur.pos.x][cur.pos.y]) continue;
        vis[cur.pos.x][cur.pos.y] = true;
        
        if(!dist(cur.pos,fin.pos)) break; //到达终点
        
        for(int k=0;k<4;k++){
            state nxt; //计算下一个状态
            nxt.pos.x = cur.pos.x+dx[k];
            nxt.pos.y = cur.pos.y+dy[k];
            nxt.g = cur.g+1; //步数+1
            nxt.h = dist(nxt.pos,fin.pos); //重新计算估价
            
            if(nxt.pos.exm(n,m) && !vis[nxt.pos.x][nxt.pos.y]) //最优性剪枝 
                Q.push(nxt);
        }
    }
    
    return cur.g;
}

int main()
{
    ... //scan
    A_star();
    ... //print
    return 0;
}

该代码的提交记录；朴素BFS的提交记录。

---

三 IDA*算法

1 思想

顾名思义，IDA*算法就是用迭代加深搜索（IDDFS）实现的A*算法。该算法更不容易被卡TLE，且空间消耗少，应用范围比A*更广。

实际上，IDDFS与IDA*算法的区别仅在于启发函数的有无。

2 例题

「LG-P1389」八数码难题

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。目标布局如下：

1 2 3
8 0 4
7 6 5

解题思路
分析数字的移动：可以看作数字与0调换位置。所以我们找到0的位置并进行搜索即可。

定义估价函数$h(x)$为“当前状态$x$与目标状态相比，不匹配的数字个数”。设当前深度为$d$，则启发函数$f(x) = d + h(x) -1$（有$i$个数字不匹配，最少需要$i-1$步使其全部匹配）。设深度限制为$mxd$，则当$f(x) > mxd$时应剪枝。

最优性剪枝：走过的状态再走一遍肯定不优，故需要判断下一个状态是不是当前状态的上层状态。

代码：

/* IDA* */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};

class locat{ //坐标
  public: int x,y;
    void init(int xx,int yy) {x=xx; y=yy;}
    bool exm() {return (x<=3&&x>=1&&y<=3&&y>=1);} //判断是否在棋盘内
    bool operator !=(const locat &a)const {return (a.x!=x||a.y!=y);} //判断坐标是否相同
};

//v define
int cur[4][4],fin[4][4],ans=0; //cur[][]: 当前状态 ; fin[][]: 最终状态

locat find_loc(int v){ //找值为v的元素的坐标
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(cur[i][j] == v)
                return (locat){i,j};
    return (locat){0,0};
}

//IDDFS
int mxd=1; //深度限制
int h(){ //估价函数 
    int incor=0; //incorrect
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(cur[i][j] != fin[i][j])
                incor++;
    return incor;
}
bool dfs(int d,locat u,locat prv){
    if(d == mxd) return !h(); //到达深度限制，检查是否是最终状态
    if(d+h()-1 > mxd) return false; //A*剪枝 
    for(int k=0;k<4;k++){
        locat v;
        v.init(u.x+dx[k],u.y+dy[k]); //计算下一个0的位置
        if(v.exm() && prv!=v){ //最优性剪枝
            swap(cur[v.x][v.y], cur[u.x][u.y]); //调换
            if(dfs(d+1,v,u)) return true; //到达最终状态，继续返回true
            swap(cur[v.x][v.y], cur[u.x][u.y]); //回溯
        }
    }
    return false; //未到达最终状态
}

int main()
{
    fin[1][1] = 1; fin[1][2] = 2; fin[1][3] = 3;
    fin[2][1] = 8; fin[2][2] = 0; fin[2][3] = 4;
    fin[3][1] = 7; fin[3][2] = 6; fin[3][3] = 5;
    
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            char c; cin>>c;
            cur[i][j] = c-'0';
        }
    
    if(h()){
        while(!dfs(0,find_loc(0),(locat){0,0})) //迭代加深
            mxd++;
        printf("%d",mxd); //输出深度限制
    }   
    else printf("0");    
    
    return 0;
}