从电影《蝴蝶效应》中学习回溯算法的核心思想
共 5795字,需浏览 12分钟
·
2021-06-23 14:39
点击上方“视学算法”,选择加"星标"或“置顶”
重磅干货,第一时间送达
关注我们丨文末赠书
深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单,但应用却 非常广泛。它除用来指导像深度优先搜索这种经典的算法设计之外,还可以用在很多实际的软件开发场景中,如正则表达式匹配、编译原理中的语法分析等。除此之外,很多经典的数学问题也可以用回溯算法解决,如数独、八皇后、0-1背包、图的着色、旅行商、求全排列等。在本文,我们就来学习一下回溯算法思想。
— 01 —
在我们的一生中,会遇到很多重要的“岔路口”。在人生的岔路口,每个选择都会影响我们今后的人生。有的人在每个“岔路口”都能做出正确的选择,生活、事业可能达到了一个很高的高度;而有的人一路选错,最后可能碌碌无为。如果人生可以量化,那么如何才能在人生的岔路口做出正确的选择,让自己的人生“最优”呢?我们可以借助贪心算法,在每次面对人生岔路口的时候,都做出当下看起来最优的选择,期望这一组局部最优选择可以使得我们的人生达到全局“最优”。
但是,贪心算法并不一定能得到最优解。那么,有没有其他办法能得到最优解呢?2004年,著名的电影《蝴蝶效应》上映,该部电影讲的就是主人公为了达到自己的目标,一直通过回溯的方法,回到童年,在关键的人生岔路口,重新做选择。当然,这只是科幻电影,我们的人生是无法倒退的,但这其中蕴含的思想其实就是回溯算法。回溯算法一般用到与“搜索”有关的问题上。不过这里说的搜索,并不是狭义地指图的搜索,而是在一组可能的解中搜索满足期望的解。回溯的处理思想有点类似枚举(或穷举)。
枚举所有的解,找出其中满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段都会面对一个“岔路口”,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个“岔路口”,另选一种走法继续走。
八皇后问题的递归代码实现如下所示:
int[] result = new int[8];//下标表示行,值表示皇后存储在哪一列
public void cal8queens(int row) { //调用方式:cal8queens(0);
if (row == 8) { //8个棋子都放置好了,输出结果
printQueens(result);
return; //8行棋子都放好了,已经没法再往下递归了,因此返回
}
for (int column = 0; column < 8; ++column) { //每一行都有8种放法
if (isOk(row, column)) { //有些放法不满足要求
result[row] = column; //第row行的棋子放到了column列
cal8queens(row+1); //考察下一行
}
}
}
//判断row行、column列放置是否合适
private boolean isOk(int row, int column) {
int leftup = column - 1, rightup = column + 1;
for (int i = row-1; i >= 0; --i) { //逐行往上考察每一行
if (result[i] == column) return false; //第i行、第column列有棋子
if (leftup >= 0) { //考察左上对角线:第i行、第leftup列有棋子吗?
if (result[i] == leftup) return false;
}
if (rightup < 8) { //考察右上对角线:第i行、第rightup列有棋子吗?
if (result[i] == rightup) return false;
}
--leftup; ++rightup;
}
return true;
}
private void printQueens(int[] result) { //输出一个二维矩阵
for (int row = 0; row < 8; ++row) {
for (int column = 0; column < 8; ++column) {
if (result[row] == column) System.out.print("Q ");
else System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
0-1 背包问题
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) {
// cw==w表示装满了;i==n表示已经考察完所有的物品
if (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);
}
}
正则表达式匹配问题
public class Pattern {
private boolean matched = false;
private char[] pattern; //正则表达式
private int plen; //正则表达式的长度
public Pattern(char[] pattern, int plen) {
this.pattern = pattern;
this.plen = plen;
}
public boolean match(char[] text, int tlen) { //文本串及其长度
matched = false
rmatch(0, 0, text, tlen)
;
return matched;
}
private void rmatch(int ti, int pj, char[] text, int tlen) {
if (matched) return; //如果已经匹配,就不要继续递归了
if (pj == plen) { //正则表达式到结尾了
if (ti == tlen) matched = true; //文本串也到结尾了
return;
}
if (pattern[pj] == '*') { //*匹配任意个字符
for (int k = 0; k <= tlen-ti; ++k) {
rmatch(ti+k, pj+1, text, tlen);
}
} else if (pattern[pj] == '?') { //?匹配0个或者1个字符
rmatch(ti, pj+1, text, tlen);
rmatch(ti+1, pj+1, text, tlen);
} else if (ti < tlen && pattern[pj] == text[ti]) { //纯字符匹配才行
rmatch(ti+1, pj+1, text, tlen);
}
}
}
内容小结
点击上图,即可购买《数据结构与算法之美》!
本书结合实际应用场景讲解数据结构和算法,涵盖常用、常考的数据结构和算法的原理讲解、代码实现和应用场景等。
本书分为11章。第1章介绍复杂度分析方法。第2章介绍数组、链表、栈和队列这些基础的线性表数据结构。第3章介绍递归编程技巧、8种经典排序、二分查找及二分查找的变体问题。第4章介绍哈希表、位图、哈希算法和布隆过滤器。第5章介绍树相关的数据结构,包括二叉树、二叉查找树、平衡二叉查找树、递归树和B+树。第6章介绍堆,以及堆的各种应用,包括堆排序、优先级队列、求TopK、求中位数和求百分位数。第7章介绍跳表、并查集、线段树和树状数组这些比较高级的数据结构。第8章介绍字符串匹配算法,包括BF算法、RK算法、BM算法、KMP算法、Trie树和AC自动机。第9章介绍图及相关算法,包括深度优先搜索、广度优先搜索、拓扑排序、Dijkstra算法、Floyd算法、A*算法、最小生成树算法、最大流算法和最大二分匹配等。第10章介绍4种算法思想,包括贪心、分治、回溯和动态规划。第11章介绍4个经典项目中的数据结构和算法的应用,包括Redis、搜索引擎、鉴权限流和短网址服务。
另外,附录A为书中的思考题的解答。尽管本书的大部分代码采用Java语言编写,但本书讲解的知识与具体编程语言无关,因此,本书不但适合各种类型的研发工程师,而且可以作为高校计算机相关专业师生的学习用书和培训学校的教材。
欢迎加入本书读书会社群,打卡学习
点个在看 paper不断!