程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 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讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?

黄申 2019-01-14
你好,我是黄申。
上一讲,我们通过社交好友的关系,介绍了为什么需要广度优先策略,以及如何通过队列来实现它。有了广度优先搜索,我们就可以知道某个用户的一度、二度、三度等好友是谁。不过,在社交网络中,还有一个经常碰到的问题,那就是给定两个用户,如何确定他们之间的关系有多紧密?
最直接的方法是,使用这两人是几度好友来衡量他们关系的紧密程度。今天,我就这个问题,来聊聊广度优先策略的一种扩展:双向广度优先搜索,以及这种策略在工程中的应用。

如何更高效地求两个用户间的最短路径?

基本的做法是,从其中一个人出发,进行广度优先搜索,看看另一个人是否在其中。如果不幸的话,两个人相距六度,那么即使是广度优先搜索,同样要达到万亿级的数量。
那究竟该如何更高效地求得两个用户的最短路径呢?我们先看看,影响效率的问题在哪里?很显然,随着社会关系的度数增加,好友数量是呈指数级增长的。所以,如果我们可以控制这种指数级的增长,那么就可以控制潜在好友的数量,达到提升效率的目的。
如何控制这种增长呢?我这里介绍一种“双向广度优先搜索”。它巧妙地运用了两个方向的广度优先搜索,大幅降低了搜索的度数。现在我就带你看下,这个方法的核心思想。
假设有两个人 。我们首先从 出发,进行广度优先搜索,记录 的所有一度好友 ,然后看点 是否出现在集合 中。如果没有,就再从 出发,进行广度优先搜索,记录所有一度好友 ,然后看 是否出现在 的并集中。如果没有,就回到 ,继续从它出发的广度优先搜索,记录所有二度好友 ,然后看 是否出现在 三者的并集中。如果没有,就回到 ,继续从它出发的广度优先搜索。如此轮流下去,直到找到 的好友和 的好友的交集。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(14)

  • elephant
    如果a和b好友分布极不均匀,比如a和a的所有子好友平均都有100个好友,b和b的所有子好友平均有2个好友,这样的情况下,从b开始的单向搜索要高效很多吧

    作者回复: 是的

    2019-01-19
    16
  • 菩提
    完善了一下这两个预留的方法
    private static boolean hasOverlap(HashSet<Integer> visited_a, HashSet<Integer> visited_b) {
    if (visited_a.isEmpty() || visited_b.isEmpty())
    return false;
    for (int user_id_a : visited_a) {
    if (visited_b.contains(user_id_a)) {
    return true;
    }
    }
    return false;
    }

    private static void getNextDegreeFriend(int user_id_a, Node[] user_nodes, Queue<Integer> queue_a,
    HashSet<Integer> visited_a, int degree_a) {
    if (user_nodes[user_id_a] == null)
    return;
    Node current_node = user_nodes[user_id_a];
    HashSet<Integer> friends = current_node.friends;
    if (friends.isEmpty())
    return;
    HashMap<Integer, Integer> degrees = current_node.degrees;
    for (int f_user_id : friends) {
    queue_a.offer(f_user_id);
    visited_a.add(f_user_id);
    degrees.put(f_user_id, degree_a + 1);
    }
    }
            // 初始化节点数组
    public static Node[] init(int user_num, int relation_num) {
    Random rand = new Random();
    Node[] user_nodes = new Node[user_num];

    // 生成所有表示用户的节点
    for (int i = 0; i < user_num; i++) {
    user_nodes[i] = new Node(i);
    }

    // 生成所有表示好友关系的边
    for (int i = 0; i < relation_num; i++) {
    int friend_a_id = rand.nextInt(user_num);
    int friend_b_id = rand.nextInt(user_num);
    if (friend_a_id == friend_b_id)
    continue;
    Node friend_a = user_nodes[friend_a_id];
    Node friend_b = user_nodes[friend_b_id];
    friend_a.friends.add(friend_b_id);
    friend_b.friends.add(friend_a_id);
    }

    return user_nodes;
    }
            // 测试
    public static void main(String[] args) {
    Node[] user_nodes = init(5, 8);
    for (Node d : user_nodes) {
    System.out.println(d.user_id + ":" + d.friends + ":" + d.degrees);
    }
    System.out.println("-----------------");
    int len = bi_bfs(user_nodes, 0, 1);
    System.out.println("距离:" + len);
    }
    运行结果:
    0:[2, 3, 4]:{0=0}
    1:[2, 4]:{1=0}
    2:[0, 1]:{2=0}
    3:[0]:{3=0}
    4:[0, 1]:{4=0}
    -----------------
    距离:2

    老师您帮忙看下程序逻辑有没有什么问题,从测试结果来看应该是对的。

    作者回复: 逻辑上是对的👌

    2019-01-16
    5
  • Wing·三金
    思考题:能想到的是当 a b 结点的好友数量极度不对称时,单向更快;优化思路是,每一次迭代时比较下一层结点的数量,若是两边的数量级有明显差距(设置个阈值),则优先选择数量级小的一边进行搜索。但这样的做的弊端也很明显——很可能这一边不断往下搜索,但事实上另一边只要往下一层就完事了。所以还需要限制单边【连续优先搜索】的次数。

    提问:老师,您有开头提到需要对 Node 添加一个 degrees 的 HashMap 变量来纪录其他用户结点与 self 的距离,但是后边用到的外部变量 degree_a 事实上就代替了这个功能是吗?
    另外在实际应用中 max_degree 是设置为树的高度吗,还是可以有其他优化方式?

    作者回复: 思考题的思路很好。
    degree_a和degree_b主要是控制总的度数(也就是max_degree),不要搜索太多。

    至于HashMap,是考虑到了不同节点到出发点的最短距离。

    2019-03-25
    1
  • 风轨
    "双向广度优先比单向广度优先更高效"的前提条件是"两个被搜索的节点必须是联通的"如果不是联通的,两个节点都会将他们各自的N度好友都找出来,不如只搜索其中一个;
    针对这种情况可以维护一个网络分块信息表,每当有连接加入这个网络时检查一下它是否将两个分割的块连接起来了,如果是将这两个块标记为同一个块。在查找的时候就方便了,如果两个节点本身就不在一个块里面,距离直接就是无穷远。但是如果这个网络里面的连接还能删除的话就比较麻烦了,每删除一条边还要检查是否将一个块分割成了两个块,计算量比较大。

    作者回复: 考虑到了网络的动态改变,这个思路很赞👍

    2019-01-30
    1
  • 一页遮目
    要想实现双向广度优先搜索,首先我们要把结点类 Node 稍作修改,增加一个变量 degrees。这个变量是 HashSet 类型。
    老师上面应该讲错了,degrees是HashMap类型

    作者回复: 感谢指正

    2019-12-05
  • teddytyy
    度数小的情况,单向广度优先更有效

    作者回复: 是的

    2019-12-05
  • Geek_zy
    感觉单向可以看作O(n^2)指数级别的增长 双向的更趋近于O(2*n)的增长

    作者回复: 从数量级来看是相同的,但是实际差别还是很大

    2019-10-24
  • qinggeouye
    https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/14_breadthFirstSearch/lesson14_1.py

    两个预留方法的 python 实现:

    get_next_degree_friend(user_nodes, que, visited) 去掉了 user_id_a 和 degree_a 两个参数。
    如果把 user_id_a 看作圆心,它的一度好友看作第一层节点,二度好友看作第二层节点 .... ,que 队列只保留某一层的节点即可,visited 仍保存所有访问过的节点。

    def get_next_degree_friend(user_nodes, que, visited):
        """
        :param user_nodes: 用户节点网络
        :param que: 某一层用户节点 即第几度好友
        :param visited: 已访问的所有用户节点
        :return:
        """
        que_return = queue.Queue() # 只保存某个用户的第几度好友
        visited_return = set() # 保存从某个用户开始到第几度好友
        while not que.empty():
            current_user_id = que.get()
            if user_nodes[current_user_id] is None:
                continue
            for friend_id in user_nodes[current_user_id].friends:
                if user_nodes[friend_id] is None:
                    continue
                if friend_id in visited:
                    continue
                que_return.put(friend_id)
                visited_return.add(friend_id) # 记录已经访问过的节点
        return que_return, visited_return

    def has_overlap(visited_a, visited_b):
        # 两个 set() 的交集
        return len(visited_a & visited_b) > 0

    #测试结果:
    if __name__ == "__main__":
        user_nodes_list = set_user_relation(10, 20)
        for i in range(len(user_nodes_list)):
            print("用户 %s 的好友: %s" % (user_nodes_list[i].user_id, user_nodes_list[i].friends))
        print("---------双向广度优先搜索---------")
        print("两个用户节点 1和2 之间的最短路径长度:", bi_bfs(user_nodes_list, 1, 2))

    用户 0 的好友: {8, 2, 3, 6}
    用户 1 的好友: {8, 3, 5}
    用户 2 的好友: {0, 4}
    用户 3 的好友: {0, 1, 4, 5, 8, 9}
    用户 4 的好友: {2, 3}
    用户 5 的好友: {9, 3, 6, 1}
    用户 6 的好友: {0, 8, 5}
    用户 7 的好友: {9}
    用户 8 的好友: {0, 1, 3, 6, 9}
    用户 9 的好友: {8, 3, 5, 7}
    ---------双向广度优先搜索---------
    两个用户节点 1和2 之间的最短路径长度: 3

    作者回复: 思路是对的,使用set实现代码也很简洁

    2019-02-25
  • Joe
    最后一个图没有看明白,图和计算结果对不上吧。不应该是5000+100+100+300吧

    作者回复: 计算“公司”那一层是,一开始还是需要100 * 5个计数器,之后才会取前1个,也就是100*1。对于“同事”那一层同理

    2019-01-23
  • 🌞🇨🇳👦
    文中描述交替看两边是否有交集的段落,b,b{1}是否出现在a,a{1},a{2},是不是没有必要呢,因为前面已经判断了a,a{1}不在b,b{1}的并集中,是不是只需判断b,b{1}是否出现在a{2}即可

    作者回复: 很好的观察👍 这样确实可以在实现的时候进行优化

    2019-01-22
  • 蒋宏伟
    代码布局有些错乱

    作者回复: 后面会整理代码的Github,供大家参考

    2019-01-21
  • 永旭
    老师 ,在哪里能看 getNextDegreeFriend 和 hasOverlap 的代码 ?

    作者回复: 因为篇幅的关系,原文没有给出,我会在第一大部分结束后,整理一个GitHub。请关注加餐栏目,到时会给出链接。

    2019-01-15
  • Being
    老师,我理解的双向广度优先搜索,其实重点关注的是两个点之间的联系(最短距离),而不是中间所有的覆盖关系。单向的必然导致大规模的覆盖搜索,像地毯式的,而双向的,不会把面积铺得那么大,在一定范围内找到交集即达到目的。所以也从侧面印证了,当关系网的规模很大的时候,使用双向的搜索覆盖面积必然比单向的小很多,而规模小反而不能体现双向BFS的优势。

    作者回复: 是的,规模小不能体现双向优势。另外,如果两个出发点a和b,如果a出发的图平均连接度明显大于b出发的图,那么从b单向广度可能效率更高。

    2019-01-15
  • 草原上的奔跑
    双向广度优先搜索应该是两个点要联通吧,感觉这是一个前提条件。图论这块内容,已经触及到我的盲区了,但是建立在这之上的内容很重要,深度搜索和广度搜索都是向一个资深程序员迈进要走的路。虽然走的时候很痛苦,但依然坚持,我喜欢看到路尽头的彩虹。

    作者回复: 对,前提要连通,否则就无解了。编码的时候可以加个判断,路径长度是否已经超出一个的阈值,或者是否有新的结点发现,可以防止代码在两者不连通的情况下,陷入死循环。

    2019-01-15
收起评论
14
返回
顶部