java - A* 欧氏距离启发式计算

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 10 年前。

我正在 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，因为 float 上的操作要快得多。

所以尝试这样的事情:

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 代替长/纬度(我没有做过太多地理空间编程)。 This article似乎相关，看起来您需要使用 haversine formula计算距离。

大约一年前，我写了一篇关于 A* 的文章，您可能会发现它有帮助 here .