程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23440 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

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

黄申 2019-01-16
你好,我是黄申。
我们经常使用手机上的地图导航 App,查找出行的路线。那计算机是如何在多个选择中找到最优解呢?换句话说,计算机是如何挑选出最佳路线的呢?
前几节,我们讲了数学中非常重要的图论中的概念,图,尤其是树中的广度优先搜索。在广度优先的策略中,因为社交网络中的关系是双向的,所以我们直接用无向边来求解图中任意两点的最短通路。
这里,我们依旧可以用图来解决这个问题,但是,影响到达最终目的地的因素有很多,比如出行的交通工具、行驶的距离、每条道路的交通状况等等,因此,我们需要赋予到达目的地的每条边不同的权重。而我们想求的最佳路线,其实就是各边权重之和最小的通路。
我们前面说了,广度优先搜索只测量通路的长度,而不考虑每条边上的权重。那么广度优先搜索就无法高效地完成这个任务了。那我们能否把它改造或者优化一下呢?
我们需要先把交通地图转为图的模型。图中的每个结点表示一个地点,每条边表示一条道路或者交通工具的路线。其中,边是有向的,表示单行道等情况。其次,边是有权重的。
假设你关心的是路上所花费的时间,那么权重就是从一点到另一点所花费的时间;如果你关心的是距离,那么权重就是两点之间的物理距离。这样,我们就把交通导航转换成图论中的一个问题:在边有权重的图中,如何让计算机查找最优通路?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(17)

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

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

    2019-01-17
    4
  • caohuan
    黄老师 说的老长了,如果给我们讲个故事 听得会更有趣。
    记得 《大话数据结构》里面有说到 广度优先和深度优先算法里,作者 用找东西的例子,广度优先是 到各个地方 比如每个房价 扫一眼,如果没有 再慢慢深入到角落,深度优先 就是 因为有个大概记忆,然后 跟随 记忆 从一个房间 比如抽屉开始 寻找,没有 再去最有可能的角落 找寻,所以 广度优先是 把所有的地方快速扫一眼,没有再慢慢进入小范围 区域,深度优先 就是去指定位置 寻找。
    本篇的 Dikstra 大概可以理解:把计算好的节点放入黑箱里,有新的节点加入 只需要与 箱子 的节点连接,然后把新节点与箱子中临近的节点连接起来,计算新节点与临近节点的距离,更新最值,已有的节点间的距离不需要重复计算,总之 Dikstra算法 是没有重复的计算,所以效率会很高,总的计算量会少很多,不像深度优先算法 有大量重复的计算,广度优先算法在添加新节点 时 也会更新已有的计算。
    所以Dijstra模块化的思想很节能,它包括 1.寻找MW的最小值或者最大值;2.update更新新节点时,再计算MW的最值。

    回答老师的问题:问题一,权限值可以为正为负,例子:跑车游戏中,获胜方为规定时间内奔跑的路程最多,规则为 路线中有不同 奖励,其中有多增加时间的道路,也有减少跑车时间的路线,就是权限值 有正有负。
    问题二:多条优先路线,照样可以运用Dijkstra算法,把 多条路线 同时与接入 新节点,然后计算距离,算出MW的值。

    有个问题 请教老师:一般地图搜索场景使用Dijkstra多一点还是 动态规划多一点,还是其他算法,地图可以用 百度地图、Google地图 举例。

    老师 在专栏里 会谈到 机器学习算法 在生活和产品中的运用吗?

    作者回复: 你的建议很好,我后面会注意用更形象的方式来讲解。

    至于边的权重,至少在目前的Dijkstra算法中,权重必须是正的。因为只有正的,我们才可以不去考虑已经进入F集合的结点。这个在证明过程中也提到了为什么。

    一般地图搜索还是用Dijkstra偏多,当然也有一些优化的算法。

    最后,我在后面两大模块讲解时,也会使用工作中实际的案例,加强学习的体验。

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

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

    2019-04-08
    1
  • null
    老师好,Dijkstra算法讲解第二步似乎有问题,你在判定C为到S最近的点后,没有更新到D的距离,D不应该是0.4而是0.3
    另外思考题第一题我认为不能使用这个算法,因为最小权重并不是绝对的,有可能后面一个负数的权重,直接改变所有F集合中的值了
    第二题,我认为可以同时执行判断,将两个点都加入F,同时更新两点所有直连点的w,如果有点同时链接这2个点,在做判断
    不知是否正确

    作者回复: 首先,两道思考题回答得很棒,思路都是正确的。

    然后,关于你说的推导问题,我又看了看原文的图,边是有向的,不过是从d到c,而不是从c到d。如果从c到d,那么就如你所说的那样。

    2019-01-17
    1
  • 南边
    有一个地方需要注意一下,应该有两个mw的映射,一个是findGeoWithMinWeight用的(这是个临时映射tempMw),用完了需要把找到的最小mw移除tempMw映射,否则findGeoWithMinWeight永远都只能找到那个固定的最小值(例子里是c点),另一个是已确定的mw映射(是结果映射resultMw),在updateWeight时候需要获取上一步的最小总权重值和更新到已确定的resultMw映射中

    作者回复: 很细致的点👍

    2019-10-31
  • Paul Shan
    总结
    广度优先:按照队列逐渐发现未知的点,遍历的顺序按照和源顶点的边数从小到大遍历。
    深度优先:按照栈逐渐发现未知的点,遍历的顺序类似于树的后序遍历,先深入腹地,逐级后退。
    最小距离遍历:按照距离的堆逐渐发现未知的点,遍历的顺序安装距离单调递增遍历所有点。
    2019-08-27
  • Paul Shan
    思考题2
    对于存在相同距离的情况下,更新权重的时候只更新距离减小的情况,选择最小的时候,最小的有多个,随便选一个就好。
    2019-08-27
  • Paul Shan
    思考题1
    边如果有负数,这个方法就不可用了,因为这个方法在证明的时候用了增强归纳,也就是第k远的点必定经过前k-1远的节点外加一条边,一旦引入负数边以后,这点就不成立了,因为完全可以用k-1远的节点外加n条边。
    这个方法之所以能成立,用到了一个隐含假设,可达的所有顶点中,存在边数最短的点距离距离也最短,其他点的距离是通过距离较短的点计算出来的。

    作者回复: 没错

    2019-08-27
  • 钠镁铝硅磷😒
    之前看过好几次dijkstra的文章,但是每次都感觉只是一知半解,过会又忘了,看完老师的这篇文章,算是真正弄明白了dijkstra算法的原理,给老师点个赞!
    除了地图导航之外,在网络中路由表的生成使用的也是dijkstra算法。

    作者回复: 很高兴这个专栏对你有用

    2019-07-02
  • tangerine
    caohuan 同学的脑子很乱, 要多看问题,多思考一些严谨的思路, 沉下心来! 老师来龙去脉说的很清楚!
    2019-04-18
  • qinggeouye
    # python 实现
    https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/15_theShortestPath/lesson15_1.py

    # 实现效果
    用户 0 的好友: [5], 权重值 [0.42]
    用户 1 的好友: [4, 9, 0, 6, 3], 权重值 [0.99, 0.16, 0.2, 0.6, 0.1]
    用户 2 的好友: 不存在
    用户 3 的好友: 不存在
    用户 4 的好友: [2, 5, 3], 权重值 [0.17, 0.03, 0.03]
    用户 5 的好友: [7], 权重值 [0.19]
    用户 6 的好友: [4], 权重值 [0.38]
    用户 7 的好友: [8, 1], 权重值 [0.86, 0.63]
    用户 8 的好友: [7, 3], 权重值 [0.8, 0.19]
    用户 9 的好友: [1], 权重值 [0.97]

    ------------- Dijkstra 单源最短路径算法 --------------
    各下标节点对应的前驱节点: [1, None, 4, 1, 6, 0, 1, 5, 7, 1]
    ------------- 源点 1 到其它各节点的最短路径 ----------
    源点 1 到 0 的最短路径:1 -> 0
    源点 1 到 1 的最短路径:不存在
    源点 1 到 2 的最短路径:1 -> 6 -> 4 -> 2
    源点 1 到 3 的最短路径:1 -> 3
    源点 1 到 4 的最短路径:1 -> 6 -> 4
    源点 1 到 5 的最短路径:1 -> 0 -> 5
    源点 1 到 6 的最短路径:1 -> 6
    源点 1 到 7 的最短路径:1 -> 0 -> 5 -> 7
    源点 1 到 8 的最短路径:1 -> 0 -> 5 -> 7 -> 8
    源点 1 到 9 的最短路径:1 -> 9
    2019-03-03
  • 失火的夏天
    Dijkstra好像是基于贪心算法的思想,因为老师用数学归纳法证明了贪心选择可以得到最优,但是出现了负数,就不满足贪心选择了,算法思路应该就变成了动态规划

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

    2019-01-30
  • 会飞的猪
    a=node('a',{'b':0.2,'c':0.3})
    b=node('b',{'d':0.2,'f':0.3})
    c=node('c',{'d':0.4,'e':0.1})
    d=node('d',{'e':0.3})
    e=node('e',{'f':0.2})
    f=node('f',{})
    mw={}
    lastMw={}
    nolist={'a':a,'b':b,'c':c,'d':d,'e':e,'f':f}
    def getLastNode(mw,lastMw):
        last=min(mw, key=mw.get)
        print('获取到mw最小值',last)
        lastMw[last]=mw[last]

        for k,v in nolist[last].son.items():
            newMw=v+mw[last]
            if k in mw:
                if newMw<mw[k]:
                    mw[k]=newMw
            else:
                mw[k] = newMw
        mw.pop(last)

        if mw:
            getLastNode(mw,lastMw)
        return lastMw
    acc=getLastNode(a.son,lastMw)
    print(acc)
    结果输出:
    获取到mw最小值 b
    获取到mw最小值 c
    获取到mw最小值 d
    获取到mw最小值 e
    获取到mw最小值 f
    {'b': 0.2, 'c': 0.3, 'd': 0.4, 'e': 0.4, 'f': 0.5}
    2019-01-25
  • 菩提
    // 执行测试
    public static void main(String[] args) {
    Node tree = init();
    Map<String, Double> mw = new HashMap<>();
    Map<String, Double> result_mw = new HashMap<>();

    List<Node> children = tree.children;
    Map<String, Double> weights = tree.weights;
    for (Map.Entry<String, Double> entry : weights.entrySet()) {
    mw.put(entry.getKey(), entry.getValue());
    }

    while (mw.size() != 0) {
    String label = findGeoWithMinWeight(mw);
    updateWeight(label, mw.get(label), result_mw);
    Node min = getMinNode(children, label);
    System.out.println("获取最小值:" + label);
    List<Node> nodes = min.children;
    if (nodes != null && nodes.size() > 0) {
    children.addAll(nodes);
    for (Node node : nodes) {
    mw.put(node.label, BigDecimal.valueOf(result_mw.get(label))
    .add(BigDecimal.valueOf(min.weights.get(node.label))).doubleValue());
    }
    }
    mw.remove(label);
    }

    System.out.println(result_mw);
    }
    }

    运行结果如下:
    获取最小值:c
    获取最小值:b
    获取最小值:d
    获取最小值:f
    获取最小值:a
    获取最小值:c
    获取最小值:f
    获取最小值:e
    获取最小值:g
    获取最小值:h
    获取最小值:g
    {a=0.5, b=0.3, c=0.2, d=0.4, e=0.5, f=0.4, g=0.6, h=0.6}

    作者回复: 细节注意的很好,点赞👍

    2019-01-20
  • 菩提
    children = new ArrayList<>();
    children.add(e);
    children.add(h);
    weights = new HashMap<>();
    weights.put("e", 0.1);
    weights.put("h", 0.2);
    f.children = children;
    f.weights = weights;

    children = new ArrayList<>();
    children.add(g);
    weights = new HashMap<>();
    weights.put("g", 0.4);
    h.children = children;
    h.weights = weights;

    return start;
    }

    children = new ArrayList<>();
    children.add(e);
    children.add(h);
    weights = new HashMap<>();
    weights.put("e", 0.1);
    weights.put("h", 0.2);
    f.children = children;
    f.weights = weights;

    children = new ArrayList<>();
    children.add(g);
    weights = new HashMap<>();
    weights.put("g", 0.4);
    h.children = children;
    h.weights = weights;

    return start;
    }

    // 获取最小权重
    public static String findGeoWithMinWeight(Map<String, Double> mw) {
    double min = Double.MAX_VALUE;
    String label = "";
    for (Map.Entry<String, Double> entry : mw.entrySet()) {
    if (entry.getValue() < min) {
    min = entry.getValue();
    label = entry.getKey();
    }
    }
    return label;
    }

    // 更新权重
    public static void updateWeight(String key, Double value, Map<String, Double> result_mw) {
    if (result_mw.containsKey(key)) {
    if (value < result_mw.get(key)) {
    result_mw.put(key, value);
    }
    } else {
    result_mw.put(key, value);
    }
    }

    // 获取最小节点
    public static Node getMinNode(List<Node> l, String label) {
    for (Node node : l) {
    if (label.equals(node.label)) {
    return node;
    }
    }
    return null;
    }
    2019-01-20
  • 菩提
    1.思考题,如果权重为负数,Dijkstra算法的方式就不能用了。您在文中也提到了,每次取到最小的mw,如果后面出现负数,那前面的权重就不能保证最小了。如果存在多条最优路径,则应该加一个字段记录节点从开始到结束的轨迹。如果权重有多个最优解,则运行轨迹才是需要求解的结果,而不是权重。

    2.我将您讲解的推导过程用代码实现了,为了避免小数位数计算导致的精度问题,先转为BigDecimal,再转成了double.由于留言区字数限制,我分开进行提交。
    public class Lesson15 {

    // 定义节点
    static class Node {
    public String label;
    public List<Node> children;
    public Map<String, Double> weights;

    public Node(String label) {
    this.label = label;
    }
    }

    // 初始化
    public static Node init() {
    Node start = new Node("s");
    Node a = new Node("a");
    Node b = new Node("b");
    Node c = new Node("c");
    Node d = new Node("d");
    Node e = new Node("e");
    Node f = new Node("f");
    Node g = new Node("g");
    Node h = new Node("h");

    List<Node> children = new ArrayList<>();
    children.add(a);
    children.add(b);
    children.add(c);
    children.add(d);
    Map<String, Double> weights = new HashMap<>();
    weights.put("a", 0.5);
    weights.put("b", 0.3);
    weights.put("c", 0.2);
    weights.put("d", 0.4);
    start.children = children;
    start.weights = weights;

    children = new ArrayList<>();
    children.add(e);
    weights = new HashMap<>();
    weights.put("e", 0.3);
    a.children = children;
    a.weights = weights;

    children = new ArrayList<>();
    children.add(a);
    children.add(f);
    weights = new HashMap<>();
    weights.put("a", 0.2);
    weights.put("f", 0.1);
    b.children = children;
    b.weights = weights;

    children = new ArrayList<>();
    children.add(f);
    children.add(h);
    weights = new HashMap<>();
    weights.put("f", 0.4);
    weights.put("h", 0.8);
    c.children = children;
    c.weights = weights;

    children = new ArrayList<>();
    children.add(c);
    children.add(h);
    weights = new HashMap<>();
    weights.put("c", 0.1);
    weights.put("h", 0.6);
    d.children = children;
    d.weights = weights;

    children = new ArrayList<>();
    children.add(g);
    weights = new HashMap<>();
    weights.put("g", 0.1);
    e.children = children;
    e.weights = weights;
    2019-01-20
  • strentchRise
    第二张图,也就是基于距离的有向有权重的图,难道不可以用递归的分而治之来做么?
    每次找出距离我最近的前方节点,这样似乎不用缓存到某节点的最小距离了吧?

    作者回复: 我理解你说的递归分治是深度优先搜索?如果是这样,也是可以的,但是某个结点会被访问多次,效率不高。另外,当前结点的最小距离还是要缓存的,因为最终需要知道起始点到某个结点的最小距离

    2019-01-17
收起评论
17
返回
顶部