浅谈 A* 与 IDA*

Sternenlicht · 2023-01-01 13:12:32 · 算法·理论

友情提示：在阅读文章之前，请确定对 BFS 与 DFS 较为熟悉。

Part 1：A ^* 算法

一、前置知识

贪心最优搜索：一种启发式搜索，利用 “BFS + 优先队列” 实现。算法思想为 “只看终点，不管起点”。
Dijkstra 算法：一种求最短路径的算法，也是利用 “BFS + 优先队列” 实现，此算法下一步的搜索是盲目的，没有方向感。算法思想为 “只看起点，不管终点”。

（若读者对以上两个算法不熟悉，请自行查阅相关资料。）

二、A ^* 算法的原理及时空复杂度

A ^* 算法是贪心最优搜索和 Dijkstra 算法的结合，它 “既看起点，又看终点”，比 Dijkstra 快，比贪心最优搜索准确。

设起点为 s，终点为 t，算法走到当前位置 i 点，则我们可以把 s-t 的路径分为两部分：s-i-t。

当走到 i 碰壁时，丢弃 i，并回退到上一层重新选择新的点 j，仍由 Dijkstra 保证最优。

A ^* 算法的思路可以简化成一个估价函数。设 f(i) 表示对 i 的评估，g(i) 表示 s-i 的代价，h(i) 表示 i-t 的代价。则有如下等式：

f(i)=g(i)+h(i)

A ^* 算法每次根据最小的 f(i) 选择下一个点。又因为 g(i) 已知，h(i) 未知，所以 f(i) 的性能取决于 h(i) 的计算。

A ^* 的复杂度，最坏情况下退化成 Dijkstra，一般情况下更优。

三、h 函数的设计

在二维平面的图问题中，有 3 种方法计算 h 函数。

曼哈顿距离。应用场景：只能在 4 个方向（上下左右）移动。
对角线距离。应用场景：可以在 8 个方向上移动。
欧氏距离。应用场景：可以向任意方向移动。

设计 h 函数时，有以下 3 条注意事项：

根据应用场景正确选择 h 函数的计算方法。

四、A ^* 算法例题

P2901 [USACO08MAR]Cow Jogging G

题意：输入一张 n 个点，m 条边的图，给定 k，若图中有第 k 短路，输出，若没有，输出 -1。

暴力求解求出所有可能的路径，按从小到大排序，取第 k 小值。

如何用 A ^* 算法优化此过程呢？

求出每个点到终点的距离 \mathrm{dis}，这里可以用 Dijkstra 或 SPFA。
将起点入队。
记 \mathrm{cost} 为起点到当前点的花费，不断扩展 \mathrm{dis+cost}。
抵达终点，记录。若此时是 k 短路，输出，结束程序；若此时不是 k 短路，再次执行步骤 3。

以上步骤有一个优点，第 x 次到达终点时的路径，就是第 x 短路。下面放上我的代码（注意 SPFA 时要跑反图）：

#include <bits/stdc++.h>
namespace IO{
    #define LL long long
    inline LL read(){
        LL x=0,f=1;char c=getchar();
        for (;!isdigit(c);c=getchar())if (c=='-')f=-1;
        for (;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
        return x*f;
    }
    inline void write(LL x,char c='\n'){
        if (x){
            if (x<0)x=-x,putchar('-');
            char a[30];short l;
            for (l=0;x;x/=10)a[l++]=x%10^48;
            for (l--;l>=0;l--)putchar(a[l]);
        }else putchar('0');putchar(c);
    }
}using namespace IO;
using namespace std;

#define int long long
const int N = 1e3+10;
const int M = 1e6+10;
struct Edge{int to,nxt,val;}e1[M],e2[M];
int head1[N],tot1,head2[N],tot2,dis[N],vis[N],n,m,k;
void add1(int x,int y,int z)
{e1[++tot1]={y,head1[x],z};head1[x]=tot1;}
void add2(int x,int y,int z)
{e2[++tot2]={y,head2[x],z};head2[x]=tot2;}
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,1,sizeof(vis));
    queue<int> que;que.push(1);
    dis[1]=0;vis[1]=0;
    while (!que.empty()){
        int x=que.front();
        que.pop();vis[x]=1;
        for (int i=head2[x];i;i=e2[i].nxt){
            int y=e2[i].to;
            if (dis[y]>dis[x]+e2[i].val){
                dis[y]=dis[x]+e2[i].val;
                if (vis[y])vis[y]=0,que.push(y);
            }
        }
    }
}
struct Node{
    int pos,val;
    friend bool operator < (Node x,Node y){
        return x.val+dis[x.pos]>y.val+dis[y.pos];
    }
};
void Astar(){
    priority_queue<Node> que;
    que.push({n,0});
    while (!que.empty()){
        Node t=que.top();que.pop();
        if (t.pos==1){
            write(t.val);k--;
            if (!k)return;
        }
        int x=t.pos;
        for (int i=head1[x];i;i=e1[i].nxt)
            que.push({e1[i].to,t.val+e1[i].val});
    }
}
signed main(){
    n=read(),m=read(),k=read();
    for (int i=1,x,y,z;i<=m;i++)
        x=read(),y=read(),z=read(),
        add1(x,y,z),add2(y,x,z);
    spfa();Astar();
    while (k--)puts("-1");
    return 0;
}

五、总结

A ^* 算法用 Dijkstra 获得最优结果，用贪心最优搜索预测扩展方向，减少搜索的节点数量，相当于 “BFS + 估价函数”。

Part 2：IDA ^* 算法

一、前置知识

IDDFS：迭代加深搜索，是 BFS 与 DFS 的结合，既不浪费空间（BFS 的弊端），也不会搜索过多无效节点（DFS 弊端）。即 “限制深度的 DFS”，形式上为 DFS，结合了 BFS 的思想。在二叉树情况下，IDDFS 时间复杂度为 \Theta(2^k)，空间复杂度为 \Theta(k)，其中 k 为搜索的层数。

二、IDA ^* 算法

IDDFS 只能限制搜索层数，如何进行优化呢？如果在进行 IDDFS 时，能预测出当前继续 DFS 后可能到达的状态，发现不能到达终点，就直接返回，从而提高了效率。这其实就是一个剪枝。

IDA ^* 正是在 IDDFS 中加入估价函数进行剪枝操作的算法。设当前深度为 \mathrm{dep}，将要花费的步数为 \mathrm{step}，深度限制为 \mathrm{limit}，则当 \mathrm{dep}+\mathrm{step}>\mathrm{limit} 时，立即返回 \mathrm{false}。

算法框架：

//定义变量 

int check(){//估价函数 
    int ret;//统计变量
    ...//估价
    return ret;//返回 
}

void dfs(int x,int y,int now,int dep){//x,y当前坐标，now当前深度，dep最大深度限制 
    if (now+check()>dep)return;//若估价后大于限制深度，返回
    if (!check())return ans=1,void();//到达终点，返回，记录
    ...//IDA* 算法 
}

int main(){
    ...//读入+其他处理 
    for (int dep=1;dep<=.../*最大可搜索的深度*/;dep++){//IDDFS  
        dfs(...);//搜索
        if (ans==1){//找到答案 
            write(dep);
            break;
        } 
    } 
    return 0;
}

三、IDA ^* 例题

例题 1：P2324 [SCOI2005]骑士精神

思路：可以发现，每次空白格子与棋子交换，最优情况是每次都一步移动到目标格子，这就是我们的估价函数。

#include <bits/stdc++.h>
namespace IO{
    #define LL long long
    inline LL read(){
        LL x=0,f=1;char c=getchar();
        for (;!isdigit(c);c=getchar())if (c=='-')f=-1;
        for (;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
        return x*f;
    }
    inline void write(LL x,char c='\n'){
        if (x){
            if (x<0)x=-x,putchar('-');
            char a[30];short l;
            for (l=0;x;x/=10)a[l++]=x%10^48;
            for (l--;l>=0;l--)putchar(a[l]);
        }else putchar('0');putchar(c);
    }
}using namespace IO;
using namespace std;

const int dx[] = {0,1,-1,1,-1,2,-2,2,-2};
const int dy[] = {0,2,2,-2,-2,1,1,-1,-1};
const int finally[8][8] = {{0,0,0,0,0,0},
                           {0,1,1,1,1,1},
                           {0,0,1,1,1,1},
                           {0,0,0,2,1,1},
                           {0,0,0,0,0,1},
                           {0,0,0,0,0,0}};//最终答案矩阵
int a[10][10],T,ans,sx,sy;
int check(){//估价函数
    int ret=0;
    for (int i=1;i<=5;i++)
        for (int j=1;j<=5;j++)
            if (a[i][j]!=finally[i][j])
                ret++;
    return ret;
}
void IDAstar(int x,int y,int now,int dep){
    if (now==dep)return ans=!check(),void();
    for (int i=1;i<=8;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if (nx<1||nx>5||ny<1||ny>5)continue;
        swap(a[x][y],a[nx][ny]);
        if (check()+now<=dep)IDAstar(nx,ny,now+1,dep);
        swap(a[x][y],a[nx][ny]);
    }
}
int main(){
    T=read();
    while (T--){
        ans=0;char c;
        for (int i=1;i<=5;i++)
            for (int j=1;j<=5;j++){
                cin>>c;
                if (c=='*')sx=i,sy=j,a[i][j]=2;
                else a[i][j]=c-48;
            }
        if (!check()){puts("0");continue;}
        for (int dep=1;dep<=15;dep++){
            IDAstar(sx,sy,0,dep);
            if (ans){write(dep);break;}
        }
        if (!ans)puts("-1");
    }
    return 0;
}

例题 2：P2534 [AHOI2012]铁盘整理

思路：先离散化，保证最后的序列为 1 \sim n，且不重复。如何构造估价函数呢？我们发现，一次翻转最多也就只能更改一对相邻数之差，对于一个序列，有多少对相邻数之差不为 1，就至少要翻转一次。注意：第 n+1 个数的值要设为 n+1，翻转第 1 \sim n 个数，就是更改了第 n 个数与第 n+1 个数的差。

#include <bits/stdc++.h>
namespace IO{
    #define LL long long
    inline LL read(){
        LL x=0,f=1;char c=getchar();
        for (;!isdigit(c);c=getchar())if (c=='-')f=-1;
        for (;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
        return x*f;
    }
    inline void write(LL x,char c='\n'){
        if (x){
            if (x<0)x=-x,putchar('-');
            char a[30];short l;
            for (l=0;x;x/=10)a[l++]=x%10^48;
            for (l--;l>=0;l--)putchar(a[l]);
        }else putchar('0');putchar(c);
    }
}using namespace IO;
using namespace std;

const int N = 50;
int a[N],b[N],n,ans;
int check(){//估价函数 
    int ret=0;
    for (int i=1;i<=n;i++)
        if (abs(a[i]-a[i+1])!=1)
            ret++;
    return ret;
}
void dfs(int now,int dep,int pre){//IDDFS
    if (now+check()>dep)return;
    if (!check())return ans=1,void();
    for (int i=1;i<=n;i++)
        if (i!=pre)//当前翻转不与上次翻转的长度相同 
            reverse(a+1,a+i+1),
            dfs(now+1,dep,i),
            reverse(a+1,a+i+1);
}
int main(){
    n=read();
    for (int i=1;i<=n;i++)a[i]=b[i]=read();
    sort(b+1,b+n+1);//排序，方便离散化 
    a[n+1]=n+1;//注意 
    for (int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b; //离散化
    for (int i=1;;i++){
        ans=0;
        dfs(0,i,0);
        if (ans)return write(i),0;
    }
    return 0;
}

四、总结

IDA ^* 相当于 “IDDFS + 估价函数”，其精髓在于限制深度，达到更优秀的时间复杂度。

Part 3：闲言

A ^* 算法通常应用在 k 短路的题目当中，因为它有一个非常好用的性质：第 x 个出队的就是第 x 短路。IDA ^* 比 A ^* 算法更优，因为其用到了 IDDFS 的思想，当题目的范围较小，且问到 “最少” 时，可以考虑使用 IDA ^*。

最后附上一个自己的 A ^* 与 IDA ^* 的题单：https://www.luogu.com.cn/training/266137。

如果有错误的地方，欢迎在评论区指出（大佬不喜轻喷）。