java - 使用欧几里得距离的 A* 启发式计算

Question

我正在用 Java 实现 A* 算法，以查找两点（不同城市的机场）之间的最短路径。为此，我使用无向加权图，其中每条边代表两个节点（机场）之间的距离。启发式计算是通过欧几里得距离完成的。这是我的启发式函数的代码

double Sum = 0;

Sum = Math.pow((destination.getG()-currentNode.getG()),2.0);

return Math.sqrt(Sum);

我正在用 G 值计算启发式，即节点之间的边缘。这是对的吗？请帮忙。启发式函数获取源节点和目标节点。我希望它清楚。

Answer 1

您不使用 G 分数来计算启发式，而是将 G 分数添加到启发式（H 分数）以获得从节点到目标的估计（F 分数）。

欧几里得距离是此图像中所示的直线：

其中，使用两个点 (x ₁ , y ₁ ) 和 (x ₂ , y ₂ ) 是这样的：

h(n) = sqrt((x ₁ - x ₂ ) ² + (y ₁ - y ₂ ) ² )

请注意，您可以sqrt()完全省略，因为执行这么多次是一项非常昂贵的操作。也更喜欢float，double因为对floats 的操作要快得多。

所以尝试这样的事情：

float x = Math.pow(destination.getX() - currentNode.getX(), 2.0);
float y = Math.pow(destination.getX() - currentNode.getX(), 2.0);

return x + y;

我假设您可以以某种方式将 x 和 y 替换为 long/lat（我没有做过很多地理空间编程）。This article似乎相关，看起来您需要使用haversine公式来计算距离。

大约一年前，我写了一篇关于 A* 的文章，在这里您可能会发现它很有帮助。