程序员的数学基础课
黄申
LinkedIn 资深数据科学家
83374 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 58 讲
导读 (1讲)
基础思想篇 (18讲)
程序员的数学基础课
15
15
1.0x
00:00/00:00
登录|注册

15 | 从树到图:如何让计算机学会看地图?

保证搜索的覆盖率
传播最小权重
避免重复无效访问
Finish
min_weight
weight
source
提前获得最终解
计算复杂度高
避免回路
无法高效完成任务
最短通路
边的权重
道路交通状况
行驶距离
交通工具
为什么每次都要选择最小的mw?
为什么每次都要看x直接相连的结点?
为什么每次都要选择最小的mw?
Dijkstra算法的主要步骤
核心思想
遍历所有可能的路线
广度优先搜索
寻找耗时最短的路线
求解最佳路线
影响因素
广度优先搜索
思考题
小结
一个优化的版本:Dijkstra算法
基于广度优先或深度优先搜索的方法
地图导航问题
图论概念
从树到图:如何让计算机学会看地图?

该思维导图由 AI 生成,仅供参考

你好,我是黄申。
我们经常使用手机上的地图导航 App,查找出行的路线。那计算机是如何在多个选择中找到最优解呢?换句话说,计算机是如何挑选出最佳路线的呢?
前几节,我们讲了数学中非常重要的图论中的概念,图,尤其是树中的广度优先搜索。在广度优先的策略中,因为社交网络中的关系是双向的,所以我们直接用无向边来求解图中任意两点的最短通路。
这里,我们依旧可以用图来解决这个问题,但是,影响到达最终目的地的因素有很多,比如出行的交通工具、行驶的距离、每条道路的交通状况等等,因此,我们需要赋予到达目的地的每条边,不同的权重。而我们想求的最佳路线,其实就是各边权重之和最小的通路。
我们前面说了,广度优先搜索只测量通路的长度,而不考虑每条边上的权重。那么广度优先搜索就无法高效地完成这个任务了。那我们能否把它改造或者优化一下呢?
我们需要先把交通地图转为图的模型。图中的每个结点表示一个地点,每条边表示一条道路或者交通工具的路线。其中,边是有向的,表示单行道等情况;其次,边是有权重的。
假设你关心的是路上所花费的时间,那么权重就是从一点到另一点所花费的时间;如果你关心的是距离,那么权重就是两点之间的物理距离。这样,我们就把交通导航转换成图论中的一个问题:在边有权重的图中,如何让计算机查找最优通路?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

利用图论中的算法解决地图导航中的最优路线问题是一项重要的技术挑战。本文重点介绍了Dijkstra算法的原理和应用。Dijkstra算法通过选择最小权重结点和更新权重来寻找最优路径,避免了对某些结点的重复无效访问,从而提升了搜索的效率。文章通过数学归纳法证明了Dijkstra算法可以找到任意两点之间的最小权重通路,为读者提供了深入理解该算法的思路。此外,文章还提到了Dijkstra算法在不同权重设置下的灵活应用,如寻找最短时间、最低价格等最优路径。最后,作者提出了两个思考题,引发读者对算法的进一步思考和讨论。通过本文的总结,读者可以快速了解Dijkstra算法的核心思想和应用,以及其在解决最优路线问题中的优势。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《程序员的数学基础课》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(29)

  • 最新
  • 精选
  • Being
    思考1: 如果边权值为负数就不能使用Dijkstra了,因为该算法是贪心算法,即每步都找最优解,在当前步的最优基础上找下一步最优,一定是单调递增的,而出现负权边,这样的前提就不满足了。 而且也不能有带负权值的环,这个样就会一直找当前最优,而且总是满足。 思考2:就在找最小值时返回最小值集合,更新集合内所有点的直连边权值的最小值,且把集合点都加入F。 (by the way这张封面图挺好看的🙂)

    作者回复: 回答思路很清晰,封面要感谢编辑帮忙 :)

    2019-01-17
    3
    14
  • 失火的夏天
    Dijkstra好像是基于贪心算法的思想,因为老师用数学归纳法证明了贪心选择可以得到最优,但是出现了负数,就不满足贪心选择了,算法思路应该就变成了动态规划

    作者回复: Dijkstra是贪心,还是动态规划,确实有些不同意见。我个人觉得Dijkstra不算是贪心,因为贪心算法往往无法得到最优解,胜在简单和效率。而Dijkstra是可以找到最优的。我觉得Dijkstra更接近动态规划

    2019-01-30
    3
    13
  • 梦倚栏杆
    负数也可以吧,我们取负数的最小值,然后所有边全部加上这个负数的最小值,转换一下不就可以了吗?

    作者回复: 如果全都是负数也是可以的,只要保证单调性。如果同时有正有负就不行了,无法保证单调性,没法按照Dijkstra算法的方式进行优化。

    2019-04-08
    2
    8
  • caohuan
    黄老师 说的老长了,如果给我们讲个故事 听得会更有趣。 记得 《大话数据结构》里面有说到 广度优先和深度优先算法里,作者 用找东西的例子,广度优先是 到各个地方 比如每个房价 扫一眼,如果没有 再慢慢深入到角落,深度优先 就是 因为有个大概记忆,然后 跟随 记忆 从一个房间 比如抽屉开始 寻找,没有 再去最有可能的角落 找寻,所以 广度优先是 把所有的地方快速扫一眼,没有再慢慢进入小范围 区域,深度优先 就是去指定位置 寻找。 本篇的 Dikstra 大概可以理解:把计算好的节点放入黑箱里,有新的节点加入 只需要与 箱子 的节点连接,然后把新节点与箱子中临近的节点连接起来,计算新节点与临近节点的距离,更新最值,已有的节点间的距离不需要重复计算,总之 Dikstra算法 是没有重复的计算,所以效率会很高,总的计算量会少很多,不像深度优先算法 有大量重复的计算,广度优先算法在添加新节点 时 也会更新已有的计算。 所以Dijstra模块化的思想很节能,它包括 1.寻找MW的最小值或者最大值;2.update更新新节点时,再计算MW的最值。 回答老师的问题:问题一,权限值可以为正为负,例子:跑车游戏中,获胜方为规定时间内奔跑的路程最多,规则为 路线中有不同 奖励,其中有多增加时间的道路,也有减少跑车时间的路线,就是权限值 有正有负。 问题二:多条优先路线,照样可以运用Dijkstra算法,把 多条路线 同时与接入 新节点,然后计算距离,算出MW的值。 有个问题 请教老师:一般地图搜索场景使用Dijkstra多一点还是 动态规划多一点,还是其他算法,地图可以用 百度地图、Google地图 举例。 老师 在专栏里 会谈到 机器学习算法 在生活和产品中的运用吗?

    作者回复: 你的建议很好,我后面会注意用更形象的方式来讲解。 至于边的权重,至少在目前的Dijkstra算法中,权重必须是正的。因为只有正的,我们才可以不去考虑已经进入F集合的结点。这个在证明过程中也提到了为什么。 一般地图搜索还是用Dijkstra偏多,当然也有一些优化的算法。 最后,我在后面两大模块讲解时,也会使用工作中实际的案例,加强学习的体验。

    2019-01-22
    4
  • 拉普达
    1.纯负数可以,否则不行。留言里那个所有权重加上最小负数绝对值的方法,没有考虑到路径中边的条数是不一样的。 2.如果有多条代价相等的最短路径,需要第二步修改,记录mw[y]=mw[x]+w(x,y)的解

    作者回复: 我理解留言里说的是所有的边权重都加上一个值,让所有权重的数值往坐标轴右移,直到没有负数。 第2点是可以的👍

    2020-03-28
    3
  • 跳刀躲梅肯
    文章最后这段话,”有的时候,边的权重越大越好,比如观光车开过某条路线的车票收入。对于这种情况,Dijkstra 算法就需要调整一下,每次找到最大的 mw,更新邻近结点时也要找更大的值“,应该是有问题的,Dijkstra算法不能用于求最长路径。

    作者回复: 确实是,因为车票是单调递增的,而不是递减,如果边上的权重都是负的,那么才能求最大值。我让编辑帮忙修改

    2020-07-02
    1
  • 杨芸芸
    1、如果权重全为负值,可以使用Dijstra算法;如果有正有负则不可以,Dijstra算法的基础是通路的权重和是单调递增的,这样才能排除一个个节点。 2、修改方法:求出mv中所有值最小节点,将其一起排除和更新他们的直接连接节点mv值

    作者回复: 是的,可以通过合理的方式,将负的值转化为正的值

    2023-02-02归属地:湖北
  • 张祈璟
    Dijkstra算法提出的最重要的一点:如果存在一个结点x,到它周边的所有结点中存在一个最小权值的点y,这个点x到点y的最优路径必是该路径。 不可能还存在其他x到y的最小路径,原因是其他的路径在一开始已经大于了该路径。

    作者回复: 是的

    2021-06-15
  • Geek_13e8db
    “第三,假设结点 s 能直接到达的边集合为 M,对于其中的每一条边 m,则把 mw[m]设为 w[s, m]” 我认为这里应该将“每一条边m”,改为“每一个对端节点m”

    作者回复: 对,这样描述更准确

    2020-06-28
  • 建强
    思考题1: 如果边的权重是负数,运用Dijksta算法得到是任意两个点之间的最大距离,因为负数比较时,绝对值越大则其值越小,因此算法运行后,两个点之间距离的绝对值是这两个点的最大距离。 思考题2: 存在多条路径情况下,算法修改如下: (1)增加一个一维数组,path,存贮从源点到各个节点的最优路径数,path[i],即表示从源点S到节点i的最优路径数,除源节点path[s]=1外,其余各个节点的路径数都初始化为0。 (2)每当新加入一个节点i,则path[i]的值加1。 (3)每当新加入一个节点i,除了更新权重数组MW,还要对F集合中的节点进行检查,对于F中的某个节点k,如果有mw[i] + mw[i,k] = mw[k],则说明从源点S到节点k至少存在着两条最优权重的路径,因此path[k]也要加1 最后path数组中即为源点到各节点的最优路径数。

    作者回复: 如果有负数是不能直接相加的

    2020-01-18
收起评论
显示
设置
留言
29
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部