algorithm - 支持 google/bing map 的数据结构

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




9年前关闭。




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

谢谢

Answer 1

你的问题有两个部分:

用什么样的数据结构来存储 map 信息。

使用什么样的算法从源到目的地“导航”。

对此，我要补充一个问题:

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

我将尝试按顺序解决每个问题。请注意，我不为谷歌地图或必应团队工作，所以很明显，这些信息可能并不完全准确。我基于从关于数据结构和算法的优秀 CS 类(class)中获得的知识。

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

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

我会说这将由某种邻接列表表示，我这么说的原因是因为，如果你想象一张 map ，它本质上是一个稀疏图。从一个位置到另一个位置只有几种方法。想想你的房子!有多少条道路(在我们的例子中是边)通向它？邻接表适合表示稀疏图，邻接矩阵适合表示稠密图。

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

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

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

在经典的实现中，我们简单地在数组的每个元素中存储一个 List(Java 中的 Vector):Adj[]。我会想象，一个链表代替 Adj[] 数组，一个二叉搜索树代替 List[Edge]。二叉搜索树将有助于 O(log N) 节点的插入和删除。这是非常可取的，因为在 List 实现中，加法是 O(1)，移除是 O(N)，当您处理数百万条边时，这是令人望而却步的。

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

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

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

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

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

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

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

作为这篇文章的后续，我将尝试添加指向我在此处放置的许多概念的链接。