【概述】

A*（A-Star）算法是一種在靜態(tài)路網中，求解最短路的最有效的直接搜索方法，也是解決許多搜索問題的有效算法之一。

A* 算法實際上是對 Dijkstra 算法的優(yōu)化后得到的，關于 Dijkstra 算法：點擊這里

A*算法在程序設計競賽中，一般用于解決 k 短路問題，關于 k 短路問題：點擊這里

【原理】

在 Dijkstra 算法中，我們借助優(yōu)先隊列來實現(xiàn)，每次從優(yōu)先隊列中取出結點，再從這個結點擴散到其他結點，而優(yōu)先隊列的優(yōu)先依據是根據起點到隊列中結點最近的一個，即隊列中的結點離起始點最近的會先出隊。

但不可避免的是，Dijkstra 存在跑偏問題，如下圖，若起點為 1 號點，終點為 6 號點，首先一定會走 3、4 號點，這肯定不是最佳路徑，一開始就跑偏了。

在 Dijkstra 算法中，判斷的依據只是已知的起點到某點 i 的距離 G(i)，那么我們可以增加一個判斷量來減少跑偏的概率。

如果能夠計算當前點 i 到終點的距離，再結合 G(i)，那么可以防止過度跑偏，但這個距離是未知的，因此我們可以設置一個估值，即啟發(fā)函數 H(i)。

啟發(fā)函數 H(i) 的設置是 A* 算法關鍵，如何設置這個啟發(fā)函數影響到算法的性能，在得到了啟發(fā)函數后，我們就有了最終的估價函數 F(i)=G(i)+H(i)，在優(yōu)先隊列中，以這個估價函數作為指標進行出隊。

一般來說，在二維平面圖中，我們將圖置于坐標軸中，通過計算結點間的歐幾里得距離來得到兩點間的直線距離，這個距離即可作為當前點 i 到終點距離的估值。但歐幾里得距離的計算要進行開方，較為復雜，一般通過加減法來計算簡單的曼哈頓距離來代替歐幾里得距離，作為啟發(fā)函數 H(i)。

而在一般圖中，我們通常是建立反圖，跑一次最短路算法，將得到每個點到 t?的最短路的距離 dis[i] 作為啟發(fā)函數 H(i)

【實現(xiàn)】

struct Edge {int to, next;int w;Edge() {}Edge(int to, int next, int w) : to(to), next(next), w(w) {} }; struct Map {int tot;int head[N];Edge edge[N * N];Map() {tot = 0;memset(head, -1, sizeof(head));}void addEdge(int x, int y, int w) {edge[++tot].to = y;edge[tot].next = head[x];edge[tot].w = w;head[x] = tot;}Edge &operator[](int pos) { return edge[pos]; } }; int n, m; Map G, GT; int dis[N]; bool vis[N]; struct Status{int node;//點編號int diss;//距離int priority;//優(yōu)先級Status() : node(0), diss(0), priority(dis[0]) {}Status(int node, int diss) : node(node), diss(diss), priority(diss + dis[node]) {}bool operator<(Status b) const { return priority > b.priority; } } status; bool SPFA(int S, int T) { //對反圖求最短路memset(dis, INF, sizeof(dis));memset(vis, false, sizeof(vis));dis[S] = 0;queue<int> Q;Q.push(S);while (!Q.empty()) {int x = Q.front();Q.pop();vis[x] = false;for (int i = GT.head[x]; i != -1; i = GT[i].next) {int y = GT[i].to;if (dis[x] + GT[i].w < dis[y]) {dis[y] = dis[x] + GT[i].w;if (!vis[y]) {Q.push(y);vis[y] = true;}}}}return dis[T] != INF; } int AStar(int S, int T) {priority_queue<Status> Q;Q.push(Status(S, 0));while (!Q.empty()) {Status temp = Q.top();Q.pop();if (temp.node == T)return temp.diss;for (int i = G.head[temp.node]; i != -1; i = G[i].next)if (temp.diss + G[i].w < temp.diss)Q.push(Status(G[i].to, temp.diss + G[i].w));}return -1; } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y, w;scanf("%d%d%d", &x, &y, &w);G.addEdge(x, y, w);GT.addEdge(y, x, w);}int s, t;scanf("%d%d", &s, &t);if (!SPFA(t, s))printf("-1\n");elseprintf("%d\n", AStar(s, t));return 0; }

?

總結

以上是生活随笔為你收集整理的搜索 —— 启发式搜索 —— A* 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。