algorithm - A* map 查找(最短时间)中使用了哪种启发式算法？

Question

像 GoogleMaps 这样的网站不仅可以找到从城市 A 到城市 B 的最短路径，还可以找到耗时最少的路径(不同的道路有不同的限速)。

要找到从 A 到 B 的最短路径，启发式方法很简单 - 它只是当前观察到的节点和 B 之间的欧几里德距离(假设 map 不是太大)。

如果我们对最短时间感兴趣并考虑特定边缘的速度限制怎么办？

我的猜测是特定节点的权重将代表到达那里所花费的时间，而启发式将是

(double) Euclidean_distance(node,B)/maximum_speedlimit_in_country

我的猜测是正确的还是我遗漏了什么？

提前谢谢你。

Answer 1

我不是 100% 确定这是否真的是他们使用的，但你的启发式方法对我来说似乎是可以接受的，因为它没有高估任何节点的成本(因此，使用启发式方法找到的路径将是最佳的)。