算法笔记-回溯算法

发表于 | 分类于
回溯算法本身除了指导沃算法设计以外，在实际软件开发场景中应用也十分广泛。例如正则表达式的匹配，编译原理中的语法分析等等。

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

如何理解回溯算法

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

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

回溯应用举例

0-1 背包问题

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 存储背包中物品总重量的最大值
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 个）任意字符， ? 匹配零个或者一个任意字符。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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);
		}
	}
}

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

总结

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

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

-------------本文结束感谢您的阅读-------------