本文参考：(44条消息) A*算法（超级详细讲解，附有举例的详细手写步骤）_Clark-dj的博客-CSDN博客_a*算法

(44条消息) 路径规划算法_于追梦丶的博客-CSDN博客_路径规划算法

A*算法基本概念

A*算法发表于1968年，A*算法是将Dijkstra算法与广度优先搜索算法（BFS）二者结合而成，通过借助启发式函数的作用，能够使该算法能够更快的找到最优路径。A*算法是静态路网中求解最短路径最有效的直接搜索方法，是最强大且最受欢迎的图搜索算法之一。

A算法的启发式函数：f(n)=g(n)+h(n)

• f(n)表示结点的综合优先级，在选择结点时考虑该结点的综合优先级；
• g(n)表示起始点到当前结点的代价值；
• h(n)表示当前结点到目标点的代价估计值，启发式函数。

当h(n)趋近于0时，此时算法退化为Dijkstra算法，路径一定能找到，但速度比较慢；当g(n)趋近于0时，算法退化为BFS算法，不能保证一定找到路径，但速度特别快。我们可以通过调节h(n)的大小来调整算法的精度与速度。
在A*算法中，采用最多的是欧几里得距离，即dist = srqt((y2-y1)2+(x2-x1)2)。

A*算法原理详细解释：

！！！重要：A*算法详细实现步骤

 A*算法的寻路伪代码(C++)

//FindPath
do{//确定中心搜索点，上一个中心点关闭，新的中心点开启 查找：Find the minimumm "point" of "F" from the "open_list" center;"now_point" = "min_point";//minimumm point "now_point"添加到"close_list";//新中心点的周围点开启，新中心点关闭 循环遍历："now_point"相邻的周围8格"s_now_point"中的每一个;//这一块它指的就是now_point周围8点当前搜索点 s_now_point，为了简单直接用它表示 if (它不可通过||它已经在"close_list"中){什么也不做;} else if (它不在开启列表中){把它添加进"open_list";把"now_point"作为这它的"father",计算它的"F","G","H";}else if (它已经在开启列表中){//通过G来判断是否需要更新 if (new_G < old_G){更新它的"father"为当前中心搜索点"now_point";更新它的"G"与"F" ;} else{不更新，保持原来的"father", "G"与"F" ;} }
} while(目标格"end_point"已经在"open_list"||"open_list"==NULL)
//存在路径：目标格"end_point"已经在"open_list"
//不存在路径： "open_list"==NULL，搜索了所有可能的点 

A*算法的优缺点：

优点：
1） 利用启发式函数，搜索范围小，提高了搜索效率
2） 如果最优路径存在，那么一定能找到最优路径
缺点：
1） A算法不适用于动态环境
2） A算法不太适合于高维空间，计算量大
3） 目标点不可达时会造成大量性能消耗