1

从 sdk 3.0 开始可以轻松使用 iPhone 中的 GPS 功能，但明确禁止使用 Google 的地图。我认为这有两个含义：

  1. 您必须自己提供地图
  2. 您必须自己计算最短路线。

我知道计算最短路线多年来一直困扰着数学家，但汤姆汤姆和谷歌都做得很好，所以这个问题似乎已经解决了。在网上搜索，我自己不是数学家，我遇到了Dijkstra 算法。有没有人在 iPhone 的类似地图的应用程序中成功使用过这个算法？您愿意与我/社区分享吗？这是正确的方法，还是其他选择？非常感谢您的考虑。

4

7 回答 7

5

我不相信 Dijkstra 的算法对现实世界的映射有用，因为正如 Tom Leys 所说（我会评论他的帖子，但缺乏这样做的代表），它需要一个单一的起点。如果起点发生变化，则必须重新计算一切，我想这在 iPhone 这样的设备上对于非常大的数据集会相当慢。

于 2009-05-18T07:52:29.677 回答
4

Dijkstra 算法用于寻找到所有节点的最短路径（从单个起始节点开始）。游戏程序员使用定向搜索，例如 A*。其中 Dijkstra 首先处理最接近起始位置的节点，A* 处理估计最接近结束位置的节点

它的工作方式是您提供从任何给定位置到终点的廉价“估计”功能。一个很好的例子是一只鸟要飞多远才能到达那里。A* 将此添加到每个节点从起点开始的当前距离，然后选择似乎在最短路径上的节点。

您的估计越好，找到一条好路径所需的时间就越短。如果这个时间仍然太长，您可以在简单地图上进行路径查找，然后在更复杂的地图上进行另一次查找，以查找您在简单地图上找到的地点之间的路线。

更新 找了好久，找到了一篇关于A*的文章供大家阅读

于 2009-05-18T07:49:32.210 回答
3

Dijkstra 的算法对于 n 个节点和 m 个边（对于单个路径）是 O(m log n)，并且足够高效，可用于网络路由。这意味着它的效率足以用于一次性计算。

简而言之，Dijkstra 算法的工作原理如下：

Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key

Repeat:
    Pop the node with the lowest depth from the priority queue
    Record the node that you came from so you can track the path back
    Mark the node as having been visited
    If this node is the destination:
        Break
    For each neighbour:
        If the node has not previously been visited:
            Calculate depth as depth of current node + distance to neighbour
            Insert neighbour into the priority queue at the calculated depth.

Return the destination node and list of the nodes through which it was reached.

与普遍的看法相反，Dijkstra 的算法不一定是全对最短路径计算器，尽管它可以适应这一点。

您必须获得街道和十字路口的图表以及十字路口之间的距离。如果您有这些数据，您可以使用 Dijkstra 算法来计算最短路线。

于 2009-05-18T09:53:52.670 回答
1

如果您查看技术 tomtom 所称的“IQ 路线”，它们会测量一天中每个时间段的实际速度和行驶时间。这使得到达时间更加准确。所以预计到达时间更基于事实http://www.tomtom.com/page/iq-routes

于 2011-08-21T10:42:34.733 回答
1

在具有离线地图数据的 iPhone 上，使用 A* 算法计算路线已经足够快了。我有商业上做这件事的经验。我使用 Wikipedia 上记录的 A* 算法，并将道路网络保存在内存中并重新使用它；一旦加载完毕，即使是在西班牙或加拿大西半部这样的大片地区，也几乎是即时的。

我从 OpenStreetMap 或 elswhere 获取数据并将其转换为有向图，假设（根据知情人士的说法，这是正确的做法）任何两条道路共享一个具有相同 ID 的点。我根据预期速度为不同类型的道路分配权重，如果道路的一部分是单向的，我只创建一条弧线；双向道路有两条弧线，每个方向一条。除了一些防止危险转弯的临时代码和实施路由限制之外，这几乎是全部内容。

于 2012-07-20T13:52:20.840 回答
0

这在前面讨论过：什么算法计算地图上从点 a 到点 b 的方向？

于 2009-06-18T10:40:46.913 回答
0

看看CloudMade。他们为 iPhone 和 iPad 提供免费服务，允许根据您当前的位置进行导航。它建立在开放的街道地图上，并具有一些漂亮的功能，例如制作自己的地图样式。它有时有点慢，但它完全免费。

于 2012-02-27T10:33:17.627 回答