数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

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

解决广义的搜索问题
剪枝操作提高效率
适合用递归实现
回溯算法思想简单
编译原理中的语法分析
数独、图的着色、旅行商问题等
深度优先搜索
递归实现
分阶段处理字符
问题描述
递归实现
分阶段选择装与不装
问题描述
递归实现
分阶段放置棋子
问题描述
分阶段处理问题
枚举所有可能解
用于搜索问题
简单但广泛应用
总结
应用场景
例子3:正则表达式匹配
例子2:0-1背包问题
例子1:八皇后问题
概述
回溯算法

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

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

如何理解“回溯算法”?

在我们的一生中,会遇到很多重要的岔路口。在岔路口上,每个选择都会影响我们今后的人生。有的人在每个岔路口都能做出最正确的选择,最后生活、事业都达到了一个很高的高度;而有的人一路选错,最后碌碌无为。如果人生可以量化,那如何才能在岔路口做出最正确的选择,让自己的人生“最优”呢?
我们可以借助前面学过的贪心算法,在每次面对岔路口的时候,都做出看起来最优的选择,期望这一组选择可以使得我们的人生达到“最优”。但是,我们前面也讲过,贪心算法并不一定能得到最优解。那有没有什么办法能得到最优解呢?
2004 年上映了一部非常著名的电影《蝴蝶效应》,讲的就是主人公为了达到自己的目标,一直通过回溯的方法,回到童年,在关键的岔路口,重新做选择。当然,这只是科幻电影,我们的人生是无法倒退的,但是这其中蕴含的思想其实就是回溯算法。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

回溯算法是一种重要的搜索算法,通过枚举搜索的方式,在一组可能的解中寻找满足期望的解。本文以八皇后问题和0-1背包问题为例,详细解释了回溯算法的实现过程。通过递归的方式,回溯算法能够有效地解决诸如八皇后问题和0-1背包问题等经典问题。此外,文章还提到了回溯算法在深度优先搜索、正则表达式匹配、编译原理中的语法分析等实际软件开发场景中的应用。回溯算法的思想简单而强大,适用于解决广义的搜索问题,如深度优先搜索、图的着色、旅行商问题、数独、全排列等。文章还提到了回溯算法的剪枝操作,这是提高回溯效率的一种技巧。总的来说,回溯算法虽然简单,但在解决各种实际问题中具有广泛的应用价值。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(229)

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

    作者回复: 👍

    2018-12-24
    15
    348
  • 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
    10
    102
  • siegfried
    回溯就是暴力枚举的解法吧?遍历所有情况,当满足情况就停止遍历(剪枝)。

    作者回复: 是的

    2018-12-24
    4
    70
  • Geek_41d472
    看不懂背包问题代码同学,请好好仔细看看下面这句话,再结合代码你就看懂了 我们可以把物品依次排列,整个问题就分解为了 n 个阶段,每个阶段对应一个物品怎么选择。先对第一个物品进行处理,选择装进去或者不装进去,然后再递归地处理剩下的物品。

    作者回复: 👍

    2019-01-06
    11
    54
  • Joker
    老师,我经过查资料,找到,其实判断是否在一条斜线上还有更加简便的做法,就是如果行互减的绝对值等于列互减的绝对值,那么就是在一条斜线上的。 if (Math.abs(row - i) == Math.abs(column - result[i])) { return false; }

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

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

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

    2018-12-25
    3
    28
  • feifei
    这个回塑问题,老师讲的的理解了,但总感觉还是哪里没有学会,我又说不出来,好像总觉得少了点什么? 老师关于课后的题目,0-1背包,在限制重量与数量的前提下,这个解我觉得其实挺简单的,就是把老师的那个代码稍加改造就OK了 public void countMaxPkg( int index, int sumValue, int sumWeight, PkgValue[] items, int maxNum, int maxWeight) { // 1,如果当前重量到达最大总重量,或者数量达到最达限制,则设置当前最大值 if (index == maxNum || sumWeight == maxWeight) { // 检查总重量是否更重 if (sumMaxWeight < sumWeight) { sumMaxWeight = sumWeight; } // 检查当前价值是否更大 if (maxValue < sumValue) { maxValue = sumValue; } return; } // 针对每个物品,有当前不加入背包中计算价值 countMaxPkg(index + 1, sumValue, sumWeight, items, maxNum, maxWeight); // 当前的最大总重量还是要小于限制值 if (sumWeight + items[index].getWeight() <= maxWeight) { // 针对每个物品,有当前加入背包计算价值 countMaxPkg( index + 1, sumValue + items[index].getValue(), sumWeight + items[index].getWeight(), items, maxNum, maxWeight); } } 完整代码在: https://github.com/kkzfl22/datastruct/blob/master/src/main/java/com/liujun/datastruct/algorithm/backtrackingAlgorithm/packageZoneOne/PackageValue.java 如果有问题,还请老师给予指正,谢谢!

    作者回复: 你是觉得太简单了吧 不敢相信吧

    2018-12-25
    3
    7
  • bucher
    正则匹配这个,*代表匹配任意个任意字符,那只要匹配到* 就可以直接返回matched=true吧,不用再递归了吧

    作者回复: 你说的对,是可以不用递归了。

    2019-11-10
    4
    2
  • 唯她命
    aab c*a*b 正则表达式,能匹配通过,文章的代码通过不了,代码有问题

    作者回复: 你自己搞错了吧,没法通过匹配啊

    2019-02-25
    7
    2
  • NeverMore
    老师思考题应该就是下章的动态规划了吧。

    作者回复: 回溯也能解决的

    2018-12-24
    2
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部