一、概念
回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走，直到遍历完所有的走法或获取到想要的结果。
二、应用
1、八皇后问题
八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
js 代码实现：
|
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 |
// 下标表示行，下标里的值表示棋子存放的列 var result = Array.from({length:8}).fill(null); function cal8queens(row) { // 调用方式：cal8queens(0); if (row == 8) { // 8个棋子都放置好了，打印结果 printQueens(result); return; // 8行棋子都放好了，已经没法再往下递归了，所以就return } // 从第一列开始，逐个放置棋子 for (let column = 0; column < 8; ++column) { // 每一行都有8中放法 // 如果满足条件 if (isOk(row, column)) { // 有些放法不满足要求 result[row] = column; // 第row行的棋子放到了column列 cal8queens(row+1); // 考察下一行 } } } // 判断当前行是否可以放置棋子 function isOk(row, column) {//判断row行column列放置是否合适 let leftup = column - 1, rightup = column + 1; for (let 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; } function printQueens(result) { // 打印出一个二维矩阵 for (let row = 0; row < 8; ++row) { var arr = []; for (let column = 0; column < 8; ++column) { if (result[row] == column) arr.push("Q "); else System.out.print("* "); } console.log(arr.join(',')); } } |
辅助理解：假设已经填满第7行的Q，到第8行的时候，如果可以放下一个Q，那么打印这个解。如果不行，那么这个函数call8queens(8)这个函数结束，此时就回到第7行 call8queens(7)，再寻找下一个适合放入Q的位置（上一次放入Q的位置开始），如果找不到，在回到上行，在寻找这一行中适合放入Q的位置；如果能找到，最终也会在第8行的找到一个位置放下Q。不断的循环调用，不断的回归，直到每一行的for循环都结束，所有的解都打印完。
2、0-1 背包问题
问题描述：对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，求背包中可容纳的物品总重量的最大值。为什么叫0-1 背包问题呢，因为对于每一个物品，只有装（1）和不装（0）两种选择。
例如：假设现在有5个物品，各个物品的重量分别为2、3、4、5、6，背包能容纳的最大重量为16，那么我们在总重量为16 的前提下，能装下的最大组合为【2、3、5、6】。
对于0-1背包问题，我们可以采取回溯算法的方法，穷举搜索所有可能的装法，然后找出满足条件的最大值。不过，回溯算法的复杂度比较高，是指数级别的。那有没有什么规律，可以有效降低时间复杂度呢？我们一起来看看：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 回溯算法实现。注意：我把输入的变量都定义成了成员变量。 let int maxW = Integer.MIN_VALUE; // 结果放到maxW中 let weight = [2，2，4，6，3]; // 物品重量 let n = 5; // 物品个数 let w = 9; // 背包承受的最大重量 function package01(i, cw) { // 调用f(0, 0) if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了 if (cw > maxW) maxW = cw; return; } package01(i+1, cw); // 选择不装第i个物品 if (cw + weight[i] <= w) { f(i+1,cw + weight[i]); // 选择装第i个物品 } } |
我们假设背包的最大承载重量是 9。我们有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。如果我们把这个例子的回溯求解过程，用递归树画出来，就是下面这个样子：
|
1 2 3 4 5 6 7 8 |
f(0, 0) / \ / \ f(1, 0) f(1, 2) / \ / \ f(2, 0) f(2, 2) f(2, 2) f(2, 4) .... .... .... .... |
我们发现，像 f(2, 2) 这种情况，会出现两次，并且越是到了后面，重复的情况越多，为了避免重复计算，
我们可以改良一下：
|
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 |
let int maxW = Integer.MIN_VALUE; // 结果放到maxW中 let weight = [2，2，4，6，3]; // 物品重量 let n = 5; // 物品个数 let w = 9; // 背包承受的最大重量 let mem = create2Array(5, 10); // 备忘录，默认值false，第一个值为 n 的大小，第二个为所有物品总的重量 function create2Array(m, n){ var arr = []; for(let i = 0; i < m; i++){ arr.push(Array.from({length: n}).fill(null)); } // 千万不要用下面的方法，所有的嵌套数组都是同一个对象，下面的方法可以考虑扩展运算符[...arr2] // var arr = []; // var arr2 = Array.from({length: n}).fill(null); // for(let i = 0; i < m; i++){ // arr.push(arr2); // } return arr; } function package01(i, cw) { // 调用f(0, 0) if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了 if (cw > maxW) maxW = cw; return; } // 重复状态 if (mem[i][cw]) return; // 千万注意上面的 return，他不是整个方法调用结束，它的意思是假如我们之前已经处理过一次f(2,2)的情况 // 以上面的图举例，当我们再次执行f(2,2)的时候，不用计算，直接return了，接着执行f(2,4)， // 那么就省掉了f(2, 2) 及 f(2, 2)后面的所有计算 mem[i][cw] = true; // 记录(i, cw)这个状态 // 从节省空间的角度考虑，mem[i][cw] 可以使用对象的方式，把 i 和 cw 拼接成一个唯一的key，如 obj[i + '_' + cw] = true package01(i+1, cw); // 选择不装第i个物品 if (cw + weight[i] <= w) { package01(i+1, cw + weight[i]); // 选择装第i个物品 } } |
辅助理解：对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2^n 种，去掉总重量超过 Wkg 的，从剩下的装法中选择总重量最接近 Wkg 的。不过，我们如何才能不重复地穷举出这 2^n 种装法呢？这里就可以用回溯的方法。我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
3、正则表达式的匹配
我假设正则表达式中只包含 “*” 和 “?” 这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“*” 匹配任意多个（大于等于 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 |
let matched = false; let pattern = []; // 正则表达式 let plen; // 正则表达式长度 function rmatch(ti, pj, text, 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); } } function match(text, tlen) { // 文本串及长度 matched = false; rmatch(0, 0, text, tlen); return matched; } |
发表评论