A*搜尋算法俗稱A星算法。A*算法是比較流行的啟發式搜尋算法之一，被廣泛套用於路徑最佳化領域[。它的獨特之處是檢查最短路徑中每個可能的節點時引入了全局信息，對當前節點距終點的距離做出估計，並作為評價該節點處於最短路線上的可能性的量度。
基本介紹
- 中文名：A*搜尋算法
- 外文名：A-star Algorithm
- 別名：A星算法
- 套用領域：圖最優路徑搜尋/查找
- 類型：求出最低通過成本的算法
算法描述,性質,可採納性,單調性,信息性,缺陷,
算法描述
A*改變它自己行為的能力基於啟發式代價函式，啟發式函式在遊戲中非常有用。在速度和精確度之間取得折衷將會讓你的遊戲運行得更快。在很多遊戲中，你並不真正需要得到最好的路徑，僅需要近似的就足夠了。而你需要什麼則取決於遊戲中發生著什麼，或者運行遊戲的機器有多快。 假設你的遊戲有兩種地形，平原和山地，在平原中的移動代價是1而在山地的是3，那么A星算法就會認為在平地上可以進行三倍于山地的距離進行等價搜尋。 這是因為有可能有一條沿著平原到山地的路徑。把兩個鄰接點之間的評估距離設為1.5可以加速A*的搜尋過程。然後A*會將3和1.5比較，這並不比把3和1比較差。然而，在山地上行動有時可能會優於繞過山腳下進行行動。所以花費更多時間尋找一個繞過山的算法並不經常是可靠的。 同樣的，想要達成這樣的目標，你可以通過減少在山腳下的搜尋行為來打到提高A星算法的運行速率。若想如此可以將A星算法的山地行動耗費從3調整為2即可。這兩種方法都會給出可靠地行動策略。
用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值是遞增的，那么它最先生成的路徑一定就是最短的。
信息性
如何判斷兩種策略哪一個更好呢?具有的啟發信息越多，搜尋的狀態就越少，越容易找到最短路徑，這樣的策略就更好。在兩個啟發策略中，如果有h(n1)
h(n2)，則表示策略h:比h,具有更多的啟發信息，同時h(n)越大表示它所搜尋的空間數就越少。但是同時需要注意的是:信息越多就需要更多的計算時間，從而有可能抵消因為信息多而減少的搜尋空間所帶來的好處。
缺陷
A*算法進行下一步將要走的節點的搜尋的時候，每次都是選擇F值最小的節點，因此找到的是最優路徑。但是正因為如此A*算法每次都要擴展當前節點的全部後繼節點，運用啟發函式計算它們的F值，然後選擇F值最小的節點作為下一步走的節點。在這個過程中，OPEN表需要保存大量的節點信息，不僅存儲量大是一個問題，而且在查找F值最小的節點時，需要查詢的節點也非常多，當然就非常耗時，這個問題就非常嚴重了。再加上如果遊戲地圖龐大，路徑比較複雜，路徑搜尋過程則可能要計算成千上萬的節點，計算量非常巨大。因此，搜尋一條路徑需要一定的時間，這就意味著遊戲運行速度降低。
