回溯算法的原理和示例

回溯算法的原理和示例

文章目录

• • 回溯算法的代码模板
  • 组和总和
  • 八皇后问题
  • 黄金矿工

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法的代码模板

private void backtrack("原始参数") {//终止条件(递归必须要有终止条件)if ("终止条件") {//一些逻辑操作（可有可无，视情况而定）return;}for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {//一些逻辑操作（可有可无，视情况而定）//做出选择//递归backtrack("新的参数");//一些逻辑操作（可有可无，视情况而定）//撤销选择}
}

组和总和

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：
所有数字都是正整数。
解集不能包含重复的组合。

public static List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> res = new ArrayList<>();dfs(res, new ArrayList<Integer>(), k, 1, n);return res;
}private static void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {// 终止条件，如果满足这个条件，再往下找也没什么意义了if (list.size() == k || n <= 0) {// 如果找到一组合适的就把他加入到集合list中if (list.size() == k && n == 0)res.add(new ArrayList<>(list));return;}//通过循环，分别遍历9个子树for (int i = start; i <= 9; i++) {// 添加到listlist.add(i);// 递归dfs(res, list, k, i + 1, n - i);// 撤销添加操作ve(list.size()-1);}
}

1. 代码dfs中最开始的地方是终止条件的判断，递归必须要有终止条件。

2. 下面的for循环分别遍历他的9个子节点，注意这里的i是从start开始的，所以有可能还没有9个子树，前面说过，如果从9个数字中选择一个之后，第2次就只能从剩下的8个选择了，第3次就只能从剩下的7个中选择了……

3. 在第20行dsf中的start是i+1，这里要说一下为什么是i+1。比如我选择了3，下次就应该从4开始选择，如果不加1，下次还从3开始就出现了数字重复，明显与题中的要求不符

4. for循环的i为什么不能每次都从1开始，如果每次都从1开始就会出现结果重复，比如选择了[1，2]，下次可能就会选择[2，1]。

5. 为什么要撤销选择。分支污染问题，因为list是引用传递，当从一个分支跳到另一个分支的时候，如果不把前一个分支的数据给移除掉，那么list就会把前一个分支的数据带到下一个分支去，造成结果错误。

八皇后问题

public class NQueens {public static void main(String[] args) {for (List<String> list : solveNQueens(4)) {for (String s : list) {System.out.println(s);}System.out.println();}}public static List<List<String>> solveNQueens(int n) {char[][] chess = new char[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {chess[i][j] = '.';}}List<List<String>> res = new ArrayList<>();resolve(res, chess, 0);return res;}public static void resolve(List<List<String>> res, char[][] chess, int row) {// 递归终止条件if (row >= chess.length) {res.add(construct(chess));}for (int col = 0; col < chess.length; col++) {// 只有当前位置可以放置皇后才能进行下一行，// 否则返回上一层递归执行撤回操作if (valid(chess, row, col)) {chess[row][col] = 'Q';// 进入下一行resolve(res, chess, row+1);// 发现在此处无解，撤回操作chess[row][col] = '.';}}}public static boolean valid(char[][] chess, int row, int col) {// 当前位置上方有没有皇后for (int i = 0; i < row; i++) {if (chess[i][col] == 'Q') {return false;}}// 当前位置左上方有没有皇后for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (chess[i][j] == 'Q') {return false;}}// 当前位置右上角有没有皇后for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {if (chess[i][j] == 'Q') {return false;}}return true;}//把数组转为listprivate static List<String> construct(char[][] chess) {List<String> path = new ArrayList<>();for (int i = 0; i < chess.length; i++) {path.add(new String(chess[i]));}return path;}}

黄金矿工

public class MaximumGold {public static void main(String[] args) {int[][] grid = {{0,6,0},{5,8,7},{0,9,0}};System.out.println(getMaximumGold(grid));}public static int getMaximumGold(int[][] grid) {int res = 0;if (grid == null || grid.length == 0) return 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {//函数dfs是以坐标(i,j)为起点，查找最大路径值res = Math.max(res, dfs(grid, i, j));}}return res;}public static int dfs(int[][] grid, int row, int col) {if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0)return 0;int temp = grid[row][col];grid[row][col] = 0;int right = dfs(grid, row, col + 1);int left = dfs(grid, row, col - 1);int down = dfs(grid, row + 1, col);int up = dfs(grid, row - 1, col);int max = Math.max(left, Math.max(right, Math.max(up, down)));grid[row][col] = temp;//返回最大路径值return grid[row][col] + max;}}