Java面试知识点（九十二）搜索与回溯算法-Java实现

一、概述

1.定义

• 搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。

• 它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

• 如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

2.算法框架

int search(int k){
    for(int i=1;i<=算符种类;i++){
        if(符合条件){
            保存条件
            if (到目的地) 输出结果
            else search(k + 1);
            回溯，把保存的结果回退
        }
    }
}

二、示例

1.矩阵寻径

【题目】
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串 “bcced” 的路径，但是矩阵中不包含 “abcb” 路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

【代码】

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

    /**
     * 个人思路：
     * 1.把一维数组变成二维数组，并额外设置一个标记数组，用来判断是否已经经过
     * 2.构建一个位移数组，分别代表上下左右的移动，注意边界的判断
     * */



    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {

        // 标记数组
        boolean[][] flag = new boolean[rows][cols];
        // 存储为二维数组
        char[][] max = new char[rows][cols];
        for (int i=0; i<rows; i++) {
            for(int j=0; j<cols; j++) {
                max[i][j] = matrix[cols*i + j];
            }
        }

        for (int i=0; i<rows; i++) {
            for(int j=0; j<cols; j++) {
                if (search(0,max,i,j,rows,cols,str,flag)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 构建位移数组,0,1,2,3分别代表上、右、下、左
    int[][] move ={{-1,0},{0,1},{1,0},{0,-1}};

    // 搜索回溯
    public boolean search(int n, char[][] max, int i, int j, int rows, int cols, char[] str, boolean[][] flag) {
        // 当前的字符与矩阵中的某个位置的字符相同
        if (str[n] == max[i][j] && !flag[i][j]) {
            flag[i][j] = true;
            // 到达终点
            if (str.length-1 == n) {
                return true;
            }
            //  上下左右没有越界
            if (i-1 >= 0  && search(n + 1, max, i - 1, j, rows, cols, str, flag)) {
                return true;
            }
            if (j+1 < cols && search(n + 1, max, i, j+1, rows, cols, str, flag)) {
                return true;
            }
            if (i+1 < rows && search(n + 1, max, i+1, j, rows, cols, str, flag)) {
                return true;
            }
            if (j-1 >= 0 && search(n + 1, max, i, j-1, rows, cols, str, flag)) {
                return true;
            }
            flag[i][j] = false;
        }
        return false;
    }

PS:关于递归方法的一些思考
如果递归方法的返回值是boolean类型，那么，把递归方法作为判断条件来返回是较好的选择，具体例子见上述方法递归的使用。