启发式搜索 ：A*算法详解

A*算法

A*算法,(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。

算法中的距离估算值与实际值越接近，最终搜索速度越快。

回顾：BFS、Dijkstra

对于求两个点之间的最短路

普通的BFS是按层遍历的过程，以起点为中心，以到终点的最短路为半径的整个圆内的所有点都会被遍历到

Dijkstra是通过优先队列进行的优化，相当于一种贪心，正因为其本质是一种贪心，所以选择的永远是局部最优，也就是选择的是从起点到当前位置的距离的最小值的点来继续更新。如果开始的搜索中起始点到该点的代价很小，但在未来的搜索中，从该目标到终点的代价很大，就可能会花费很大的代价。也就是说优先队列优化的bfs缺乏对未来的估计。

A*算法-估价函数

A* 算法是一种启发式搜索，根据估价函数+当前代价作为优先队列的排序标准，相当于纵观历史与预见未来同时作用

估价函数指的是从当前点到终点的代价的一个估计值

估价函数的设计原则：估值必须比实际更优(估计代价<=实际代价)

• 如果把好的状态估差了，那本来在最优解搜索路径上的状态被错误地估计了较大的代价，被压在堆中无法及时取出，从而导致非最优解搜索路径上的状态不断扩展，直至在目标状态上产生错误的答案把

• 如果把坏的状态估好了，只要估价不大于未来实际代价，这个值总会比最优解更早地被取出，从而得到修正。最坏后果无非就是算的状态多了,跑得慢一些。

所以我们要选择一个好的估价函数，选择良好的估计函数可以使得A*算法的时间得到缩减，估价函数越接近真实代价，速度越快

当估价函数等于0，则退化成普通的优先队列版的bfs

例题：第K短路

思路：

把i到t的最短路作为估价函数f(i)

优先队列就按照当前走过的路径的长度 + 估计函数最小的状态去扩展

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
typedef pair<int, pii> piii;

#define MAX 300000 + 50
int n, m, k, x, y, z;
int s, t;

int tot;
int head[MAX];
int rhead[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int he[], int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = he[u];
    he[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void dijkstra(int s){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, inf);
    q.push(m_p(0, s));dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = rhead[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
}

int num[MAX];
void Astar(){
    priority_queue<piii, vector<piii>, greater<piii> >q;
    q.push(m_p(dis[s], m_p(0, s)));
    while (!q.empty()) {
        auto [d, u] = q.top().second;q.pop();
        ++num[u];
        if(num[t] == k){
            cout << d << endl;
            return;
        }
        if(num[u] > k)continue;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            q.push(m_p(dis[v] + d + tr[i].val, m_p(d + tr[i].val, v)));
        }
    }
    cout << -1 << endl;
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y >> z;
        add(head, x, y, z);
        add(rhead, y, x, z);
    }
    cin >> s >> t >> k;
    if(s == t)++k;
    dijkstra(t);
    Astar();
}


int main(){
    io;
    work();
    return 0;
}

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
82
83
84
85
86
87
88
89
90
91
92

经验之谈

对于有向图，则建反图求以终点为起点的最短路为估价函数

对于网格形式的图，有以下这些启发函数可以使用：

• 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离。
  • 曼哈顿距离： $|x_1-x_2|+|y_1-y_2|$
• 如果图形中允许朝八个方向移动，则可以使用对角距离。
  • 对角距离： $\sqrt{2}\ast min(|x_1-x_2|,|y_1-y_2|)+|x_1-x_2|+|y_1-y_2|$
• 如果图形中允许朝任何方向移动，则可以使用欧几里得距离。
  • 欧几里得距离：$\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$