44最短路径:地图软件是如何计算出最优出行路径的?Q群170701297.pdf
《44最短路径:地图软件是如何计算出最优出行路径的?Q群170701297.pdf》由会员分享,可在线阅读,更多相关《44最短路径:地图软件是如何计算出最优出行路径的?Q群170701297.pdf(14页珍藏版)》请在三一文库上搜索。
1、44|最短路径:地图软件是如何计算出最优出行路径的? file:/F/geektime/ebook/数据结构与算法之美/44最短路径:地图软件是如何计算出最优出行路径的?.html2019/1/22 18:48:23 44|最短路径:地图软件是如何计算出最优出行路径的? 基础篇的时候,我们学习了图的两种搜索算法,深度优先搜索和广度优先搜索。这两种算法主要是针对无权图的搜索算法。针对有权图,也就是图中的每条边都 有一个权重,我们该如何计算两点之间的最短路径(经过的边的权重和最小)呢?今天,我就从地图软件的路线规划问题讲起,带你看看常用的最短路径算 法(Shortest Path Algorith
2、m)。 像Google地图、百度地图、高德地图这样的地图软件,我想你应该经常使用吧?如果想从家开车到公司,你只需要输入起始、结束地址,地图就会给你规划一条 最优出行路线。这里的最优,有很多种定义,比如最短路线、最少用时路线、最少红绿灯路线等等。作为一名软件开发工程师,你是否思考过,地图软件的最优 路线是如何计算出来的吗?底层依赖了什么算法呢? 算法解析 我们刚提到的最优问题包含三个:最短路线、最少用时和最少红绿灯。我们先解决最简单的,最短路线。 解决软件开发中的实际问题,最重要的一点就是建模,也就是将复杂的场景抽象成具体的数据结构。针对这个问题,我们该如何抽象成数据结构呢? 我们之前也提到过,
3、图这种数据结构的表达能力很强,显然,把地图抽象成图最合适不过了。我们把每个岔路口看作一个顶点,岔路口与岔路口之间的路看作一 条边,路的长度就是边的权重。如果路是单行道,我们就在两个顶点之间画一条有向边;如果路是双行道,我们就在两个顶点之间画两条方向不同的边。这样, 整个地图就被抽象成一个有向有权图。 具体的代码实现,我放在下面了。于是,我们要求解的问题就转化为,在一个有向有权图中,求两个顶点间的最短路径。 public class Graph / 有向有权图的邻接表表示 private LinkedList adj; / 邻接表 private int v; / 顶点个数 public Gra
4、ph(int v) this.v = v; this.adj = new LinkedListv; for (int i = 0; i (); public void addEdge(int s, int t, int w) / 添加一条边 this.adjs.add(new Edge(s, t, w); private class Edge public int sid; / 边的起始顶点编号 public int tid; / 边的终止顶点编号 public int w; / 权重 public Edge(int sid, int tid, int w) this.sid = sid; t
5、his.tid = tid; this.w = w; / 下面这个类是为了dijkstra实现用的 private class Vertex 44|最短路径:地图软件是如何计算出最优出行路径的? file:/F/geektime/ebook/数据结构与算法之美/44最短路径:地图软件是如何计算出最优出行路径的?.html2019/1/22 18:48:23 public int id; / 顶点编号ID public int dist; / 从起始顶点到这个顶点的距离 public Vertex(int id, int dist) this.id = id; this.dist = dist;
6、 想要解决这个问题,有一个非常经典的算法,最短路径算法,更加准确地说,是单源最短路径算法(一个顶点到一个顶点)。提到最短路径算法,最出名的莫过 于Dijkstra算法了。所以,我们现在来看,Dijkstra算法是怎么工作的。 这个算法的原理稍微有点儿复杂,单纯的文字描述,不是很好懂。所以,我还是结合代码来讲解。 / 因为Java提供的优先级队列,没有暴露更新数据的接口,所以我们需要重新实现一个 private class PriorityQueue / 根据vertex.dist构建小顶堆 private Vertex nodes; private int count; public Prio
7、rityQueue(int v) this.nodes = new Vertexv+1; this.count = v; public Vertex poll() / TODO: 留给读者实现. public void add(Vertex vertex) / TODO: 留给读者实现. / 更新结点的值,并且从下往上堆化,重新符合堆的定义。时间复杂度O(logn)。 public void update(Vertex vertex) / TODO: 留给读者实现. public boolean isEmpty() / TODO: 留给读者实现. public void dijkstra(in
8、t s, int t) / 从顶点s到顶点t的最短路径 int predecessor = new intthis.v; / 用来还原最短路径 Vertex vertexes = new Vertexthis.v; for (int i = 0; i nextVertex if (minVertex.dist + e.w “ + t); 我们用vertexes数组,记录从起始顶点到每个顶点的距离(dist)。起初,我们把所有顶点的dist都初始化为无穷大(也就是代码中的Integer.MAX_VALUE)。我们 把起始顶点的dist值初始化为0,然后将其放到优先级队列中。 我们从优先级队列中取
9、出dist最小的顶点minVertex,然后考察这个顶点可达的所有顶点(代码中的nextVertex)。如果minVertex的dist值加 上minVertex与nextVertex之间边的权重w小于nextVertex当前的dist值,也就是说,存在另一条更短的路径,它经过minVertex到达nextVertex。那我们就 把nextVertex的dist更新为minVertex的dist值加上w。然后,我们把nextVertex加入到优先级队列中。重复这个过程,直到找到终止顶点t或者队列为空。 以上就是Dijkstra算法的核心逻辑。除此之外,代码中还有两个额外的变量,predeces
10、sor数组和inqueue数组。 predecessor数组的作用是为了还原最短路径,它记录每个顶点的前驱顶点。最后,我们通过递归的方式,将这个路径打印出来。打印路径的print递归代码我就不详 细讲了,这个跟我们在图的搜索中讲的打印路径方法一样。如果不理解的话,你可以回过头去看下那一节。 inqueue数组是为了避免将一个顶点多次添加到优先级队列中。我们更新了某个顶点的dist值之后,如果这个顶点已经在优先级队列中了,就不要再将它重复添加进 去了。 看完了代码和文字解释,你可能还是有点懵,那我就举个例子,再给你解释一下。 44|最短路径:地图软件是如何计算出最优出行路径的? file:/F/
11、geektime/ebook/数据结构与算法之美/44最短路径:地图软件是如何计算出最优出行路径的?.html2019/1/22 18:48:23 理解了Dijkstra的原理和代码实现,我们来看下,Dijkstra算法的时间复杂度是多少? 在刚刚的代码实现中,最复杂就是while循环嵌套for循环那部分代码了。while循环最多会执行V次(V表示顶点的个数),而内部的for循环的执行次数不确定,跟 每个顶点的相邻边的个数有关,我们分别记作E0,E1,E2,E(V-1)。如果我们把这V个顶点的边都加起来,最大也不会超过图中所有边的个数E(E表示边 的个数)。 for循环内部的代码涉及从优先级队
12、列取数据、往优先级队列中添加数据、更新优先级队列中的数据,这样三个主要的操作。我们知道,优先级队列是用堆来实现 的,堆中的这几个操作,时间复杂度都是O(logV)(堆中的元素个数不会超过顶点的个数V)。 所以,综合这两部分,再利用乘法原则,整个代码的时间复杂度就是O(E*logV)。 弄懂了Dijkstra算法,我们再来回答之前的问题,如何计算最优出行路线? 从理论上讲,用Dijkstra算法可以计算出两点之间的最短路径。但是,你有没有想过,对于一个超级大地图来说,岔路口、道路都非常多,对应到图这种数据结构 上来说,就有非常多的顶点和边。如果为了计算两点之间的最短路径,在一个超级大图上动用Di
13、jkstra算法,遍历所有的顶点和边,显然会非常耗时。那我们有没 有什么优化的方法呢? 做工程不像做理论,一定要给出个最优解。理论上算法再好,如果执行效率太低,也无法应用到实际的工程中。对于软件开发工程师来说,我们经常要根据问题 的实际背景,对解决方案权衡取舍。类似出行路线这种工程上的问题,我们没有必要非得求出个绝对最优解。很多时候,为了兼顾执行效率,我们只需要计算出 一个可行的次优解就可以了。 44|最短路径:地图软件是如何计算出最优出行路径的? file:/F/geektime/ebook/数据结构与算法之美/44最短路径:地图软件是如何计算出最优出行路径的?.html2019/1/22
14、18:48:23 有了这个原则,你能想出刚刚那个问题的优化方案吗? 虽然地图很大,但是两点之间的最短路径或者说较好的出行路径,并不会很“发散”,只会出现在两点之间和两点附近的区块内。所以我们可以在整个大地图上, 划出一个小的区块,这个小区块恰好可以覆盖住两个点,但又不会很大。我们只需要在这个小区块内部运行Dijkstra算法,这样就可以避免遍历整个大图,也就大 大提高了执行效率。 不过你可能会说了,如果两点距离比较远,从北京海淀区某个地点,到上海黄浦区某个地点,那上面的这种处理方法,显然就不工作了,毕竟覆盖北京和上海的 区块并不小。 我给你点提示,你可以现在打开地图App,缩小放大一下地图,看
15、下地图上的路线有什么变化,然后再思考,这个问题该怎么解决。 对于这样两点之间距离较远的路线规划,我们可以把北京海淀区或者北京看作一个顶点,把上海黄浦区或者上海看作一个顶点,先规划大的出行路线。比如,如 何从北京到上海,必须要经过某几个顶点,或者某几条干道,然后再细化每个阶段的小路线。 这样,最短路径问题就解决了。我们再来看另外两个问题,最少时间和最少红绿灯。 前面讲最短路径的时候,每条边的权重是路的长度。在计算最少时间的时候,算法还是不变,我们只需要把边的权重,从路的长度变成经过这段路所需要的时 间。不过,这个时间会根据拥堵情况时刻变化。如何计算车通过一段路的时间呢?这是一个蛮有意思的问题,你
16、可以自己思考下。 每经过一条边,就要经过一个红绿灯。关于最少红绿灯的出行方案,实际上,我们只需要把每条边的权值改为1即可,算法还是不变,可以继续使用前面讲 的Dijkstra算法。不过,边的权值为1,也就相当于无权图了,我们还可以使用之前讲过的广度优先搜索算法。因为我们前面讲过,广度优先搜索算法计算出来的两 点之间的路径,就是两点的最短路径。 不过,这里给出的所有方案都非常粗糙,只是为了给你展示,如何结合实际的场景,灵活地应用算法,让算法为我们所用,真实的地图软件的路径规划,要比这 个复杂很多。而且,比起Dijkstra算法,地图软件用的更多的是类似A*的启发式搜索算法,不过也是在Dijkst
17、ra算法上的优化罢了,我们后面会讲到,这里暂且不展 开。 总结引申 今天,我们学习了一种非常重要的图算法,Dijkstra最短路径算法。实际上,最短路径算法还有很多,比如Bellford算法、Floyd算法等等。如果感兴趣,你可以自 己去研究。 关于Dijkstra算法,我只讲了原理和代码实现。对于正确性,我没有去证明。之所以这么做,是因为证明过程会涉及比较复杂的数学推导。这个并不是我们的重 点,你只要掌握这个算法的思路就可以了。 这些算法实现思路非常经典,掌握了这些思路,我们可以拿来指导、解决其他问题。比如Dijkstra这个算法的核心思想,就可以拿来解决下面这个看似完全不相关 的问题。这个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 44 路径 地图 软件 如何 计算出 最优 出行 170701297
链接地址:https://www.31doc.com/p-5529927.html