这一次,真正理解回溯算法

简介: 回溯算法思想很简单,大部分都是用来解决广义搜索问题:从一组可能解中,选出一个满足要求的解。回溯非常适合用递归实现,剪枝是提高回溯效率的一种技巧,无需穷举搜索所有情况。回溯算法可解决很多问题,如DFS、八皇后、0-1背包、图的着色、旅行商、数独、全排列、正则表达式匹配等。

理解“回溯算法”

若人生可重来,如何才能在岔路口做出最正确选择,让自己的人生“最优”?

贪心算法,在每次面对岔路口的时候,都做出看起来最优的选择,期望这一组选择可以使得我们的人生达到“最优”。但不一定能得到的是最优解。

如何确保得到最优解?

回溯算法很多时候都应用在“搜索”问题:在一组可能解中,搜索期望解。

处理思想,类似枚举搜索:枚举所有解,找到满足期望的解。

为规律枚举所有可能解,避免遗漏、重复,将问题求解过程分为多个阶段。

每个阶段,都要面对一个岔路口,先随意选一条路走,当发现这条路走不通(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。

八皇后

8x8的棋盘,往里放8个棋子(皇后),每个棋子所在的行、列、对角线都不能有另一个棋子。

image.png

把这个问题划分成8个阶段,依次将8个棋子放到第一行、第二行、第三行……第八行。

放置过程中,不停地检查当前方法,是否满足要求

  • 满足
    跳到下一行继续放置棋子
  • 不满足
    换种方法尝试

适合递归实现:

11.png

0-1背包

经典解法是动态规划,但还有简单但没那么高效的回溯解法。

  • 有一背包,背包总承载重量Wkg
  • 有n个物品,每个物品重量不等且不可分割
  • 期望选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,求背包中物品的总重量max?


这个背包问题,物品不可分割,要么装要么不装,所以叫0-1背包,就无法通过贪心解解决了。

  • 对于每个物品来说,都有两种选择,装 or 不装
  • 对于n个物品,就有  2^n 种装法,去掉总重量超过Wkg的,从剩下的装法中选择总重量最接近Wkg的
  • 但如何才能不重复地穷举出这 2^n种装法?

这就能回溯,把物品依次排列,整个问题分解为n个阶段,每个阶段对应一个物品怎么选择;

  • 先对第一个物品进行处理,选择装进去 or 不装进去
  • 再递归处理剩下物品

搜索剪枝的技巧:当发现 已选择物品重量 > Wkg,就停止探测剩下物品。

12.png

正则表达式

假设正表达式中只包含*?通配符且现在规定:

  • * 匹配任意多个(大于等于0个)任意字符
  • ? 匹配0或1个任意字符

如何用回溯算法,判断某给定文本,是否匹配给定的正则表达式?

依次考察正则表达式中的每个字符,当是非通配符时,就直接跟文本的字符进行匹配:

  • 相同
    继续往下处理
  • 不同
    回溯

遇到特殊字符时,就有多种处理方式,如*有多种匹配方案,可匹配任意个文本串中的字符,先随意选择一种匹配方案,然后继续考察剩下字符:

  • 若中途发现无法继续匹配,就回到岔路口,重新选择一种匹配方案,再继续匹配剩下字符。

image.png

总结

回溯算法思想很简单,大部分都是用来解决广义搜索问题:从一组可能解中,选出一个满足要求的解。

回溯非常适合用递归实现,剪枝是提高回溯效率的一种技巧,无需穷举搜索所有情况。

回溯算法可解决很多问题,如DFS、八皇后、0-1背包、图的着色、旅行商、数独、全排列、正则表达式匹配等。

目录
相关文章
|
20天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
20天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
20天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
20天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
20天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
20天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
23天前
|
算法
”回溯算法“框架及练习题
”回溯算法“框架及练习题
33 0