具有欧氏距离的A*启发式计算

Question

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

double Sum = 0;

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

return Math.sqrt(Sum);

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

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(我没有做太多的地理空间编程).这篇文章似乎相关,看起来你需要使用半正公式来计算距离.

我在大约一年前写了一篇关于A*的文章,你可能会在这里找到帮助.