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

快来打我* 2021-09-20 23:10 328阅读 0赞

### 一、概述 ###

**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类型，那么，把递归方法作为判断条件来返回是较好的选择，具体例子见上述方法递归的使用。