A*算法
A*算法,(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。
算法中的距离估算值与实际值越接近，最终搜索速度越快。
回顾：BFS、Dijkstra
对于求两个点之间的最短路
普通的BFS是按层遍历的过程，以起点为中心，以到终点的最短路为半径的整个圆内的所有点都会被遍历到
Dijkstra是通过优先队列进行的优化，相当于一种贪心，正因为其本质是一种贪心，所以选择的永远是局部最优，也就是选择的是从起点到当前位置的距离的最小值的点来继续更新。如果开始的搜索中起始点到该点的代价很小，但在未来的搜索中，从该目标到终点的代价很大，就可能会花费很大的代价。也就是说优先队列优化的bfs缺乏对未来的估计。
A*算法-估价函数
A* 算法是一种启发式搜索，根据估价函数+当前代价作为优先队列的排序标准，相当于纵观历史与预见未来同时作用
估价函数指的是从当前点到终点的代价的一个估计值
估价函数的设计原则：估值必须比实际更优(估计代价<=实际代价)
如果把好的状态估差了，那本来在最优解搜索路径上的状态被错误地估计了较大的代价，被压在堆中无法及时取出，从而导致非最优解搜索路径上的状态不断扩展，直至在目标状态上产生错误的答案把
如果把坏的状态估好了，只要估价不大于未来实际代价，这个值总会比最优解更早地被取出，从而得到修正。最坏后果无非就是算的状态多了,跑得慢一些。
所以我们要选择一个好的估价函数，选择良好的估计函数可以使得A*算法的时间得到缩减，估价函数越接近真实代价，速度越快
当估价函数等于0，则退化成普通的优先队列版的bfs
例题：第K短路
思路：
把
i到t的最短路作为估价函数f(i)优先队列就按照当前走过的路径的长度 + 估计函数最小的状态去扩展
#include <bits/stdc++.h>
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;
}
经验之谈
对于有向图，则建反图求以终点为起点的最短路为估价函数文章来源：https://www.toymoban.com/news/detail-403678.html
对于网格形式的图，有以下这些启发函数可以使用：文章来源地址https://www.toymoban.com/news/detail-403678.html
- 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离。
- 曼哈顿距离： ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1−x2∣+∣y1−y2∣
- 如果图形中允许朝八个方向移动，则可以使用对角距离。
- 对角距离： 2 ∗ m i n ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) + ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ \sqrt{2}*min(|x_1-x_2|,|y_1-y_2|)+|x_1-x_2|+|y_1-y_2| 2∗min(∣x1−x2∣,∣y1−y2∣)+∣x1−x2∣+∣y1−y2∣
- 如果图形中允许朝任何方向移动，则可以使用欧几里得距离。
- 欧几里得距离： ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} (x1−x2)2+(y1−y2)2
到了这里，关于启发式搜索 ：A*算法详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
