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 =0. 接下来证明: PriorityQueue出队列的顶点顺序是所有顶点到单源点的最短路径按路径总权重从小到大排列的顺序. Base Case: 第1个出队列的是源点本身, 最短路 径总权重=0为最小（这里就要求所有权重=0，否则base都不成立）. 假设第1, 2, .n次出队列的顶点分别对应最短路径总权重最小的前n个顶点，那么第n+1个 最短路径顶点自然就是在前n个顶点的所有邻接顶点集合中取更新后总距离离源点最小的那个，即堆顶元素. 假如排第n+1的顶点
5、t不是堆顶元素的话，其最短 路径的前驱顶点s必然不在已出队列顶点集合中(否则通过s找到的t就是对顶元素)，但又由于权重(s, t)0, 源点到s的最短距离必然是排前n+1的，则t必须是其前 驱节点s，矛盾. 老师最后举的打分的例子初看上去和最短距离没太大关系，可能是指在这个基于历史状态下的单步迭代策略(DP?)使得全局最优上有点类似吧 . 想当上帝的司机 2019-01-10 00:45:37 if (inqueuenextVertex.id=false)/加了这个判断的话，就不会走2了，因为在走1的时候2已经进入inqueue了，我在本地试的是去掉这个条件结果是对的，不知 道是不是语言的原因
6、，我是用gonlang写的，优先级队列是网上找的一个插件，老师你本地跑是成功的吗 44|最短路径：地图软件是如何计算出最优出行路径的？ file:/F/geektime/ebook/数据结构与算法之美/44最短路径：地图软件是如何计算出最优出行路径的？.html2019/1/22 18:48:23 作者回复2019-01-10 09:59:15 我测试过的 我再多找个数据测试一下 五岳寻仙 2019-01-09 07:23:58 Liam 有问到 Dkijstra 算法是否是贪心算法，求得的解是否是全局最优解。 答案是：它不是贪心算法，事实上它是动态规划算法，求得的解全局最优解。 这个算法很有
7、名，网上有很多帖子，具体可以百度或谷歌。 卡罗 2019-01-08 18:27:42 翻译那个例子没看懂。 纯洁的憎恶 2019-01-07 23:20:46 思考题好发散啊我也开开脑洞吧。 1.可考虑的因素有很多，在此补充一点：如果使用我的导航app用户很多，那么就有可能掌握每条道路通行车辆的实时速度、汽车数量，于是就可以结合道路 长度比较精确的计算出当前通行时间。 2.公交和地铁都有固定线路，与开车、步行情境下的路线有很大不同。如果只考虑公交，可以简化问题为只保留公交车站为顶点，站与站之间为边的有向图 即可。但如果把公交和步行混合起来就复杂了，也行可以考虑公交线路覆盖区域，以车站为顶点、
8、站与站连线为边、边的通勤时间为权重，覆盖不到的区域 以岔路为顶点、道路为边、步行通勤时间为权重，构建有向图。 纯洁的憎恶 2019-01-07 18:33:57 回顾了一下31讲，广度优先算法的过程不难理解，但是广度优先算法遍历无权图中一点s到另一点t的路径，就是它的最短路径，是如何证明的呢？ 你有资格吗？ 2019-01-07 11:44:58 打卡 传说中的成大大 2019-01-07 11:06:46 1. 代码中inqueue声明是 inQueue 2. 感觉有点类似 暴力搜索判断,起始点和截止点的之间的所有结点都考察一遍 slvher 2019-01-07 09:56:43 机器翻译
9、的例子，用于解码的启发式剪枝是 beam search 算法吧？在 NLP 领域序列解码场合有广泛应用，不保证最优解，但通过调整 beam width 参数能得到 工程上可接受的结果 44|最短路径：地图软件是如何计算出最优出行路径的？ file:/F/geektime/ebook/数据结构与算法之美/44最短路径：地图软件是如何计算出最优出行路径的？.html2019/1/22 18:48:23 作者回复2019-01-17 15:08:38 beam search算法不怎么懂，我抽空研究下：） 不过，我的那个算法是可以得到最优解的。 PtricK 2019-01-07 09:25:14 课后思考： 1. 想到一个简单粗暴的，用道路长度/限速作为权重。（实际上算上交通拥堵的话感觉复杂好多，需要去根据当前交通状况判断） 2. 分别取离起点和终点最近的地铁站为s和t，地铁每个站权重为1（也就是无权），类似Dijkstra算法，从s开始搜索，维护一个优先级队列，遇到换乘点则添 加分支。（公交车的如果也用这个想法，每个站都会是换乘点，而且每个换乘点有n个线路 会想用上分区的办法） 魏全运 2019-01-07 09:00:26 vertex compareTo有问题吧，怎么没有相等的分支呀？ 作者回复2019-01-07 09:39:14 有也可以 没有也可以的
个人主页
