A*算法
A*算法,(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。
算法中的距離估算值與實(shí)際值越接近，最終搜索速度越快。
回顧：BFS、Dijkstra
對(duì)于求兩個(gè)點(diǎn)之間的最短路
普通的BFS是按層遍歷的過程，以起點(diǎn)為中心，以到終點(diǎn)的最短路為半徑的整個(gè)圓內(nèi)的所有點(diǎn)都會(huì)被遍歷到
Dijkstra是通過優(yōu)先隊(duì)列進(jìn)行的優(yōu)化，相當(dāng)于一種貪心，正因?yàn)槠浔举|(zhì)是一種貪心，所以選擇的永遠(yuǎn)是局部最優(yōu)，也就是選擇的是從起點(diǎn)到當(dāng)前位置的距離的最小值的點(diǎn)來繼續(xù)更新。如果開始的搜索中起始點(diǎn)到該點(diǎn)的代價(jià)很小，但在未來的搜索中，從該目標(biāo)到終點(diǎn)的代價(jià)很大，就可能會(huì)花費(fèi)很大的代價(jià)。也就是說優(yōu)先隊(duì)列優(yōu)化的bfs缺乏對(duì)未來的估計(jì)。
A*算法-估價(jià)函數(shù)
A* 算法是一種啟發(fā)式搜索，根據(jù)估價(jià)函數(shù)+當(dāng)前代價(jià)作為優(yōu)先隊(duì)列的排序標(biāo)準(zhǔn)，相當(dāng)于縱觀歷史與預(yù)見未來同時(shí)作用
估價(jià)函數(shù)指的是從當(dāng)前點(diǎn)到終點(diǎn)的代價(jià)的一個(gè)估計(jì)值
估價(jià)函數(shù)的設(shè)計(jì)原則：估值必須比實(shí)際更優(yōu)(估計(jì)代價(jià)<=實(shí)際代價(jià))
如果把好的狀態(tài)估差了，那本來在最優(yōu)解搜索路徑上的狀態(tài)被錯(cuò)誤地估計(jì)了較大的代價(jià)，被壓在堆中無法及時(shí)取出，從而導(dǎo)致非最優(yōu)解搜索路徑上的狀態(tài)不斷擴(kuò)展，直至在目標(biāo)狀態(tài)上產(chǎn)生錯(cuò)誤的答案把
如果把壞的狀態(tài)估好了，只要估價(jià)不大于未來實(shí)際代價(jià)，這個(gè)值總會(huì)比最優(yōu)解更早地被取出，從而得到修正。最壞后果無非就是算的狀態(tài)多了,跑得慢一些。
所以我們要選擇一個(gè)好的估價(jià)函數(shù)，選擇良好的估計(jì)函數(shù)可以使得A*算法的時(shí)間得到縮減，估價(jià)函數(shù)越接近真實(shí)代價(jià)，速度越快
當(dāng)估價(jià)函數(shù)等于0，則退化成普通的優(yōu)先隊(duì)列版的bfs
例題：第K短路
思路：
把
i到t的最短路作為估價(jià)函數(shù)f(i)優(yōu)先隊(duì)列就按照當(dāng)前走過的路徑的長(zhǎng)度 + 估計(jì)函數(shù)最小的狀態(tài)去擴(kuò)展
#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;
}
經(jīng)驗(yàn)之談
對(duì)于有向圖，則建反圖求以終點(diǎn)為起點(diǎn)的最短路為估價(jià)函數(shù)文章來源：http://www.zghlxwxcb.cn/news/detail-403678.html
對(duì)于網(wǎng)格形式的圖，有以下這些啟發(fā)函數(shù)可以使用：文章來源地址http://www.zghlxwxcb.cn/news/detail-403678.html
- 如果圖形中只允許朝上下左右四個(gè)方向移動(dòng)，則可以使用曼哈頓距離。
- 曼哈頓距離： ∣ x 1 ? x 2 ∣ + ∣ y 1 ? y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1??x2?∣+∣y1??y2?∣
- 如果圖形中允許朝八個(gè)方向移動(dòng)，則可以使用對(duì)角距離。
- 對(duì)角距離： 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?∣
- 如果圖形中允許朝任何方向移動(dòng)，則可以使用歐幾里得距離。
- 歐幾里得距離： ( 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?
到了這里，關(guān)于啟發(fā)式搜索 ：A*算法詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
