use*_*412 6 algorithm driving-directions data-structures
我想知道google/bing地图等应用程序中的数据结构是什么.如何在搜索路线时如此快速地返回结果？什么样的算法用于确定这些信息？
谢谢
小智 10
您的问题分为两部分:
对此,我想补充一个问题:
我将尝试按顺序解决每个问题.请注意,我不为谷歌地图或必应团队工作,所以很明显,这些信息可能不完全准确.我的基础是从一个关于数据结构和算法的优秀CS课程中获得的知识.
Ans 1)地图存储在边加权有向图中.地图上的位置是顶点,从一个位置到另一个位置(从一个顶点到另一个顶点)的路径是边缘.
很明显,由于可以有数百万个顶点和一个数量级更多的边缘,真正有趣的是这个边缘加权有向图的表示.
我会说这会用某种邻接列表来表示,我说的原因是因为,如果你想象一张地图,它本质上是一个稀疏图.从一个位置到另一个位置只有几种方法.想想你的房子!有多少条道路(在我们的情况下是边缘)导致它？邻接列表适用于表示稀疏图,邻接矩阵适用于表示密集图.
当然,即使我们能够有效地在内存中表示稀疏图形,但考虑到顶点和边缘的数量,将无法一次将所有内容存储在内存中.因此,我会想象下面有某种流媒体库.
要为此创建一个类比,如果您曾经玩过像魔兽世界/ Syrim/GTA这样的开放世界游戏,您会发现很大程度上没有加载屏幕.但很明显,不可能立刻将所有东西都装进记忆中.因此,使用四叉树和平截头体剔除算法的组合,这些游戏能够动态加载资源(地形,精灵,网格等).
我会想象类似的东西,但对于Graphs.我没有对这个特定的方面进行过多的考虑,但是为了制作一个非常基本的系统,可以想象一个内存数据库,他们根据需要在运行时查询和添加/删除图中的顶点和边.这带来了另一个有趣的观点.由于顶点和边需要在运行时删除并添加,因此Adjacency List的经典实现不会削减它.
在经典实现中,我们只是在数组的每个元素中存储一个List(一个Java中的Vector):Adj [].我想,代替Adj []数组的链表和代替List [Edge]的二叉搜索树.二叉搜索树将促进O(log N)插入和删除节点.这是非常理想的,因为在List实现中,当加法是O(1)时,删除是O(N),当你处理数百万个边时,这是令人望而却步的.
这里要注意的最后一点是,在您实际开始导航之前,有"无"图形.由于可能有数百万用户,因此为每个人维护一个巨大的图表是没有意义的(由于仅内存空间要求,这是不可能的).我想,在统计导航过程时,会为您创建一个图表.很明显,由于您从位置A开始并转到位置B(以及之后可能的其他位置),因此为您创建的图表不应占用大量内存(前提是流式架构已到位).
答案2)这是一个非常有趣的问题.解决该问题的最基本算法是Dijkstra Path Finding算法.存在更快的变化,例如A*.如果它可以与上面讨论的流式架构一起正常工作,我会想象Dijkstra足够快.Dijkstra使用与V成比例的空间和与E lg V成比例的时间,这是非常好的数字,特别是对于稀疏图.请记住,如果流媒体架构尚未被确定,V和E将爆炸,Dijkstra的空间和运行时间要求将使其变得令人望而却步.
回答1)流媒体问题:不要将此问题与上面讨论的流式架构混淆.这基本上是询问如何实现无缝变焦.
实现这一目标的一个很好的算法是四叉树算法(你可以将它推广到n树).在树中向下移动时,可以在树中存储较粗的图像,在较高分辨率的图像中存储较高分辨率的图像.这实际上是KML(Keyhole)对其映射算法所做的.Keyhole是一家多年前与NVIDIA合作生产第一款"Google Earth"软件之一的公司.
Quad Tree剔除的灵感来自于现代3D游戏,它用于快速剔除不在视锥体中的部分场景.
为了进一步澄清这一点,想象一下你正在从真正的高处看美国的地图.在此级别,您基本上将地图拆分为4个部分,并使每个部分成为四叉树的子级.
现在,当您放大时,您可以放大其中一个部分(很明显,您可以在中心放大,这样您的缩放实际上会触及所有4个部分,但为了简单起见,我们可以放大其中一个部分.部分).因此,当您放大一个部分时,您将遍历该部分的4个子项.这4个孩子包含其父母的更高分辨率数据.然后,您可以继续缩小,直到您点击一组包含最高分辨率数据的树叶.为了使从一个分辨率跳跃到下一个"无缝",可以利用模糊和衰落效果的组合.
作为这篇文章的后续内容,我将尝试添加我在这里提出的许多概念的链接.