寻找地理坐标之间最短路径的算法
AFAIK，AStar 的工作原理是直线。
就我而言，我们有地理坐标，我可以得到航路点之间的直线距离。但我想知道这大概是多少？实际上重要的“公路”实际距离可能有所不同。
例子。 假设A和B在同一平面上，并且到目标点的距离相等，如果我们考虑A和目标点、B和目标点之间的直线。
A 和目标点之间的“公路”距离可能大于或小于 B。但由于 AStar 基于直线工作，因此它会将两条路线返回为最短路线。
这是正确的吗？
如果是，那么如果我们想要基于实际距离（Km/m）的结果，应该考虑哪种算法？
如果不是，那么我错过了什么？
AStar works on the basis of straight lines, AFAIK.
In my case, we have geocoordinates and I can get the straight line distance between the waypoints. But I am wondering how approximate will that be? The actual distance "by road", which actually matters can be different.
Example.
Assuming A and B are on the same plane, and will be equidistant from the goal point, if we consider a straight line between A and the goal point and, B and the goal point.
The distance "by road" between A and the goal point may be greater or lesser than B. But because the AStar works on the basis of straight lines, it will return both the routes as the shortest.
Is that correct?
If yes, then which algo should be considered , if we want the results on the basis of actual distance in Km/m?
If no, then what's the point that I am missing?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
默认情况下，A-star 在边具有非负权重的图上运行。不存在边缘必须是直线的限制。与Dijkstra 算法相比，A-star 的不同之处在于它使用启发式地首先搜索图的哪些节点。在嵌入欧几里德空间的图的情况下，这种启发式通常被选择为节点之间的欧几里德距离，尽管还有其他可能性。
By default, A-star operates on a graph with edges having non-negative weights. There is no constraint that the edges have to be straight lines. The thing that makes A-star different, than say Dijkstra's algorithm, is that it uses a heuristic in which nodes of the graph to search first. This heuristic is typically chosen to be Euclidean distance between nodes in the case of a graph embedded in Euclidean space, though there are other possibilities.
好吧，既然你要求我发布答案……
在了解 A* 之前，您必须首先了解 Dijkstra 算法。给定一个图（一组节点以及节点之间的边）和每条边的（正）“距离”（例如道路距离），Dijkstra 算法给出某个源节点和每个目标节点之间的最短距离。例如，在您的图表中，节点可能是道路交叉口，边缘可能是道路，您在边缘上施加的权重/距离可能是该道路的长度，或者穿过该道路所需的时间，或者任何。
请理解：Dijkstra 算法总是根据您在边缘上施加的权重给出正确的距离。事实上，该图甚至不需要嵌入平面中，即，首先可能不存在“直线距离”的概念。它可以是任何任意图。
现在，A* 可以被认为是加速 Dijkstra 算法的特定启发式算法。您可以将其视为使用启发式来决定考虑图中节点的顺序。
形式上：你有一个图 G，其中有两个节点 s 和 t，你想要找到 s 和 t 之间的距离 d(s,t)。 （距离是根据图表，例如根据示例中的道路距离。）为了找到 d(s,t)，在 A* 中，您使用启发式函数 h(x)，它满足 h(x) ≤ d(x ，t）。例如（仅一种可能性），您可以选择 h(x) 作为从 x 到 t 的直线距离。 h(x) 作为 d(x,t) 的估计越好，A* 算法运行得越快，但 h 的选择只影响速度，而不影响答案：它总是根据下式给出最短距离d，不是 h。
因此，要找到 s 到 t 的道路距离，只需将 d(u,v) 设置为每对节点 u 和 v 之间有道路的道路距离，运行 A*，您将找到 d(s ,t) 你想要的。
OK, since you asked me to post an answer….
Before you understand A*, you must first understand Dijkstra's algorithm. Given a graph (a set of nodes, and edges between nodes) and the (positive) "distance" of each edge (e.g. the road distance), Dijkstra's algorithm gives the shortest distance between a certain source node and each destination node. For instance, in your graph, the nodes may be road-intersections, the edges may be the roads, and the weight/distance you put on an edge may be the length of that road, or the time it takes to traverse it, or whatever.
Please understand: Dijkstra's algorithm always gives the correct distance according to the weights you have put on the edges. In fact, the graph need not even be embeddable in a plane, i.e., there may be no notion of "straight line distance" in the first place. It can be any arbitrary graph.
Now, A* can be thought of as a particular heuristic to speed up Dijkstra's algorithm. You can think of it as using a heuristic to decide the order in which to consider nodes in the graph.
Formally: you have a graph G, two nodes s and t in it, and you want to find the distance d(s,t) between s and t. (The distance is according to the graph, e.g. according to road distance in your example.) To find d(s,t), in A* you use a heuristic function h(x) which satisfies h(x) ≤ d(x,t). For instance (just one possibility), you can choose h(x) to be the straight line distance from x to t. The better h(x) is as an estimate of d(x,t), the faster the A* algorithm will run, but the choice of h affects only the speed, not the answer: it will always give the shortest distance according to d, not h.
So to find the road distance s to t, just set d(u,v) to be the road distance for every pair of nodes u and v with a road between them, run A*, and you'll find the d(s,t) you want.
您可以使用加权图对这种情况进行建模，其中顶点是您考虑的点，它们之间的边的权重等于对应点之间的道路距离。然后，您可以使用例如 Dijkstra 算法 来查找点之间的最短距离。
例如，如果平面上有点 A 和 B，并且它们之间的道路距离等于 C，那么在图中您将有顶点 [A] 和 [B] 以及它们之间的长度为 C 的边：
You can model the situation with a weighted graph, where vertices are the points you consider, and the edges between them have the weights equal to the road distances between corresponding points. Then you can use, for example, Dijkstra's algorithm to find the shortest distance between points.
For example, if you have points A and B on a plane, and the road distance between them is equal to C, then in graph you will have vertices [A] and [B] and an edge of length C between them: