Aster（A*）算法

Aster算法是在Dijkstra算法基础上发展出来的，是在静态路径中用于求解最优路径有效的直接搜索算法，比dijkstra算法多了一个启发式的搜索函数，也就是通过一个代价函数来确定搜索方向（从起点开始向周围扩张，通过代价函数，计算得到周围每个节点的代价值，选出最小代价节点作为下一个扩展点，重复这个过程直到到达目标点。）。

算法对比：

A ^∗ 算法的代价函数f(n)表示为：

例子：要求机器人从起始点绕过障碍物到达目标点，这里我们使用 A*算法寻找出最优的路径。
第一步：将地图简化成易于表示的区域。
我们使用正方形作为寻路算法的单元（也可用其他形状），将如图所示区域分为5X7的栅格。

第二步：建立open和closed列表

open列表：记录下所有被考虑来寻找最短路径的方格；把起始点定义为“父节点”，靠近父节点的点称为子节点，将所有可通过的点放入open列表中作为待查点（图中的8 9 10 15 17 22 23 24八个方格。）
closed列表：记录下不会再被考虑的方格。如图首先将起始点添加到closed列表中。

A^∗算法中的代价函数f(n)=g(n)+h(n)中：

• g值：g值表示从当前方格到达起始点代价值。我们规定机器人水平（或垂直）移动一个格代价值为10，对角线方向移动代价值为14.方格左下角为g值。

• h值：h值表示从当前方格到目标点（图中可乐所在位置）的代价。这里我们用曼哈顿距离表示。下图表示了不同点h值得度量。（h值我们放在格子得右下角）

算g时要考虑障碍物的存在，h则不用。

h：指的是17这个格子到终点的h值

。。。。。。
。。。。。。
。。。。。。