8

我想知道像 google/bing 地图这样的应用程序中的数据结构是什么。搜索路线时，怎么会这么快返回结果？使用什么样的算法来确定这些信息？

谢谢

4

6 回答 6

14

你的问题有两个部分：

  1. 使用什么样的数据结构来存储地图信息。
  2. 使用哪种算法从源“导航”到目的地。

对此，我还要补充一个问题：

  1. Google/Bing 如何“流入”数据。例如，您可以无缝地从几英里放大到地面，同时保持坐标系。

我将尝试按顺序解决每个问题。请注意，我不为 Google 地图或 Bing 团队工作，因此很明显，这些信息可能并不完全准确。我的基础是从一门关于数据结构和算法的优秀 CS 课程中获得的知识。

Ans 1）地图存储在边缘加权有向图中。地图上的位置是顶点，从一个位置到另一个位置（从一个顶点到另一个顶点）的路径是边。

很明显，由于可能有数百万个顶点和一个数量级的边，真正有趣的是这个边加权有向图的表示。

我会说这将由某种邻接表表示，我之所以这么说是因为，如果你想象一张地图，它本质上是一个稀疏图。从一个位置到另一个位置只有几种方法。想想你的房子！有多少条道路（在我们的例子中是边）通向它？邻接表适用于表示稀疏图，邻接矩阵适用于表示密集图。

当然，即使我们能够有效地表示内存中的稀疏图，考虑到顶点和边的数量，一次将所有内容都存储在内存中是不可能的。因此，我会想象下面有某种流媒体库。

打个比方，如果你玩过魔兽世界/Syrim/GTA这样的开放世界游戏，你会发现在很大程度上没有加载屏幕。但很明显，一次将所有内容都放入内存是不可能的。因此，使用四叉树和截锥体剔除算法的组合，这些游戏能够动态加载资源（地形、精灵、网格等）。

我会想象类似的东西，但对于 Graphs。我没有对这个特定方面进行太多思考，但是要构建一个非常基本的系统，可以想象一个内存数据库，它们在运行时根据需要从图中查询和添加/删除顶点和边。这给我们带来了另一个有趣的观点。由于需要在运行时删除和添加顶点和边，所以邻接表的经典实现不会削减它。

在经典实现中，我们只是在数组的每个元素中存储一个 List（Java 中的 Vector）：Adj[]。我想，一个链表代替 Adj[] 数组，一个二叉搜索树代替 List[Edge]。二叉搜索树将有助于 O(log N) 节点的插入和删除。这是非常可取的，因为在 List 实现中，添加是 O(1)，删除是 O(N)，当您处理数百万条边时，这是禁止的。

这里要注意的最后一点是，在您真正开始导航之前，“没有”图表。由于可能有数百万用户，因此为每个人维护一个巨大的图表是没有意义的（仅由于内存空间需求，这是不可能的）。我想当您统计导航过程时，会为您创建一个图表。很明显，由于您从位置 A 开始并转到位置 B（以及之后可能的其他位置），为您创建的图形不应该占用大量内存（前提是流式架构已到位）。

Ans 2）这是一个非常有趣的问题。解决这个问题的最基本算法是 Dijkstra Path Finding 算法。存在更快的变体，例如 A*。如果 Dijkstra 可以与上面讨论的流式架构一起正常工作，我会想象 Dijkstra 足够快。Dijkstra 使用与 V 成比例的空间和与 E lg V 成比例的时间，这是非常好的数字，尤其是对于稀疏图。请记住，如果流式架构尚未确定，V 和 E 将爆炸，并且 Dijkstra 的空间和运行时间要求将使其望而却步。

Ans 1) 流式问题：不要将此问题与上面讨论的流式架构混淆。这基本上是在问如何实现无缝缩放。

实现这一点的一个很好的算法是四叉树算法（您可以将其推广到 n-tree）。当您遍历树时，您将较粗略的图像存储在树中较高的位置，并存储较高分辨率的图像。这实际上是 KML (Keyhole) 用它的映射算法所做的。Keyhole 是一家多年前与 NVIDIA 合作的公司，生产了第一批类似“Google Earth”的软件。

Quad Tree culling 的灵感来自现代 3D 游戏，它用于快速剔除不在视锥体中的场景部分。

为了进一步澄清这一点，假设您正在从非常高的地方查看美国地图。在这个级别，您基本上将地图分成 4 个部分，并使每个部分成为四叉树的子级。

现在，当您放大时，您会放大其中一个部分（很明显，您可以在中心放大，这样您的缩放实际上会触及所有 4 个部分，但为简单起见，假设您放大了其中一个部分部分）。因此，当您放大到一个部分时，您会遍历该部分的 4 个子项。这 4 个子级包含其父级的更高分辨率数据。然后，您可以继续缩小，直到找到一组包含最高分辨率数据的叶子。为了从一个分辨率跳到下一个“无缝”，可以使用模糊和褪色效果的组合。

作为这篇文章的后续，我将尝试添加指向我在这里提出的许多概念的链接。

于 2011-12-30T08:09:36.087 回答
2

对于这种应用程序，您可能需要某种数据库来表示地图特征以及它们之间的连接，然后需要：

  1. 地图特征库的空间索引，可以通过二维坐标进行高效查询；和
  2. 一种搜索连接以找到成本最低的路线的好方法，用于某种成本度量（例如距离）。

对于 1，一个例子是R-tree数据结构。

对于 2，您需要一个图搜索算法，例如A*。

于 2010-01-23T23:00:27.773 回答
1

从谷歌作者那里查找一篇关于 Highway Dimension 的论文。这个想法是预先计算重要节点之间的最短路径，然后通过这些路径路由所有内容。你不会使用住宅街道从洛杉矶到芝加哥，除了在两端上下高速公路。

于 2010-10-18T19:13:30.547 回答
0

我会认为它是一个计算几何问题。当您单击地图中的特定坐标并使用该信息时，可以获得该位置的纬度和经度。根据经纬度和缩放级别，可以识别地点。

一旦你确定了这两个地方，你唯一的问题就是确定最近的路线。现在这个问题是找到两点之间的最短路径，它们之间有多边形块（对应于不包含道路的地方），唯一可能的连接是道路。这是一个已知问题，并且存在有效的算法来解决这个问题。

我不确定这是否是谷歌正在做的事情，但我希望他们在这些方面做点什么。

这个学期我要学习计算几何。这是课程链接：http ://www.ams.sunysb.edu/~jsbm/courses/545/ams545.html 。如果您有兴趣，请检查它们。

于 2010-01-26T05:37:57.457 回答
0

我不确定内部数据结构，但它可能是某种基于 2D 坐标的树结构，仅显示一定数量的级别。这些级别将对应于缩放因子，因此您可以忽略低于当前级别的 5 个级别以及高于当前级别的内容。

无论它的结构如何，您都可以使用它：

http://code.google.com/apis/maps/documentation/reference.html

于 2010-01-22T04:51:45.970 回答
-5

我想知道像 google/bing 地图这样的应用程序中的数据结构是什么。

对用户：XHTML/CSS/Javascript。像任何网站一样。

在服务器上：谁知道？这里有 Google 开发人员吗？它当然不是 PHP 或 ASP.net ......

搜索路线时，怎么会这么快返回结果？

因为谷歌花费了数年、人力和数百万美元来构建架构以获得尽可能快的服务器反应时间？

使用什么样的算法来确定这些信息？

行程规划算法。

于 2010-01-22T04:32:51.280 回答