4.2欧几里得距离(EuclideanDistance)
4.3切比雪夫距离(ChebyshevDistance)
5，A*算法代码实现
A*搜索算法(A*searchalgorithm)又称A*算法(A-starAlgorithm)，是比较流行的启发式搜索算法之一，被广泛应用于路径优化领域。
A*算法结合了Dijkstra算法的优点(即保证找到最短路径)和贪心算法最佳优先搜索的优点(通过启发式函数引导搜索方向)，在大多数情况下能高效地找到最优路径。
举个例子，我们知道BFS搜索基本上是处于盲搜，它不知道目标值的大概方向，每次都是搜索离它最近的点。
如下图所示，如果使用BFS从起始点到目标点找一条最短的路径，可以看到红色框内的位置离目标点是越来越远，我们没必要提前搜索，先搜索离目标点最近的点即可。
离目标点位置越来越远的点是否可以舍弃，答案肯定是不行的，如下图所示，离目标点越来越近的点被墙挡住了，只能沿着离目标点远的点继续搜索。
A*算法搜索的时候，我们需要确定当前位置到目标点的距离，要始终沿着离目标点最近的位置开始搜索，怎么确定这个距离呢？这里就涉及到了启发式函数的定义。
A*算法是使用一个启发式函数h(n)来估计从位置n到目标点的代价(可以是距离，花费等)，并结合已知的从起始点到位置n的代价g(n)，综合考虑这两个值来选择搜索路径。其核心公式为：f(n)=g(n)+h(n)：
1，g(n)：从起点到位置n的代价。
2，h(n)：从位置n到目标点的估计代价（启发式函数）。
3，f(n)：从起点经过位置n到目标点的总估计代价。
下面对这个公式进行展开讨论：
1，h(n)=0：即启发式函数值为零，即只计算从起始点到位置n的代价，不需要启发函数，此时A*算法退化为Dijkstra算法，可以找到最短路径，但效率较低，因为失去了启发式搜索的优势。
2，h(n)<实际代价：启发式函数的预估代价小于实际代价，A*算法能保证找到最短路径，但可能需要扩展更多的节点，运行较慢，并且h(n)越小，需要扩展的点就越多，运行就越慢，效率就越差。
3，h(n)=实际代价：启发式函数的预估代价恰好等于实际代价，A*算法将只扩展必要的节点，运行非常快，效率也是最高的。但在实际情况中，很难完全准确的预估。
4，h(n)>实际代价：启发式函数的预估代价大于实际代价，运行速度比较快，但找到的不一定是最优解。
5，g(n)=0：不考虑从起始点到位置n的代价，只计算从位置n到目标点的代价，这个就是纯贪心算法，速度也是最快的，但找到的解不一定是最优的。
A*算法和Dijistra区别
A*算法通过启发式搜索策略，利用启发式函数来估算从当前节点到目标节点的成本，从而加速寻路过程。如果启发式选择得当，A*算法通常比Dijkstra算法更快，效率更高，搜索范围更小，因为它可以更直接地朝向目标节点前进。
1，创建一个空的开放列表(openlist)，并把起始点放入其中，开放列表一般使用优先队列，节点按照f(n)的值进行排序，以确保优先查找f(n)值最小的节点。
2，创建一个空的关闭列表(closedlist)，用于记录已经被探索过的节点，以避免重复探索。
3，从开放列表中取出f(n)值最小的节点n。
3.1，如果n是目标点，则终止并返回路径，否则，将n节点移到关闭列表中。
3.2，访问n的每个邻居节点m：
3.2.1，如果m已在关闭列表中，则忽略它。
3.2.2，如果m不在开放列表中，计算g(m)、h(m)和f(m)，并将它添加到开放列表中。
3.2.3，如果m已在开放列表中，并且通过n到达m的路径更短，则更新g(m)、h(m)和f(m)，并设置m的父节点为n。
4，重复上面的步骤3，如果找到目标节点，即可通过回溯父节点来找到最短路径。如果遍历结束后仍未找到终点，说明不存在从起点到终点的路径。
A*算法的步骤是它的核心部分，主要是在第三步，一定要完全掌握。可以参考下我们前面讲的，开放列表相当于BFS中的队列，关闭列表相当于BFS中的visited数组，记录哪些点被访问过了，避免重复访问。
上面我们讲了A*搜索算法的原理以及实现步骤，其中关于距离的启发式函数没有介绍，A*算法的性能高度依赖于启发式函数的选择，一个好的启发式函数可以显著提高搜索效率。
启发式函数比较多，常见的有曼哈顿距离，欧几里得距离，切比雪夫距离。
4.1曼哈顿距离（ManhattanDistance）
曼哈顿距离适用于只能沿水平或垂直方向移动的网格，如城市街道，也称为城市街区距离。对于二维平面上的两个点(x1,y1)和(x2,y2)，曼哈顿距离为|x1-x2|+|y1-y2|。
例如，点(1,3)和(4,6)的曼哈顿距离为|1-4|+|3-6|=3+3=6。
4.2欧几里得距离（EuclideanDistance）
欧几里得距离是两点之间的直线距离，对于二维平面上的两个点(x1,y1)和(x2,y2)，欧几里得距离为sqrt((x1-x2)^2+(y1-y2)^2)。
例如，点(1,1)和(4,5)的欧几里得距离为sqrt((1-4)^2+(1-5)^2)=sqrt(9+16)=5。
4.3切比雪夫距离（ChebyshevDistance）
切比雪夫距离是两点之间的最大水平和垂直距离，对于二维平面上的两个点(x1,y1)和(x2,y2)，切比雪夫距离为max(|x1-x2|,|y1-y2|)。
例如，点(1,1)和(4,5)的切比雪夫距离为max(|1-4|,|1-5|)=4。
A*算法可以看作是BFS的增强版，它根据启发式函数的引导，慢慢朝着目标点移动，我们用下面这个图来看下它怎么搜索的。
因为每次搜索的时候都会计算当前位置的上下左右四个方向，如果搜索的顺序改变可能会导致路径不同，如下图所示两张图，分别是按照右下左上和上下左右顺序搜索的两张图，其中关闭列表中的顶点包含最短路径的顶点。