A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜寻方法，也是解决许多搜寻问题的有效算法。算法中的距离估算值与实际值越接近，最终搜寻速度越快。
基本介绍
- 中文名：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到目标状态的代价估计，
g(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*算法是一个可採纳的最好优先算法。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)的信息，即减小约束条件。但算法的準确性就差了，这里就有一个平衡的问题。
