数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想

王争 2018-12-24
我们在第 31 节提到,深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单,但是应用却非常广泛。它除了用来指导像深度优先搜索这种经典的算法设计之外,还可以用在很多实际的软件开发场景中,比如正则表达式匹配、编译原理中的语法分析等。
除此之外,很多经典的数学问题都可以用回溯算法解决,比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等等。既然应用如此广泛,我们今天就来学习一下这个算法思想,看看它是如何指导我们解决问题的。

如何理解“回溯算法”?

在我们的一生中,会遇到很多重要的岔路口。在岔路口上,每个选择都会影响我们今后的人生。有的人在每个岔路口都能做出最正确的选择,最后生活、事业都达到了一个很高的高度;而有的人一路选错,最后碌碌无为。如果人生可以量化,那如何才能在岔路口做出最正确的选择,让自己的人生“最优”呢?
我们可以借助前面学过的贪心算法,在每次面对岔路口的时候,都做出看起来最优的选择,期望这一组选择可以使得我们的人生达到“最优”。但是,我们前面也讲过,贪心算法并不一定能得到最优解。那有没有什么办法能得到最优解呢?
2004 年上映了一部非常著名的电影《蝴蝶效应》,讲的就是主人公为了达到自己的目标,一直通过回溯的方法,回到童年,在关键的岔路口,重新做选择。当然,这只是科幻电影,我们的人生是无法倒退的,但是这其中蕴含的思想其实就是回溯算法。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(101)

  • 纯洁的憎恶
    回溯算法本质上就是枚举,优点在于其类似于摸着石头过河的查找策略,且可以通过剪枝少走冤枉路。它可能适合应用于缺乏规律,或我们还不了解其规律的搜索场景中。

    作者回复: 👍

    2018-12-24
    1
    104
  • slvher
    0-1 背包问题的回溯实现技巧:

    第 11 行的递归调用表示不选择当前物品,直接考虑下一个(第 i+1 个),故 cw 不更新

    第 13 行的递归调用表示选择了当前物品,故考虑下一个时,cw 通过入参更新为 cw + items[i]

    函数入口处的 if 分支表明递归结束条件,并保证 maxW 跟踪所有选择中的最大值
    2018-12-24
    2
    67
  • G.S.K
    0-1背包问题根据老师下边这句话的讲解,代码再加两行注释就非常容易理解了

    我们可以把物品依次排列,整个问题就分解为了 n 个阶段,每个阶段对应一个物品怎么选择。先对第一个物品进行处理,选择装进去或者不装进去,然后再递归地处理剩下的物品。

    public int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
    // cw 表示当前已经装进去的物品的重量和;i 表示考察到哪个物品了;
    // w 背包重量;items 表示每个物品的重量;n 表示物品个数
    // 假设背包可承受重量 100,物品个数 10,物品重量存储在数组 a 中,那可以这样调用函数:
    // f(0, 0, a, 10, 100)
    public void f(int i, int cw, int[] items, int n, int w) {
      if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
        if (cw > maxW) maxW = cw;
        return;
      }
      f(i+1, cw, items, n, w); //当前物品不装进背包
      if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候,就不要再装了
        f(i+1,cw + items[i], items, n, w); //当前物品装进背包
      }
    }
    2019-03-03
    32
  • 纯洁的憎恶
    0-1背包的递归代码里第11行非常巧妙,它借助回溯过程,实现了以每一个可能的物品,作为第一个装入背包的,以尝试所有物品组合。但如果仅按从前向后执行的顺序看,是不太容易发现这一点的。
    2018-12-24
    1
    23
  • www.xnsms.com小鸟接码
    看不懂背包问题代码同学,请好好仔细看看下面这句话,再结合代码你就看懂了

    我们可以把物品依次排列,整个问题就分解为了 n 个阶段,每个阶段对应一个物品怎么选择。先对第一个物品进行处理,选择装进去或者不装进去,然后再递归地处理剩下的物品。

    作者回复: 👍

    2019-01-06
    2
    22
  • Shawn
    0-1背包问题理解:
    假设三个物品,每个物品在考虑时有两种选择,1-放进包,0-不放
    11行代码表示不放进包里。13行代码表示放进包里。
    三个物品遍历过程如下:
    0 0 0 update maxW
    0 0 1 update maxW
    0 1 0 update maxW
    0 1 1 update maxW
    1 0 0 update maxW
    1 0 1 update maxW
    1 1 0 update maxW
    1 1 1 update maxW

    作者回复: 👍

    2019-05-30
    18
  • 传说中的成大大
    今天又读了一遍这个文章,又写一遍八皇后,写的更快,更流畅,背包和正则匹配的代码也理解得更透彻了
    2018-12-27
    1
    11
  • siegfried
    回溯就是暴力枚举的解法吧?遍历所有情况,当满足情况就停止遍历(剪枝)。

    作者回复: 是的

    2018-12-24
    11
  • Monday
    8皇后以前提到就觉得难懂,今天硬着头皮去写,竟虽然难还是写出来了。多写多写多写
    2018-12-25
    8
  • 猫头鹰爱拿铁
    总觉得背包问题11行代码应该写在14行后,那个if条件后面。
    2018-12-28
    7
  • 叶明
    老师,你好,背包问题,貌似只记录了可以放进去的最大值,没有记录放进最大值对应的放法,我稍微
    改了下,算出了最大值对应的所有放法,不知道可行不,希望老师回复下。
    private int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
        // 下标表示物品序号,值表示是否放进背包:1放,0不放
        private int[] currentAnswer;
        //存储所有解(map key表示放进去的重量,value表示对应重量的物品放法),
        //最终所有最优解为bestAnswerMap.get(maxW)
        private Map<Integer, List<int[]>> bestAnswerMap = new HashMap();

        // cw 表示当前已经装进去的物品的重量和;i 表示考察到哪个物品了;
        // w 背包重量;items 表示每个物品的重量;n 表示物品个数
        // 假设背包可承受重量 100,物品个数 10,物品重量存储在数组 a 中,那可以这样调用函数:
        // f(0, 0, a, 10, 100)
        public void f(int i, int cw, int[] items, int n, int w) {
            if(currentAnswer == null){
                currentAnswer = new int[n];
            }

            if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
                if (cw >= maxW) {
                    maxW = cw;
                    int[] bestAnswer = new int[currentAnswer.length];
                    for(int j=0; j<currentAnswer.length; j++){
                        bestAnswer[j] = currentAnswer[j];
                    }
                    if(bestAnswerMap.containsKey(cw)){
                        bestAnswerMap.get(cw).add(bestAnswer);
                    }else{
                        List<int[]> list = new ArrayList<int[]>();
                        list.add(bestAnswer);
                        bestAnswerMap.put(cw, list);
                    }
                }
                return;
            }
            currentAnswer[i] = 0;
            f(i+1, cw, items, n, w);
            if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候,就不要再装了
                currentAnswer[i] = 1;
                f(i+1,cw + items[i], items, n, w);
            }
        }

    最终maxW 对应的所有最优解为bestAnswerMap.get(maxW)
    2019-01-30
    1
    6
  • AllenGFLiu
    8皇后的Python代码是按照争哥的JAVA代码翻译的,写完之后并没有深刻的理解“回溯”这个动作发生在哪里,后来在微信公众小灰上又看了一遍图解,决定debug跑一下。
    借助着VSCode显示出来的递归栈终于明白了“回溯”是怎么执行的。
    简单来说,当前几个循环皇后按照要求站好位之后,已经产生了对应数量的递归栈,此时一致是递归中的递,当走到当前循环时检查发现 一行中8个位置检查isOK都是false时,栈顶的cal8queens这个函数就结束了,这个时候就该递归中的归了,所以就回到上一行,为该行的皇后换另外一个符合条件的位置,这就是所谓的枚举搜索啊。
    我太高兴了,哈哈。
    2019-08-27
    5
  • Joker
    老师,我经过查资料,找到,其实判断是否在一条斜线上还有更加简便的做法,就是如果行互减的绝对值等于列互减的绝对值,那么就是在一条斜线上的。
    if (Math.abs(row - i) == Math.abs(column - result[i])) {
                    return false;
                }

    作者回复: 是的,我写的时候也查过资料。

    2019-02-01
    4
    4
  • 传说中的成大大
    我今天也把8皇后写出来了 虽然是第一次

    作者回复: 写多了你就会发现 这玩意贼简单

    2018-12-25
    4
  • peng
    八皇后我一开始一直没想明白一个问题,就是每当print一种结果之后,并没有重置result数组,那再穷举下一种结果时,result中的脏数据会影响到isOK()函数的判断吗?
    经过一番调试思考后,发现我的担心多余了。每次穷举下一种结果时,都会在上一种结果的基础上进行穷举,所以result中<row之前的结果都是有用的,不是脏数据, 也不应该清掉它。
    而isOK()每次都寻找正上,左上,右上的占用结果进行判断,因此result中>=row的结果也不会影响到isOK()的判断,很快就可能被后续的穷举重新设置,遂而形成新的穷举结果。
    有这些疑问只能说明我对递归回溯理解得还不到位,只能通过一步步调试来寻找答案
    2019-08-03
    3
  • Geek_bd613f
    看完这篇文章,写了个求n位逐位整除数的题,发现剪枝技巧其实在考虑题目限制条件时自然就用上了,比如背包问题会判断weigh<背包最大载重,如果不判断,递归到最后就不能直接取maxW了,因为这个值可能超过背包最大载重。
    2019-06-19
    3
  • 饺子
    流程大概就是:
    第一个不放,第二个不放,……,第n-1个不放,第n个不放。
    第一个不放,第二个不放,……,第n-1个不放,
    第n个放。
    第一个不放,第二个不放, ……,第n-1个放,
    第n个不放。
    第一个不放,第二个不放, ……,第n-1个放,
    第n个放。
    ……
    以此类推
    感觉这些问题就是将概率论知识转化成代码实现。
    2019-02-23
    3
  • Kudo
    0-1背包python实现:
    maxW = -1 # tracking the max weight

    def backpack(i, cw, items, w):
        '''
        # i: the ith item, integer
        # cw: current weight, integer
        # items: python list of item weights
        # w: upper limit weight the backpack can load
        '''
        global maxW
        
        if cw==w or i==len(items): # base case
            if cw > maxW:
                maxW = cw
            return
        
        # There are 2 states, traverse both!!!
        backpack(i+1, cw, items, w) # do not choose
        if (cw + items[i] <= w):
            backpack(i+1, cw+items[i], items, w) # choose
        
    # how to use
    items = [2, 2, 4, 6, 3]
    backpack(0, 0, items, 10)
    print(maxW)
    2018-12-27
    3
  • 森码
    今天正好发现一个算法的示例,大家结合看看,应该能更好的理解https://algorithm-visualizer.org/backtracking/n-queens-problem
    2018-12-27
    3
  • 一个工匠
    难道只有我把回溯理解成多叉树的“后序排序”?
    之所以会回溯,是因为在一个结点,有多个选择,每个选择就是一叉,那多个选择就是多叉。选择一叉后,下一个结点又有多叉。这就是一个多叉树嘛。
    return,就是叶子结点。
    当return的时候,叶子结点访问完了,就要出栈了。依据“后序排序”的规则,开始回到上一个结点的下一叉进行入栈,然后又return了,又出栈了。
    最后,把所有可能性全部遍历了一遍,game over了。
    2019-09-10
    1
    2
收起评论
99+
返回
顶部