回溯算法

发表于 | 分类于 | 阅读次数:

回溯的算法题，之前也遇到过，但是每次都没有仔细研究，这几天做 剑指offer 的题中，又再次遇到了回溯，于是打算这一次能够将他弄明白

概述

常用解释

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点

许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法的美称

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束

题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子

举例

如在下图矩阵中包含一条字符串 bcced 的路径，但是矩阵中不包含 abcb 路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子

1
2
3
a	b	c	e
s	f	c	s
a	d	e	e

思路

这道题可以采用回溯算法来做，我们可以以矩阵中每一个点为起始点，当有一个点与字符串中第一个字符相等，即可继续前进，接下来去搜索该节点的上下左右节点，如果有任意一个节点和字符串中接下来的字符相等时，即继续前进；否则返回到之前的节点，再重新搜索。

代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class BackTracking {
    /**
     * @param matrix 输入的矩阵
     * @param rows   矩阵行数
     * @param cols   矩阵列数
     * @param str    将要搜索的字符串
     * @return 是否找到    是：true 否：false
     */
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        //参数校验
        if (matrix == null || matrix.length != rows * cols || rows < 1 || cols < 1 || str.length < 1 || str == null) {
            return false;
        }
        //定义boolean型矩阵，用来标识路径是否进入某个格子
        boolean[] visited = new boolean[rows * cols];
        //记录结果，作为str字符串的角标
        int pathLength = 0;
        //以每一个点为起始进行搜索
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {

                //给每个格子初始值赋为负值
                memset(visited, false);

                if (hasPathCore(matrix, rows, cols, str, i, j, visited, pathLength)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @param matrix     输入的矩阵
     * @param rows       矩阵总行数
     * @param cols       矩阵总列数
     * @param str        需要查找的str字符串
     * @param row        当前处理的矩阵行号
     * @param col        当前处理的矩阵列号
     * @param visited    访问标记数组
     * @param pathLength 已经处理str字符串的个数
     * @return 是否找到    是：true 否：false
     */
    private static boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, int row, int col, boolean[] visited, int pathLength) {
        //判断：如果检测到了数组的最后一位，可以直接返回true
        if(pathLength == str.length)
            return true;

        boolean hasPath = false;

        if (row < rows && col < cols && col >= 0 && row >= 0 &&
                matrix[row * cols + col] == str[pathLength] && !visited[row * cols + col]) {

            visited[row * cols + col] = true;
            pathLength++;

            // 按照上下左右回溯
            hasPath = hasPathCore(matrix, rows, cols, str, row, col - 1, visited, pathLength)
                    || hasPathCore(matrix, rows, cols, str, row - 1, col, visited, pathLength)
                    || hasPathCore(matrix, rows, cols, str, row, col + 1, visited, pathLength)
                    || hasPathCore(matrix, rows, cols, str, row + 1, col, visited, pathLength);

            if (!hasPath) {
                --pathLength;
                visited[row * cols + col] = false;
            }
        }
        return hasPath;
    }

    /**
     * 给boolean型数组赋值
     *
     * @param booleans 数组
     * @param bool     赋值
     */
    private static void memset(boolean[] booleans, boolean bool) {
        for (int i = 0; i < booleans.length; i++) {
            booleans[i] = bool;
        }
    }

}

测试

为了方便测试，使用了 Junit 来进行测试，不得不说，真好用啊！！

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
import org.junit.Test;

public class BackTrackingTest {
    @Test
    public void test1() {
        char[] matrix = new char[]{'a', 'b', 'c', 'e',
                's', 'f', 'c', 's', 'a', 'd', 'e', 'e'};
        char[] str = new char[]{'b', 'f', 'c', 'e'};

        boolean bool = BackTracking.hasPath(matrix, 3, 4, str);
        System.out.println(bool);
    }

    @Test
    public void test2(){
        String matrix = "asdfzxcvqwer";
        String str = "sxzq";

        boolean bool = BackTracking.hasPath(matrix.toCharArray(), 3, 4, str.toCharArray());
        System.out.println(bool);
    }

    @Test
    public void test3(){
        String matrix = "";
        String str = "sxzq";

        boolean bool = BackTracking.hasPath(matrix.toCharArray(), 0, 0, str.toCharArray());
        System.out.println(bool);
    }

    @Test
    public void test4(){
        String matrix = "qwerasdfzxcv";
        String str = "qwsw";

        boolean bool = BackTracking.hasPath(matrix.toCharArray(), 0, 0, str.toCharArray());
        System.out.println(bool);
    }
}