0.前言

这里没有负边权，SPFA请右转最短路。
本文章基于路径规划之 A* 算法的精致动图以及算法竞赛等数据以及个人鄙见，望大佬提出建议qwq。

1. 前人的铺垫

1.1.Dijkstra算法

这不是图论的最短路吗？

其实这个算法就是用来寻找图形中节点之间的最短路径

考虑这样一种场景，在一些情况下，图形中相邻节点之间的移动代价并不相等。例如，游戏中的一幅图，既有平地也有山脉，那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。

在Dijkstra算法中，需要计算每一个节点距离起点的总移动代价。同时，还需要一个优先队列结构。对于所有待遍历的节点，放入优先队列中会按照代价进行排序。

在算法运行的过程中，每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。

下图中绿色部分代表有额外点权（默认大于1）：

当图形为网格图且点权均为1时，降为BFS

这里贴一个Dijkstra算法的单源最短路模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct node
{
    int pos,dis;
    bool operator<(const node&x)const{
        return x.dis<dis;
    }
};
priority_queue<node> q;
vector<edge> adj[MN];
void djl(){
	memset(ans,0x3f,sizeof(ans));
    while (!q.empty())
    {
        node f=q.top();
        q.pop();
        int fp=f.pos,fdis=f.dis;
        if(vis[fp]) continue;
        vis[fp]=1;
        for(auto v:adj[fp]){
            if(ans[v.v]>v.w+ans[fp]){
                ans[v.v]=ans[fp]+v.w;
                if(!vis[v.v]){
                    q.push({v.v,ans[v.v]});
                }
            }
        }
    }
}

1.2.贪心最佳优先搜索

如果我们可以预先计算出每个节点到终点的距离，利用曼哈顿，欧拉，对角线距离等求出。我们可以利用这个距离丢进优先队列。每次我们取出最小的进行遍历，这种算法和Dijkstra算法是相似的，而且时间复杂度很低很低。如右图

仔细观察一下，不对啊，如果你在沿着“理论”上的最短路径进行搜索的话，如果最短路径上有障碍物不就错误了？而且这个时候如果绕开，答案是错误的！因为在障碍物有缺口的时候我完全可以直接走离答案最近的缺口啊，也就是说这种情况在“理论最优路径”有障碍物的时候就会出现错误

如下图，有图即最佳优先搜索。

看完上面集中算法，我们总结一下上面的算法的优点与缺点。这里我们直接点出各个算法之间的本质

  • Dijkstra算法：高效的求出一个起点到其他所有点的最短路径，把所有遍历到的点按照到起点的距离压进优先队列进行处理，直到终点停止。但是他也有BFS的一定弊端，就是只看起点，不看终点，说白了就是把图上所有点遍历差不多了，他一定会遇到终点。这种在极端情况下仍需要遍历很多的点（目前来说若不指定终点，这种算法的时间复杂度是O(nlog⁡n)O(n\log n)最优，证明可以见计算机协会的报刊）

  • 贪心最佳优先搜索：对于每一个遍历的点我们看其到终点的距离进行选择，也就是说他只看终点，不看起点。在无障碍物的图上跑的飞快，有障碍物不适用。而且不会回头反悔重新选择。并且使用欧拉，曼哈顿，对角线这类简单的计算，不会提前绕开障碍。

2. A-STAR算法

看完上面算法，我们能否实现一个搜索算法，让他即能够做到即看起点，又看终点，而且跑的都比Dijkstra算法和贪心优先快呢？大名鼎鼎的A-STAR算法就能同时够做到这一点！

我们来看A-STAR是怎么结合这个算法的：

我们设起点为ss，终点为tt，对于每个当前位置的点ii，我们将s→ts \rightarrow t的路径分为s→i→ts\rightarrow i \rightarrow t。

  1. 对于s→is\rightarrow i，我们使用Dijkstra算法来保证最优性
  2. 对于i→ti\rightarrow t ，我们使用贪心最佳优先来保证最优
  3. 如果ii碰壁，我们丢弃他，回溯（类似于反悔贪心），回溯过程中仍由Dijkstra算法保证到起点最优

我们可以使用一个估价函数来操作：

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

其中f(i)f(i)表示当前对ii点的评估，g(i)g(i)表示s→is\rightarrow i的代价，h(i)h(i)表示i→ti \rightarrow t的代价。

敏锐的你一定能发现，如果我把g(i)=0g(i)=0，那么不就是贪心最佳优先吗；如果我把h(i)=0h(i)=0，那么不就是Dijkstra算法吗。这个时候我们就可以了解到A-STAR是怎么能够做到“即看起点，又看终点”

那么怎么设计函数呢，对于g(i)g(i)我们只需要记录走过的路径长度即可，放优先队列里就可以来。而A-STAR高效的地方就在于h(i)h(i)的设计,设计一个好的h(i)h(i)的函数能够减少我们到处“碰壁”的可能，h(i)h(i)函数在A-STAR算法中起到的作用就类似于引路人，引导你如何走（就是如何选点），找到一个好的引路人能够少走弯路（懒的走qwq）。

时间复杂度？在你完全不找引路人h(i)h(i)或者h(i)h(i)及其不靠谱的情况下就是Dijkstra算法，一般情况下跑的快。

最终结果是最优吗，因为它和Dijkstra算法的解一样都是最短路径，当ii达到终点tt的时候h(t)=0h(t)=0，这个时候f(t)=g(t)+h(t)=g(t)f(t)=g(t)+h(t)=g(t)，就是Dijkstra算法求得的最短路。

可以看看A-STAR是如何绕开障碍的

2.1如何设计h函数

在二维平面图中，有三种放置可以设计

  1. 曼哈顿距离——只能在上下左右四个方向移动

h(i)=∣i.x−t.x∣+∣i.y−t.y∣h(i)=|i.x-t.x|+|i.y-t.y|

  1. 对角线距离，可以在八个方向移动

h(i)=max(∣i.x−t.x∣,∣i.y−t.y∣)h(i)=max(|i.x-t.x|,|i.y-t.y|)

  1. 欧拉距离，可以向任意方向移动

h(i)=(i.x−t.x)2+(i.y−t.y)2h(i)=\sqrt{(i.x-t.x)^2+(i.y-t.y)^2}

而对于非平面问题我们就需要自行设计。

但是我们对于h函数应当遵循以下规则

  1. gg和hh应当使用同样的计算方法，例如hh是曼哈顿距离那么gg也一样，不然性质都不一样ff就没有参考意义了。
  2. 根据应用情况正确选择hh，你不能在坐标系上任意移动使用曼哈顿距离吧
  3. hh应当优于实际存在的所有路径。也就是说最后得到的实际路径长度必须大于等于h(i)h(i)，如果小于的话那么最优的路径就算不上了。这一条十分重要。

2.2例题

2.2.1——k短路问题

给出一张图，有 n 个点， m 条边（有向边），并给出起点 s ，终点 t ，以及第 k 短路的 k 。请你求出从 s 到 t 的路径中，第 k 短路径的长度。若不存在，则输出 −1 。

我们使用A-STAR算法做这一类题目，这个题正解不是A-STAR算法因为在图是个nn元环时，最坏时间复杂度为O(nklog⁡n)O(nk\log n)可以构造数据卡出，正解为可持久化可并堆。

那么如何设计h(i)h(i)呢，在这个题目里h(i)h(i)其实就是到终点的距离，我们可以建反边跑Dijkstra算法，就可以求出每个点到终点的h(i)h(i)了。

记g(i)g(i)为经过的距离，那么初始的时候就是(s,0)(s,0)，每个点的状态就是(i,g(i))(i,g(i))，因为h(i)h(i)是确定的。

因为是kk短路，我们可以给每一个点加一个计数器，如果被重复计算超过kk次就不再计算，这种做法对吗？如果该点在最优路径上，那么这个显然不影响结果；如果在，那么分两种情况，第一种kk短路都经过这个点，那么刚好计数器就能够累加答案至kk结束，如果不都经过也不影响kk短路的答案。

故代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#define pir pair<int,int>
using namespace std;
const int MN=1e5+15;
int n,m,s,t,x,h[MN],g[MN],cnt[MN];
const int INF=0x3f3f3f3f;
struct edge
{
    int v,w;
};
struct node{
    int v,nh,ng;
    bool operator<(const node&x)const{
        return nh+ng<x.nh+x.ng;
    }
};
vector<edge> adj[MN],adjh[MN];
void dij(){
// 求h(i)
priority_queue<pir,vector<pir>,greater<pir>>q;
    q.push(pir(0,t));
    h[t]=0;
    while(!q.empty()){
        pir f=q.top();
        q.pop();
        int u=f.second,w=f.first;
        if(w>h[u]) continue;
        for(int i=0;i<adjh[u].size();i++){
            edge e=adjh[u][i];
            int v=e.v,ew=e.w;
            if(h[v]>h[u]+ew){
                h[v]=h[u]+ew;
                q.push(pir(h[v],v));
            }
        }
    }
}
bool astar(){
	//跑A-STAR，如何开局引路人说不能走就不走
	// INF默认无解
    if(h[s]==INF) return 0;
    priority_queue<node> q;
    q.push({s,0,0});
    while(!q.empty()){
        node f=q.top();
        q.pop();
        int u=f.v,fh=f.nh,fg=f.ng;
        cnt[u]++;
        if(u==t&&cnt[u]==x){
            cout<<fg;
            return 1;
        }
        if(cnt[u]>x) continue;
        for(int i=0;i<adj[u].size();i++){
            edge e=adj[u][i];
            int v=e.v,ew=e.w;
            q.push({v,h[v],fg+ew});
        }
    }
    return 0;
}
int main(){
    memset(h,0x3f,sizeof(h));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adjh[v].push_back({u,w});
    }
    cin>>s>>t>>x;
    dij();
    if(!astar()){
        cout<<-1;
    }
    return 0;
}

2.Power Hungry Cows

P10494

2个变量a,ba,b初始时为a=1,b=0a=1,b=0，每一步可以执行a×2,b×2,a+b,∣a−b∣a\times 2,b\times 2,a+b,|a-b| 任意操作，并把结果存回aa或bb，问最快能得到一个整数PP。
1≤P≤200001\le P \le 20000

如何设计估价函数？我们要求出的是最快能够达到x=Px=P或y=Py=P的结果，那么这个时候就呼之欲出了，我们可以设h(i)h(i)为当前值到PP一共需要多少步。我们可以看出只需要让最大的这样做就可以了，而且贪心一下最佳操作就是乘法操作。

我们肯定需要剪枝，因为在计算h(i)h(i)的时候会出现一些无法转移或非最优解的情况。

我们一个状态(x,y,g,h)(x,y,g,h)，其中xx为较大的(a,b)(a,b)其中一个，另一个yy即较小的。

首先当x>n×2x>n\times 2的时候肯定不行（此路不通非走）
当x>n and y=0x>n\,and\,y=0时无法转移
当x>n and y>nx>n\,and\,y>n时不是最优解
当x=yx=y的时候肯定也不是

我们可以用map记录当前的最优解，之后不断更新，如果当前解比最优解还大那么就剪枝。

如果只执行到这里会TLE4个点。

我们还能否进一步进行剪枝，对于a,ba,b函数来说，我们可以进行乘法和加减操作。乘法？加法？

我们可以将上述题目转化为一个方程即ax+byax+by，默认的时候a=1,b=0a=1,b=0，在操作的时候只需要对aa与bb进行修改即可。
我们不考虑能否进行最优解，我们只需要判断是否有解即可，接下来请出贝祖定理！

设a,ba,b是不为0的整数，对任意整数x,yx,y，满足gcd(x,y)∣ax+bygcd(x,y)|ax+by

那么就很简单了，就看PP能否整除gcd(x,y)gcd(x,y)就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pir;
template<typename type>
inline void read(type &x){
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    flag?x=-x:0;
}
template<typename type>
inline void write(type x,bool mode=1)
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}
int n;
map<pir,int> m;
struct node{
    int x,y,g,h;
    bool operator<(const node& a)const{
        return h+g>a.g+a.h;
    }
};
priority_queue<node> q;
void update(int x,int y,int g,int h){

    if(x<y) swap(x,y);
    if(x>n*2) return;
    if(x>n&&y==0) return;
    if(x>n&&y>n) return;
    if(x==y) return;
    if(m[pir(x,y)]&&m[pir(x,y)]<g+1+h) return;
    if(n%__gcd(x,y)) return;

    int newh=0,k=x;
    while(k<n)k*=2,newh++;
    m[pir(x,y)]=g+newh+1;
    q.push({x,y,g+1,newh});
}
void astar(){
    update(1,0,0,0);
    while(!q.empty()){
        node f=q.top();
        q.pop();
        int x=f.x,y=f.y,g=f.g,h=f.h;
        if(f.x==n||f.y==n){
            write(f.g-1);
            return;
        }
        update(x,2*y,g,h);
        update(y,2*x,g,h);
        update(x,2*x,g,h);
        update(y,2*y,g,h);
        update(x,x-y,g,h);
        update(y,x-y,g,h);
        update(x,x+y,g,h);
        update(y,x+y,g,h);
    }
}
int main(){
    ios::sync_with_stdio(0);
    read(n);
    astar();
    return 0;
}

3.ID-DFS与IDA∗*迭代加深(启发式)搜索

3.1 BFS与DFSの痛

我们假设一个场景，一个多叉树，树十分甚至九分的深，树上每一个点表示当前解的状态，而我们要搜索的答案就是这个树上的一个点。我们可以通过BFS和DFS来找到这个终点。例如下图

BFS是一层一层遍历，到depth=2depth=2的层找到，而在他的队列中，拓展到红色节点中同一层级和下一层级的部分节点也会入队。

DFS是按照深度，先遍历左子树在遍历有子树，直到遇到终点，如果树很深那么只有遍历到最深的叶子节点才会回溯。

缺点如下：

  1. BFS可能会消耗巨大空间，第kk层就有至多2k−12^k-1个节点，如果是一颗满二叉树就如上图那么消耗的节点空间就会很多。如果确定终点可以考虑双向BFS，复杂度降为2k22^{\frac{k}{2}}，但是一般情况是不知道终点。
  2. DFS有很多无效搜索的节点，这里不再阐明，可以看图理解。
    那我们可以将两者结合起来吗？IDDFS！

3.2 IDDFS迭代加深搜索

如果问题的解在搜索树的较浅层，那么我们可以用IDDFS来解决问题，他是BFS和DFS结合的产物。即不像BFS挥霍空间，又不像DFS一样搜索过多无效节点。

IDDFS的步骤如下：

  1. 限制深度depth=0depth=0，做DFS
  2. 限制深度depth=1depth=1，做DFS
  3. 限制深度depth=2depth=2，做DFS…直到遇到节点

我们发现最坏的情况就是答案节点一直在最后才会遍历到，由上面公式可以得到对于第kk层至多有2k−12^k-1个节点。那么以此遍历每一层，总时间时间复杂度就是O(21+22+...+2k)=O(2k)O(2^1+2^2+...+2^k)=O(2^k) ，空间复杂度因为是DFS与BFS的结合体，我们DFS由递归计空间复杂度O(n)O(n)，考虑BFS按层遍历，显然空间复杂度O(k)O(k)。

以下是对比：

算法时间复杂度空间复杂度应用场景
DFSO(2n)O(2^n)O(n)O(n)n不是很大，就是搜索树不是很大
BFSO(2k)O(2^k)O(2k)O(2^k)k不是很大，占用空间不会超过限制
IDDFSO(2k)O(2^k)O(k)O(k)k不是很大且空间限制较大

3.3 IDA∗*

IDDFS一般需要升级为IDA∗IDA*，IDA∗IDA*就是利用估价函数f(x)f(x)来进行剪枝的IDDFS。

我们观察IDDFS的步骤，我们再回顾A∗A*提到的BFS与DFS算法的优缺点，我们发现IDDFS也是有着“盲目”的特性在，只是对搜索层数进行限制。如果我们在进行搜索能通过估价函数进行“剪枝”，就能够大幅优化！

来看一道题

P2324

补充：如果能在15步以内达到输出结果，否则输出-1

这道题就是经典的例题，我们可以用A∗A*或者IDA∗IDA*去做，我们使用IDA∗IDA*。

我们的估价函数的目的就是引导我们去达到这个目标状态，我们回顾以下估价函数的组成：$$f(x)=g(x)+h(x)$$
这里g(x)g(x)我们可以统计之前的步数来实现，而h(x)h(x)的设计需要和上面2.1的内容的条件，其中最重要的是“hh应优于实际存在的所有路径”，那么我们就可以设h(x)h(x)为与最终状态的相差个数。

那么h(x)h(x)函数设计很简单，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char goal[6][6]={
	{'0','0','0','0','0','0'},
	{'0','1','1','1','1','1'},
	{'0','0','1','1','1','1'},
	{'0','0','0','*','1','1'},
	{'0','0','0','0','0','1'},
	{'0','0','0','0','0','0'}
};
char map[6][6];
int geth(){
    int cnt=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            if(map[i][j]!=goal[i][j]){
                cnt++;
            }
        }
    }
    return cnt;
}

那么怎么进行IDA∗IDA*呢？其实也很简单，估价函数的值就是预估我们从当前点到目标点到底走多少步，到IDDFSIDDFS上就是拓展多少深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int x,int y,int dep,int mdep){
    if(dep==mdep){
        if(!geth()) isok=1;//答案找到了
        return;
    }
    for(int i=0;i<8;i++){
        int nx=x+fx[i],ny=y+fy[i];
        if(nx>=1&&nx<=5&&ny>=1&&ny<=5){
            swap(map[x][y],map[nx][ny]);
            if(dep+geth()<=mdep) dfs(nx,ny,dep+1,mdep);//如果预估深度足够，那么dfs
            if(isok) return;//如果有答案就返回
            swap(map[x][y],map[nx][ny]);
        }
    }
}

让后就和IDDFS一样，直接搜索就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void dfs(int x,int y,int dep,int mdep){
    if(dep==mdep){
        if(!geth()) isok=1;//答案找到了
        return;
    }
    for(int i=0;i<8;i++){
        int nx=x+fx[i],ny=y+fy[i];
        if(nx>=1&&nx<=5&&ny>=1&&ny<=5){
            swap(map[x][y],map[nx][ny]);
            if(dep+geth()<=mdep) dfs(nx,ny,dep+1,mdep);//如果预估深度足够，那么dfs
            if(isok) return;//如果有答案就返回
            swap(map[x][y],map[nx][ny]);
        }
    }
}

void solve(){
    int kx,ky;
    isok=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            cin>>map[i][j];
            if(map[i][j]=='*'){
                kx=i;
                ky=j;
            }
        }
    }
    for(int i=1;i<=15;i++){
        dfs(kx,ky,0,i);
        if(isok){
            cout<<i<<'\n';
            return;
        }
    }
    cout<<-1<<'\n';
}

4.总结

A∗A*与IDA∗IDA*两个算法都关键在于h(x)h(x)的设计，如果h(x)h(x)设计的好，那么算法跑的就飞快，反之就根BFSBFS差不多。

IDA∗IDA*的速度是大部分比A∗A*快的。