1

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

double Sum = 0;

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

return Math.sqrt(Sum);

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

4

1 回答 1

9

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

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

在此处输入图像描述

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

h(n) = sqrt((x 1 - x 2 ) 2 + (y 1 - y 2 ) 2 )

请注意，您可以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* 的文章，在这里您可能会发现它很有帮助。

于 2013-06-01T07:48:15.153 回答