A*算法-展开的椭圆属性
A* algorithm - ellipse property of expension
基于A*的椭圆属性，这个算法为什么收敛
一系列扩展椭圆中的所有节点？
A* 使用函数 f(x) = g(x) + h(x) 评估下一个要访问的节点，其中 g(x) 是从开始到 x 和 h(x) 的实际成本是从 x 到目标（= 启发式）的估计成本。
让我们看一下欧几里得平面中的连续情况，我们想从 (0, 0) 到 (10, 20)。那么：
g(x) = Length(x)
探索前沿的形状在很大程度上取决于启发式。让我们从完美的启发式开始
h(x) = Length(x - (10, 20))
我们可以在平面上绘制 g(x) + h(x) 的值，并查看访问节点的顺序（f 较小的点将首先访问）。这样做，我们应该知道，如果以前访问过 none 个节点的邻居，则无法访问该节点，因此实际值仅表示顺序。我们会记住这一点。使用完美的启发式，我们得到下图：
起点和目标之间连接上的所有点具有相同的 f 成本，等于起点和目标的距离。如果我们检查 f，我们会看到
f = Length(x - (0, 0)) + Length(x - (10, 20)),
这正是以起点和目标为焦点的椭圆的隐含形式。
我说过形状取决于启发式。如果启发式是实际距离的下限，则启发式是有效的。让我们试试
h(x) = 0.5 * Length(x - (10, 20))
现在，算法将在到达目标之前开始探索起点周围的更多点。特别是，将访问目标点之前轮廓内的所有点。
我们甚至可以更进一步，设置
h(x) = 0
这是 Dijkstra 算法的设置，在这里我们不能说到目标的距离：
此处，算法将访问起点周围磁盘中的节点。
到目标的距离的一个常见近似值是曼哈顿距离，因为它的计算成本很低：
h(x, y) = |x - 10| + |y - 20|
此试探法无效，因为它不是实际距离的下限。它给了我们：
这正是靠近目标的点的 f 分数低于靠近起点的点的情况。虽然他们在这个图中的值较低，但他们当然不会被首先访问，因为他们的邻居还没有被探索过。这是一个 close-up:
我们可以通过引入常数因子使启发式有效：
h(x, y) = 1/sqrt(2) * (|x - 10| + |y - 20|)
这将为我们提供一个具有正确正面形状的有效启发式算法：
基于A*的椭圆属性，这个算法为什么收敛 一系列扩展椭圆中的所有节点？
A* 使用函数 f(x) = g(x) + h(x) 评估下一个要访问的节点，其中 g(x) 是从开始到 x 和 h(x) 的实际成本是从 x 到目标（= 启发式）的估计成本。
让我们看一下欧几里得平面中的连续情况，我们想从 (0, 0) 到 (10, 20)。那么：
g(x) = Length(x)
探索前沿的形状在很大程度上取决于启发式。让我们从完美的启发式开始
h(x) = Length(x - (10, 20))
我们可以在平面上绘制 g(x) + h(x) 的值，并查看访问节点的顺序（f 较小的点将首先访问）。这样做，我们应该知道，如果以前访问过 none 个节点的邻居，则无法访问该节点，因此实际值仅表示顺序。我们会记住这一点。使用完美的启发式，我们得到下图：
起点和目标之间连接上的所有点具有相同的 f 成本，等于起点和目标的距离。如果我们检查 f，我们会看到
f = Length(x - (0, 0)) + Length(x - (10, 20)),
这正是以起点和目标为焦点的椭圆的隐含形式。
我说过形状取决于启发式。如果启发式是实际距离的下限，则启发式是有效的。让我们试试
h(x) = 0.5 * Length(x - (10, 20))
现在，算法将在到达目标之前开始探索起点周围的更多点。特别是，将访问目标点之前轮廓内的所有点。
我们甚至可以更进一步，设置
h(x) = 0
这是 Dijkstra 算法的设置，在这里我们不能说到目标的距离：
此处，算法将访问起点周围磁盘中的节点。
到目标的距离的一个常见近似值是曼哈顿距离，因为它的计算成本很低：
h(x, y) = |x - 10| + |y - 20|
此试探法无效，因为它不是实际距离的下限。它给了我们：
这正是靠近目标的点的 f 分数低于靠近起点的点的情况。虽然他们在这个图中的值较低，但他们当然不会被首先访问，因为他们的邻居还没有被探索过。这是一个 close-up:
我们可以通过引入常数因子使启发式有效：
h(x, y) = 1/sqrt(2) * (|x - 10| + |y - 20|)
这将为我们提供一个具有正确正面形状的有效启发式算法：