基本介紹
- 中文名：A*算法
- 外文名：A-star algorithm
- 別稱：啟發式搜尋
- 表達式：f(n)=g(n)+h(n)
原理,簡單案例,算法分類,實際運用,其它算法,好處,
原理
A*（A-Star)算法是一種靜態路網中求解最短路徑最有效的直接搜尋方法，也是許多其他問題的常用啟發式算法。注意——是最有效的直接搜尋算法，之後湧現了很多預處理算法（如ALT，CH，HL等等），線上查詢效率是A*算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中， f(n) 是從初始狀態經由狀態n到目標狀態的代價估計，
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價。
（對於路徑搜尋問題，狀態就是圖中的節點，代價就是距離）
h(n)的選取
保證找到最短路徑（最優解的）條件，關鍵在於估價函式f(n)的選取（或者說h(n)的選取）。
我們以d(n)表達狀態n到目標狀態的距離，那么h(n)的選取大致有如下三種情況：
- 如果h(n)< d(n)到目標狀態的實際距離，這種情況下，搜尋的點數多，搜尋範圍大，效率低。但能得到最優解。
- 如果h(n)=d(n)，即距離估計h(n)等於最短距離，那么搜尋將嚴格沿著最短路徑進行， 此時的搜尋效率是最高的。
- 如果 h(n)>d(n)，搜尋的點數少，搜尋範圍小，效率高，但不能保證得到最優解。
簡單案例
參見參考資料中的“A*算法入門”。
另外，A*同樣可以用於其他搜尋問題，只需要對應狀態和狀態的距離即可。
算法分類
該算法在最短路徑搜尋算法中分類為：
直接搜尋算法：直接在實際地圖上進行搜尋，不經過任何預處理；
啟發式算法：通過啟發函式引導算法的搜尋方向；
靜態圖搜尋算法：被搜尋的圖的權值不隨時間變化（後被證明同樣可以適用於動態圖的搜尋）。
實際運用
距離估計與實際值越接近，估價函式取得就越好
例如對於幾何路網來說，可以取兩節點間曼哈頓距離做為距離估計，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；這樣估價函式f(n)在g(n)一定的情況下，會或多或少的受距離估計值h(n)的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜尋向終點的方向進行。明顯優於Dijkstra算法的毫無方向的向四周搜尋。
算法實現（路徑搜尋）
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的h(s);
將起點放入OPEN表;
while(OPEN!=NULL){ 從OPEN表中取f(n)最小的節點n; if(n節點==目標節點) break; for(當前節點n的每個子節點X) { 計算f(X); if(XinOPEN) if(新的f(X)<OPEN中的f(X)) { 把n設定為X的父親; 更新OPEN表中的f(n); } if(XinCLOSE) continue; if(Xnotinboth) { 把n設定為X的父親; 求f(X); 並將X插入OPEN表中;//還沒有排序 } }//endfor 將n節點插入CLOSE表中; 按照f(n)將OPEN表中的節點排序;//實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。}//endwhile(OPEN!=NULL)保存路徑，即從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
用C語言實現A*最短路徑搜尋算法，作者 Tittup frog(跳跳蛙)。
#include <stdio.h>#include <math.h> #define MaxLength 100 //用於優先佇列（Open表）的數組#define Height 15 //地圖高度#define Width 20 //地圖寬度 #define Reachable 0 //可以到達的結點#define Bar 1 //障礙物#define Pass 2 //需要走的步數#define Source 3 //起點#define Destination 4 //終點 #define Sequential 0 //順序遍歷#define NoSolution 2 //無解決方案#define Infinity 0xfffffff #define East (1 << 0)#define South_East (1 << 1)#define South (1 << 2)#define South_West (1 << 3)#define West (1 << 4)#define North_West (1 << 5)#define North (1 << 6)#define North_East (1 << 7) typedef struct{ signed char x, y;} Point; const Point dir[8] ={ {0, 1}, // East {1, 1}, // South_East {1, 0}, // South {1, -1}, // South_West {0, -1}, // West {-1, -1}, // North_West {-1, 0}, // North {-1, 1} // North_East}; unsigned char within(int x, int y){ return (x >= 0 && y >= 0 && x < Height && y < Width);} typedef struct{ int x, y; unsigned char reachable, sur, value;} MapNode; typedef struct Close{ MapNode *cur; char vis; struct Close *from; float F, G; int H;} Close; typedef struct //優先佇列（Open表）{ int length; //當前佇列的長度 Close* Array[MaxLength]; //評價結點的指針} Open; static MapNode graph[Height][Width];static int srcX, srcY, dstX, dstY; //起始點、終點static Close close[Height][Width]; // 優先佇列基本操作void initOpen(Open *q) //優先佇列初始化{ q->length = 0; // 隊內元素數初始為0} void push(Open *q, Close cls[Height][Width], int x, int y, float g){ //向優先佇列（Open表）中添加元素 Close *t; int i, mintag; cls[x][y].G = g; //所添加節點的坐標 cls[x][y].F = cls[x][y].G + cls[x][y].H; q->Array[q->length++] = &(cls[x][y]); mintag = q->length - 1; for (i = 0; i < q->length - 1; i++) { if (q->Array[i]->F < q->Array[mintag]->F) { mintag = i; } } t = q->Array[q->length - 1]; q->Array[q->length - 1] = q->Array[mintag]; q->Array[mintag] = t; //將評價函式值最小節點置於隊頭} Close* shift(Open *q){ return q->Array[--q->length];} // 地圖初始化操作void initClose(Close cls[Height][Width], int sx, int sy, int dx, int dy){ // 地圖Close表初始化配置 int i, j; for (i = 0; i < Height; i++) { for (j = 0; j < Width; j++) { cls[i][j].cur = &graph[i][j]; // Close表所指節點 cls[i][j].vis = !graph[i][j].reachable; // 是否被訪問 cls[i][j].from = NULL; // 所來節點 cls[i][j].G = cls[i][j].F = 0; cls[i][j].H = abs(dx - i) + abs(dy - j); // 評價函式值 } } cls[sx][sy].F = cls[sx][sy].H; //起始點評價初始值 // cls[sy][sy].G = 0; //移步花費代價值 cls[dx][dy].G = Infinity;} void initGraph(const int map[Height][Width], int sx, int sy, int dx, int dy){ //地圖發生變化時重新構造地 int i, j; srcX = sx; //起點X坐標 srcY = sy; //起點Y坐標 dstX = dx; //終點X坐標 dstY = dy; //終點Y坐標 for (i = 0; i < Height; i++) { for (j = 0; j < Width; j++) { graph[i][j].x = i; //地圖坐標X graph[i][j].y = j; //地圖坐標Y graph[i][j].value = map[i][j]; graph[i][j].reachable = (graph[i][j].value == Reachable); // 節點可到達性 graph[i][j].sur = 0; //鄰接節點個數 if (!graph[i][j].reachable) { continue; } if (j > 0) { if (graph[i][j - 1].reachable) // left節點可以到達 { graph[i][j].sur |= West; graph[i][j - 1].sur |= East; } if (i > 0) { if (graph[i - 1][j - 1].reachable && graph[i - 1][j].reachable && graph[i][j - 1].reachable) // up-left節點可以到達 { graph[i][j].sur |= North_West; graph[i - 1][j - 1].sur |= South_East; } } } if (i > 0) { if (graph[i - 1][j].reachable) // up節點可以到達 { graph[i][j].sur |= North; graph[i - 1][j].sur |= South; } if (j < Width - 1) { if (graph[i - 1][j + 1].reachable && graph[i - 1][j].reachable && map[i][j + 1] == Reachable) // up-right節點可以到達 { graph[i][j].sur |= North_East; graph[i - 1][j + 1].sur |= South_West; } } } } }} int bfs(){ int times = 0; int i, curX, curY, surX, surY; unsigned char f = 0, r = 1; Close *p; Close* q[MaxLength] = { &close[srcX][srcY] }; initClose(close, srcX, srcY, dstX, dstY); close[srcX][srcY].vis = 1; while (r != f) { p = q[f]; f = (f + 1) % MaxLength; curX = p->cur->x; curY = p->cur->y; for (i = 0; i < 8; i++) { if (! (p->cur->sur & (1 << i))) { continue; } surX = curX + dir[i].x; surY = curY + dir[i].y; if (! close[surX][surY].vis) { close[surX][surY].from = p; close[surX][surY].vis = 1; close[surX][surY].G = p->G + 1; q[r] = &close[surX][surY]; r = (r + 1) % MaxLength; } } times++; } return times;} int astar(){ // A*算法遍歷 //int times = 0; int i, curX, curY, surX, surY; float surG; Open q; //Open表 Close *p; initOpen(&q); initClose(close, srcX, srcY, dstX, dstY); close[srcX][srcY].vis = 1; push(&q, close, srcX, srcY, 0); while (q.length) { //times++; p = shift(&q); curX = p->cur->x; curY = p->cur->y; if (!p->H) { return Sequential; } for (i = 0; i < 8; i++) { if (! (p->cur->sur & (1 << i))) { continue; } surX = curX + dir[i].x; surY = curY + dir[i].y; if (!close[surX][surY].vis) { close[surX][surY].vis = 1; close[surX][surY].from = p; surG = p->G + sqrt((curX - surX) * (curX - surX) + (curY - surY) * (curY - surY)); push(&q, close, surX, surY, surG); } } } //printf("times: %d\n", times); return NoSolution; //無結果} const int map[Height][Width] = { {0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1}, {0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1}, {0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1}, {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0}, {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1}, {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}}; const char Symbol[5][3] = { "□", "▓", "▽", "☆", "◎" }; void printMap(){ int i, j; for (i = 0; i < Height; i++) { for (j = 0; j < Width; j++) { printf("%s", Symbol[graph[i][j].value]); } puts(""); } puts("");} Close* getShortest(){ // 獲取最短路徑 int result = astar(); Close *p, *t, *q = NULL; switch(result) { case Sequential: //順序最近 p = &(close[dstX][dstY]); while (p) //轉置路徑 { t = p->from; p->from = q; q = p; p = t; } close[srcX][srcY].from = q->from; return &(close[srcX][srcY]); case NoSolution: return NULL; } return NULL;} static Close *start;static int shortestep;int printShortest(){ Close *p; int step = 0; p = getShortest(); start = p; if (!p) { return 0; } else { while (p->from) { graph[p->cur->x][p->cur->y].value = Pass; printf("（%d，%d）→\n", p->cur->x, p->cur->y); p = p->from; step++; } printf("（%d，%d）\n", p->cur->x, p->cur->y); graph[srcX][srcY].value = Source; graph[dstX][dstY].value = Destination; return step; }} void clearMap(){ // Clear Map Marks of Steps Close *p = start; while (p) { graph[p->cur->x][p->cur->y].value = Reachable; p = p->from; } graph[srcX][srcY].value = map[srcX][srcY]; graph[dstX][dstY].value = map[dstX][dstY];} void printDepth(){ int i, j; for (i = 0; i < Height; i++) { for (j = 0; j < Width; j++) { if (map[i][j]) { printf("%s ", Symbol[graph[i][j].value]); } else { printf("%2.0lf ", close[i][j].G); } } puts(""); } puts("");} void printSur(){ int i, j; for (i = 0; i < Height; i++) { for (j = 0; j < Width; j++) { printf("%02x ", graph[i][j].sur); } puts(""); } puts("");} void printH(){ int i, j; for (i = 0; i < Height; i++) { for (j = 0; j < Width; j++) { printf("%02d ", close[i][j].H); } puts(""); } puts("");} int main(int argc, const char **argv){ initGraph(map, 0, 0, 0, 0); printMap(); while (scanf("%d %d %d %d", &srcX, &srcY, &dstX, &dstY) != EOF) { if (within(srcX, srcY) && within(dstX, dstY)) { if (shortestep = printShortest()) { printf("從（%d，%d）到（%d，%d）的最短步數是: %d\n", srcX, srcY, dstX, dstY, shortestep); printMap(); clearMap(); bfs(); //printDepth(); puts((shortestep == close[dstX][dstY].G) ? "正確" : "錯誤"); clearMap(); } else { printf("從（%d，%d）不可到達（%d，%d）\n", srcX, srcY, dstX, dstY); } } else { puts("輸入錯誤！"); } } return (0);}其它算法
啟發式搜尋其實有很多的算法
比如：局部擇優搜尋法、最好優先搜尋法等等，當然A*也是。這些算法都使用了啟發函式，但在具體的選取最佳搜尋節點時的策略不同。像局部擇優搜尋法，就是在搜尋的過程中選取“最佳節點”後捨棄其他的兄弟節點、父親節點，而一直得搜尋下去。這種搜尋的結果很明顯，由於捨棄了其他的節點，可能也把最好的節點都捨棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，它在搜尋時，並沒有捨棄節點（除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的f(n)比較得到一個“最佳的節點”，這樣可以有效的防止“最佳節點”的丟失。那么A*算法又是一種什麼樣的算法呢？
好處
其實A*算法也是一種最好優先的算法
我們先下個定義，如果一個估價函式可以找出最短的路徑，我們稱之為可採納性。A*算法是一個可採納的最好優先算法。A*算法的估價函式可表示為：
f'(n) = g'(n) + h'(n)
這裡，f'(n)是估價函式，g'(n)是起點到節點n的最短路徑值，h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函式f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明套用這樣的估價函式是可以找到最短路徑的，也就是可採納的。我們說套用這種估價函式的最好優先算法就是A*算法。
舉一個例子，其實廣度優先算法就是A*算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先算法是一種可採納的。實際也是。當然它是一種最臭的A*算法。
再說一個問題，就是有關h(n)啟發函式的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函式越好或說這個算法越好。這就是為什麼廣度優先算法的不甚為好的原因了，因為它的h(n)=0，沒有一點啟發信息。但在遊戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但算法的準確性就差了，這裡就有一個平衡的問題。
