图的搜索之A*算法 a搜索算法求解八数码

A*算法也是在图中求解最短路径的算法。

由狄克斯特拉算法发展而来，与之不同的是，A*不会计算起点到所有顶点的最短路径。A*算法先定一个估算值，实际计算路径的时候，一旦发现有的路径大于这个估算值，就不进行计算，因此可以提高效率。

估算值的估计是根据已知信息人工估算出来的，这个值最好与实际值很相近，如果无法估计这个值，那么就不能使用A*算法。

举例：从S点到G点，途中所有顶点的权重标记在图中，如果使用狄克斯特拉算法，那么每一个到每一个顶点的距离都要计算。而实际蓝色箭头两个方向离G点趋远。

下面按照A*算法先估算一个值，此处按照直线距离估计为5（等腰直角三角形斜边长度为根号2乘以4的平方，所以结果估计为5或者6都可以）。这样以来有效避免了无效搜索。