算法笔记-回溯算法

在深度优先算法的总结中，就用到了回溯算法求解。回溯算法本身除了指导沃算法设计以外，在实际软件开发场景中应用也十分广泛。例如正则表达式的匹配，编译原理中的语法分析等等。

如何理解回溯算法

如同走迷宫一样，我们会不断地遇到分叉路口，此时可以随机选择一条路走下去。如果，后续发现这条路走不通，那么我们就返回到分叉路口的选择处，重新选择一条新的路继续走下去，直到走出迷宫。

回溯的处理思想，类似于枚举搜索。我们枚举出所有的解，然后选择其中最优的解。为了有规律的枚举出所有可能的解，避免遗漏和重复，我们把问题的求解分解成多个阶段，每个阶段随机选择一种解法，如果不能求解，就返回到上个阶段选择之初，重现选择另外一种解法。

回溯应用举例

0-1 背包问题

0-1背包问题中，0 与 1 代表的就是选择与否。

假如我们有一个背包，背包的承载重量为 Wkg。现在有 n 个物品，每个物品质量不等，并且物品不可分割。我们期望选出部分物品，使得这些物品质量之和不超过背包的承载重量，并且总质量最大。

在这个过程中，每个物品都面临两种选择：选中与不选中。所以，我们把 n 个物品分成 n 个阶段的选择，每个阶段可以选择放入该物品或者不放入该物品。我们用递归的方法处理每一个阶段。

	// 存储背包中物品总重量的最大值public int maxW = Integer.MIN_VALUE; /*** * @param i  表示任务进行的阶段，考察到哪个物品了* @param cw 表示当前已经装进去的物品的重量和* @param items 数组存放每个物品的质量* @param n   物品的数量* @param w   背包的承载重量*/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);}}

上述代码有详细的注释，足以理解整个过程。需要注意的是，f 方法中抛开递归终止的条件判断以外，后续的逻辑分别执行了物品不放入背包和放入背包的两种情况。

也就是说，算法的是想依然是回溯思想，但是执行的逻辑确是一步到底，分情况执行了所有的选择。所以，我们看到的是代码直接走到最后，没有看到有返回重新选择的步骤。

正则表达式

为了理解方便，该例子中的正则表达式只有两种通配符： * 代表匹配任意多个（大于等于 0 个）任意字符， ? 匹配零个或者一个任意字符。

匹配过程中，如果遇到通配符，意味着我们到了分叉路口，有了多种选择。此时我们先任意选择一种匹配方案，然后继续匹配后续的字符。

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) {// ti + k，选择先匹配 k 个字符rmatch(ti + k, pj + 1, text, tlen);}} else if (pattern[pj] == '?') { // 遇到 ? 通配符，新的分叉路口//匹配 0 个 （选择其中一条路）rmatch(ti, pj + 1, text, tlen);//匹配 1 个 （选择另外一条路）rmatch(ti + 1, pj + 1, text, tlen);} else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行rmatch(ti + 1, pj + 1, text, tlen);}}
}

上述代码有详细的注释，足以理解整个过程。需要特别注意的是，当遇到通配符 * 的时候，代表后续可以匹配任意个字符。也就是说，从该字符到文本结束，任意一段的字符串都可以匹配上，也代表了该分叉路口有许多的路可供选择。

总结

本文创作灵感来源于 极客时间 王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。

初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉

关注本人公众号，第一时间获取最新文章发布，每日更新一篇技术文章。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！