A*算法是用于寻找两点之间的最短路径,同时它也是一种静态路网中求解最短路最有效的直搜索方法,公式f(n)=h(n)+g(n)给出了邻居节点到目标节点所需要的总消耗成本,h(n)是当前节点到该邻居节点的所消耗的成本，g(n)是该邻居节点到目标节点的估计消耗成本,比较常用的估计方法是欧几里得方法和曼哈顿方法。

A*算法首先要准备两个列表，一个开启列表，一个关闭列表，开启列表存储还未走的节点(但不是一开始就把所有节点加入开启列表),关闭列表存储走过的节点,将起始节点加入到开启列表,在开启列表不为空时,取出开启列表中最小消耗成本的节点,判断是否是目标节点,是就直接结束A*,取得它的周围邻居节点(通常是8个),判断邻居节点是否在关闭列表中,在关闭列表中,不做处理，不在关闭列表中,再判断是否在开启列表中，若已在开启列表中,计算它的f(n),是否比以前的f(n)小,小就更新它的f(n)并将它的父节点设为当前节点。大的话就不做处理,若不在开启列表中,计算它的f(n)，更新f(n)将父节点设为当前节点。处理完它的周围邻居节点后，一轮循环结束,再移除开启列表中的当前节点，放在关闭列表中,因为已经走过这个节点。然后在开启列表不为空时继续上述循环，直到找到目标节点,或者找遍所有节点都找不到目标节点。C++代码如下(相关函数并未实现,视实际情况而定):

1 typedef struct node 2 { 3 float currentCost;//h(n) 4 float toTalCost;//f(n) 5 node * parent;//父节点 6 }Node; 7 Vector
     
        OpenList;//开启列表 8 Vector
      
         CloseList;//关闭列表 9 10 Node  AStar(Node start,Node Goal){11   OpenList.Add(start);12   while(OpenList.Length!=0)13 {14       Node* minNode=  OpenLIst.Min();//Min()选出最小消耗成本节点15       if(minNode == Goal)16 {17 return minNode;18 }19        Vector
       
         Neighbors;//邻居列表20          GetNeighBors(Neighbors,minNode）;/*得到最小消耗成本节点的周围邻居节点*/21            for(int i=0;i
       
      
     

若成功返回一个节点,那么可以不断往回迭代父节点得到一条逆向的最短路径。A*的思想是为每个节点都估价消耗成本(沿当前所走的路径到目标节点的消耗成本),选择最小消耗成本的节点优先计算,就使节点搜索沿目标节点那边搜索，也被称之为启发式搜索。而开启列表得到最小的消耗成本节点或添加节点，应该用二叉堆(最小堆)插入,这样取最小节点时间复杂度为O(1),添加节点时间复杂度为O(log(n)),比另一种遍历取节点O(n)，加节点O(1)好一些。