我一直对 Map Routing 很感兴趣，但我从来没有找到任何好的入门（甚至是高级！）级别的教程。有没有人有任何指针，提示等？
更新：我主要是在寻找有关如何实现地图系统（数据结构、算法等）的指针。
问问题
10547 次
9 回答
15
看看开放街道地图项目，看看在一个真正自由的软件项目中是如何处理这类事情的，只使用用户提供和许可的数据，并有一个包含您可能会感兴趣的东西的 wiki。
几年前，参与其中的人很随和，回答了我的很多问题，所以我看不出他们为什么仍然不是一个好人。
于 2008-08-05T20:27:36.633 回答
5
通过地图路由，您的意思是找到沿街道网络的最短路径？
Dijkstra 最短路径算法是最著名的。维基百科的介绍不错：http ://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
这里有一个 Java 小程序，您可以在其中看到它的运行情况：http ://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html和谷歌您可以引导您找到几乎任何的源代码语言。
任何生成行车路线的实际实施都将包括街道网络上的大量数据，这些数据描述了与穿越链接和节点相关的成本——道路网络层次结构、平均速度、交叉路口优先级、交通信号连接、禁止转弯等。
于 2008-08-15T04:31:27.390 回答
5
A* 实际上更接近于生产映射算法。与 Dijikstra 的原始算法相比，它需要的探索要少得多。
于 2008-09-24T23:19:48.583 回答
4
谷歌地图寻路功能的工程师之一巴里·布鲁米特（Barry Brumitt）就该主题写了一篇可能感兴趣的帖子：
更好的寻路之路 11/06/2007 03:47:00 PM
于 2008-09-17T08:44:28.847 回答
2
而不是向每个地图服务提供商学习 API（如 Gmaps、Ymaps api） 学习Mapstraction很好
“Mapstraction 是一个为各种 javascript 映射 API 提供通用 API 的库”
我建议您访问 URL 并学习通用 API。也有大量的 How-Tos。
于 2008-08-06T13:35:08.930 回答
2
从概念的角度来看，想象一下将一块石头扔进池塘并观察涟漪。这些路线将代表池塘和您的起始位置的石头。
当然，随着距离 n 的增加，算法必须搜索 n^2 路径的一部分。您将带您开始位置并检查从该点开始的所有可用路径。然后递归调用这些路径末端的点，依此类推。
您可以提高性能，方法是不要在路径上双重支持，如果某个点已被覆盖，则不重新检查路径，并放弃花费太长时间的路径。
另一种方法是使用蚂蚁信息素方法，蚂蚁从起点随机爬行并留下气味踪迹，这样越多蚂蚁越过给定路径。如果您从起点和终点都发送（足够）蚂蚁，那么最终气味最强的路径将是最短的。这是因为在给定时间段内，最短路径将被访问更多次，因为蚂蚁以均匀的速度行走。
编辑@Spikie
作为对如何实现池塘算法的进一步解释 - 突出显示了所需的潜在数据结构：
您需要将地图存储为网络。这只是它们之间的一组nodes和edges。一组nodes构成一个route。一条边连接两个节点（可能都是同一个节点），并有一个关联的cost如distance或time来遍历边。边可以是双向的，也可以是单向的。可能最简单的方法是只有单向的，然后在节点之间进行双向旅行（即一条边从 A 到 B，另一条边从 B 到 A）。
举例来说，想象三个火车站以向上的等边三角形排列。在它们之间还有另外三个车站。边将所有相邻的站点连接在一起，最终的图表将有一个倒三角形位于较大的三角形内。
从左下角开始标记节点，从左到右并向上，分别为 A、B、C、D、E、F（F 在顶部）。
假设可以沿任一方向遍历边缘。每条边的成本为 1 公里。
好的，所以我们希望从左下角的 A 到顶部的 F 站。有许多可能的路线，包括那些自己加倍返回的路线，例如 ABCBDEF。
我们有一个例程NextNode，它接受 anode和 acost并为它可以到达的每个节点调用自身。
显然，如果我们让这个例程运行，它最终会发现所有路线，包括可能无限长的路线（例如 ABABABAB 等）。我们通过检查cost. 每当我们访问一个以前没有访问过的节点时，我们都会将成本和我们来自的节点放在那个节点上。如果在我们检查现有成本之前已经访问了一个节点，并且如果我们更便宜，那么我们更新节点并继续（递归）。如果我们更昂贵，那么我们跳过节点。如果所有节点都被跳过，那么我们退出例程。
如果我们命中目标节点，那么我们也会退出例程。
这样，所有可行的路线都会被检查，但最重要的是只检查那些成本最低的路线。在该过程结束时，每个节点将具有最低的到达该节点的成本，包括我们的目标节点。
为了获得我们从目标节点向后工作的路线。由于我们存储了我们来自的节点以及成本，我们只是向后跳来构建路由。对于我们的示例，我们最终会得到如下内容：
节点 A -（总）成本 0 - 来自节点 无
节点 B - 成本 1 - 来自节点 A
节点 C - 成本 2 - 来自节点 B
节点 D - 成本 1 - 来自节点 A
节点 E - 成本 2 - 来自节点 D / 成本2 - 来自节点 B（这是一个例外，因为成本相同）
节点 F - 成本 2 - 来自节点 D
所以最短的路线是ADF。
于 2008-09-26T14:05:18.623 回答
1
关于每次遍历的成本，我想到了另一个想法，但会增加计算所需的时间和处理能力。
示例：根据谷歌地图，我可以采取 3 种方式（我住的地方）从 A 点到 B 点。QuickestGarmin 设备在路线计算中提供这 3 条路径中的每一条。在多次遍历这些路线并取平均值后（显然会根据一天中的时间、咖啡因的量等而产生误差），我觉得算法可以考虑道路上的弯道数量以实现高精度,例如 1 英里 的 直线 路 将 比 1 英里 的 有 急弯 的 路 快. 这不是一个实用的建议，但肯定是我用来改善日常通勤结果集的建议。
于 2011-09-18T21:34:27.853 回答
1
根据我在该领域工作的经验，A* 做得非常好。它（如上所述）比 Dijkstra 的算法快，但对于普通的有能力的程序员来说仍然足够简单来实现和理解。
构建路线网络是最难的部分，但这可以分解为一系列简单的步骤：获得所有道路；对点进行排序；使不同道路上的相同点组成为交叉点（节点）；在节点连接的两个方向上添加弧线（或仅在单向道路的一个方向上）。
A* 算法本身在 Wikipedia 上有很好的记录。优化的关键地方是从开放列表中选择最佳节点，为此您需要一个高性能的优先级队列。如果您使用 C++，您可以使用 STL priority_queue 适配器。
自定义算法以在网络的不同部分（例如，行人、汽车、公共交通工具等）上根据速度、距离或其他标准进行路由是非常容易的。您可以通过编写过滤器来控制哪些路段可用、何时构建网络以及为每个路段分配的权重。
于 2012-07-15T21:13:02.097 回答