算法思想-回溯

发表于 |

笼统地讲，回溯算法很多时候都应用在“搜索”这类问题上。不过这里说的搜索，并不是狭义的指我们前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。

八皇后问题

在8*8的棋盘上放置8个棋子，并且保证行列，左右对角线上都没有棋子。

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
const result = [];
function cal8queens(row) {
    if (row === 8) {
        printQueens(result);
    }

    // 遍历列，如果符合要求则进入下一行，DFS
    for (let column = 0; column < 8; column++) {
        if (isOk(row, column)) {
            result[row] = column;
            cal8queens(row + 1);
        }
    }
}

function isOk(row, column) {
    let leftup = column - 1;
    let rightup = column + 1;

    for(let i = row - 1; i >= 0; i--) {
        if (result[i] === column) return false; // 同一列有值，失败

        if (leftup >= 0) { // 左对角线有值，失败
            if (result[i] == leftup) return false;
        }
        
        if (rightup < 8) { //  右对角线有值，失败
            if (result[i] == rightup) return false;
        }

        leftup--;
        rightup++;
    }
    return true;
}

function printQueens(result) {
    for (let row = 0; row < 8; row++) {
        let s = "";
        for (let column = 0; column < 8; column++) {
            if (result[row] === column) s += "Q ";
            else s += "* ";
        }
        console.log(s + "\n");
    }
    console.log("-----------\n");
}
cal8queens(0);

0-1背包

我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let maxW = 0; // 存储背包中物品总质量的最大值
// i表示考察到哪个物品了；
// cw 表示当前已经装进去的物品的重量和；
// items 物品重量
// n 物品数量；
// w 背包重量
function f(i, cw, items, n, w) {
    if (cw == w || i == n) { // 装满了或者考察完所有物品
        if (cw > maxW) maxW = cw;
        return;
    }

    // 对于第i个物品，会有装或者不装两种情况
    // 不装第i个物品
    f(i+1, cw, items, n, w);

    // 装第i个物品
    if (cw + items[i] <= w) {
        f(i + 1, cw + items[i], items, n, w);
    }
}

正则表达式

假设正则表达式中只包含“”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“”匹配任意多个（大于等于 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
// ti 第i个text字符
// pj 第i个正则字符
// text 文本
// tlen 文本长度

let matched = false;
const pattern = ""; // 正则
const plen = pattern.length;
function match(ti, pj, text, tlen) {
    if(matched) return;

    if (pj == plen) {
        if (ti === tlen) matched = true;
        return;
    }

    if (pattern[pj] === "*") {
        for (let k = 0; k <= tlen - ti; k ++) {
            match(ti + k, pj + 1, text, tlen);
        }
    } else if (pattern[pj] === "?") {
        // 匹配0个字符
        match(ti, pj+1, text, tlen);

        // 匹配1个字符
        match(ti + 1, pj + 1, text, tlen);
    } else if (ti < tlen && pattern[pj] == text[ti]) {
        match(ti + 1, pj + 1, text, tlen);
    }
}

总结

回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，