devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

回溯法：回溯法通用模版汇总以及模版应用_回溯模板

作者：小桥流水78 | 2024-08-22 01:01:19

赞

踩

回溯模板

从一个问题开始

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]

很容易想到 用两个for循环就可以解决。

如果n为100，k为50呢，那就50层for循环，是不是开始窒息。

此时就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来！

回溯法的本质

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下(但最坏时间复杂度一般来说还是2^n)，还没有更高效的解法。

搜索空间： 子集树

比如简单背包问题的解空间，本质就是一个满二叉树，只不过会通过剪枝避免暴力得出所有可能的解。

这里介绍的模版不会在求解时进行剪枝，因为本人认为这会让一个模版变得较为复杂，可能达到真正意义上的“通用性”，而是在获取到所有可能的解之后再按题目的要求进行筛选。

回溯法:0-1背包问题-CSDN博客

其中两个可行解为：

<0,1,1,1>:x_1=0,x_2=1,x_3=1,x_4=1\\ <1,0,1,0>:x_1=1,x_2=0,x_3=1,x_4=0

一个回溯法模版回顾

参考文章：代码随想录

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  6.  
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

 这个模版使用最大的难点就是如何写出终止条件，在递归过程中来存放结果往往会使得这个模版用起来较为困难。所以接下来介绍的模版是直接拿到所有的解之后再按条件进行筛选

暴力回溯法的模版

亮点在于容易写出来，缺点在回溯中没有用到剪枝，最好最坏时间复杂度都为2^n

本质就是拿到一个高为N的树所有的叶子结点

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4.  
  5. public class KnapsackProblem1 {
  6.     static List<List<Integer>> result = new ArrayList<>();
  7.     //path记录所有的可能,最后结果总共个数必定为2^N
  8.     static LinkedList<Integer> path = new LinkedList<>();
  9.     //N代表着问题规模的大小,即2^N,最终的叶子结点个数就是2^N
  10.     static int N = 4;
  11.  
  12.     public static void main(String[] args) {
  13.         backtracking();
  14.     }
  15.  
  16.     public static void backtracking() {
  17.         if (path.size() == N) {
  18.             //找到了一个叶子结点，就保存下来
  19.             //就算这个叶子结点是不满足题目的要求也保存下来
  20.             result.add(new ArrayList<>(path));
  21.             return;
  22.         }
  23.         //往1走代表选择这个元素
  24.         path.add(1);
  25.         backtracking();
  26.         path.removeLast();
  27.         //往0走代表不选择这个元素
  28.         path.add(0);
  29.         backtracking();
  30.         path.removeLast();
  31.     }
  32. }

易于剪枝的回溯法模版应用

0-1背包问题

 问题描述

给定n种物品和一背包。 物品i的重量是w_i， 其价值为v_i，背包的容量为 c。 问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？注意物品不重复!

实例：物品价值V={12, 11, 9, 8}, 物品重量W={8, 6, 4, 3}, 背包容量c=13

结点：向量(x_1,x_2,...,x_k) （ 子集的部分特征向量）

搜索空间： 子集树，2^n片树叶

其中两个可行解为：

<0,1,1,1>:x_1=0,x_2=1,x_3=1,x_4=1\\ <1,0,1,0>:x_1=1,x_2=0,x_3=1,x_4=0

实现代码

终止条件代码

  1. public static void backtracking(int n,  int startIndex) {
  2.     if (startIndex>=n){
  3.         //此时startIndex越界了
  4.         if (getPathSum()<=c){
  5.             result.add(new ArrayList<>(path));
  6.             return;
  7.         }
  8.         return;
  9.     }
  10.     //再加后面任意一个就肯定不够了
  11.     if (getPathSum()<=c&&(getPathSum() + items_min_weight[startIndex]) > c) {
  12.         //        if (getPathSum()<c) {
  13.         result.add(new ArrayList<>(path));
  14.         return;
  15.     }
  16.     for (int i = startIndex; i < n; i++) {
  17.         path.add(i);
  18.         backtracking(n,  i + 1);
  19.         path.removeLast();
  20.     }

最终代码(含注释)

需要注意的是这里的可行，是再加上未选中的任意一项就>背包容量C

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4.  
  5. public class KnapsackProblem {
  6.     static List<List<Integer>> result = new ArrayList<>();
  7.     static LinkedList<Integer> path = new LinkedList<>();
  8.  
  9.     static int N = 4;
  10.     //    static int[] items_weight = new int[N];
  11.     static int[] items_weight = {8, 6, 4, 3};
  12.     //    static int[] items_value = new int[N];
  13.     static int[] items_value = {12, 11, 9, 8};
  14.     //每个items_min_weight(对应下标为i)的值为min{items_weight[i],...,items_weight[N-1]}
  15.     static int[] items_min_weight = new int[N];
  16.     //c为背包的容量
  17.     static int c=13;
  18.  
  19.     public static void main(String[] args) {
  20.         items_min_weight[N - 1] = items_weight[N - 1];
  21.         int min = items_min_weight[N - 1];
  22.         for (int i = items_weight.length - 2; i >= 0; i--) {
  23.             if (items_weight[i] < min) {
  24.                 min = items_weight[i];
  25.             }
  26.             items_min_weight[i] = min;
  27.         }
  28.         backtracking(N,  0);
  29.         System.out.println("可行解有:");
  30.         result.forEach(System.out::println);
  31.         //要是想求最优解,直接对每个可行解对应重量求和,之后取最大一个就好啦
  32.     }
  33.  
  34.     public static void backtracking(int n,  int startIndex) {
  35.         if (startIndex>=n){
  36.             //此时startIndex越界了
  37.             if (getPathSum()<=c){
  38.                 result.add(new ArrayList<>(path));
  39.                 return;
  40.             }
  41.             return;
  42.         }
  43.         //再加后面任意一个就肯定不够了
  44.         if (getPathSum()<=c&&(getPathSum() + items_min_weight[startIndex]) > c) {
  45.             //        if (getPathSum()<c) {
  46.             result.add(new ArrayList<>(path));
  47.             return;
  48.         }
  49.         for (int i = startIndex; i < n; i++) {
  50.             path.add(i);
  51.             backtracking(n,  i + 1);
  52.             path.removeLast();
  53.         }
  54.     }
  55.  
  56.     public static int getPathSum() {
  57.         int sum = 0;
  58.         for (int i = 0; i < path.size(); i++) {
  59.             sum += items_weight[path.get(i)];
  60.         }
  61.         return sum;
  62.     }
  63. }

八皇后问题

问题背景

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。

• 问题是：在8×8的棋盘上摆放八个皇后， 使其不能互相攻击， 即任意两个皇后都不能处于同一行、 同一列或同一斜线上。

• n皇后问题：即在n× n的棋盘上摆放n个皇后， 使任意两个皇后都不能处于同一行、 同一列或同一斜线上。

搜索空间:N叉树

4后问题：解是一个4维向量， (x1, x2, x3, x4)（放置列号），这里x1为第一行，x2为第二行，以此类推。

搜索空间： 4叉树

8后问题：解是一个8维向量， (x1, x2, x3, x4, x5, x6, x7, x8)

搜索空间： 8叉树,一个解： <1,3,5,2,4,6,8,7>

问题分析

确定问题状态： 问题的状态即棋盘的布局状态。

构造状态空间树： 状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。

由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有n个子结点

⚫ 设4个皇后为xi， 分别在第i行(i=1， 2， 3， 4)；

⚫ 问题的解状态：可以用(1, x1)， (2, x2)， ……， (4, x4)表示4个皇后的位置；

⚫ 由于行号固定， 可简单记为： (x1, x2, x3, x4)；例如：(4, 2, 1, 3)

⚫ 问题的解空间： (x1, x2, x3, x4)， 1≤xi≤4 (i=1， 2， 3， 4)， 共4! 个状态；

4皇后问题解空间的树结构

约束条件

⚫ 任意两个皇后不能位于同一行上;

⚫ 任意两个皇后不能位于同一列上，所以解向量X必须满足约束条件：i\ne j,x_i\ne x_j

搜索解空间中进行剪枝

（1） 从空棋盘起， 逐行放置棋子。

（2） 每在一个布局中放下一个棋子， 即推演到一个新的布局。

（3） 如果当前行上没有可合法放置棋子的位置，则回溯到上一行， 重新布放上一行的棋子。

以4皇后问题为例

为了简化问题， 下面讨论4皇后问题。4皇后问题的解空间树是一个完全4叉树， 树的根结点表示搜索的初始状态， 从根结点到第2层结点对应皇后1在棋盘中第1行可能摆放的位置， 从第2层到第3层结点对应皇后2在棋盘中第2行的可能摆放的位置， 以此类推。

回溯法求解4皇后问题的搜索过程

n=4的n皇后问题的搜索、 剪枝与回溯

代码思路

参考文章：代码随想录

回溯模板

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  6.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  7.         处理节点;
  8.         backtracking(路径，选择列表); // 递归
  9.         回溯，撤销处理结果
  10.     }
  11. }

递归终止条件

  1. if (row == n) {
  2.     result.push_back(chessboard);
  3.     return;
  4. }

单层搜索的逻辑

  1. for (int col = 0; col < n; col++) {
  2.     if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
  3.         chessboard[row][col] = 'Q'; // 放置皇后
  4.         backtracking(n, row + 1, chessboard);
  5.         chessboard[row][col] = '.'; // 回溯，撤销皇后
  6.     }
  7. }

验证棋盘是否合法

按照如下标准去重：

不能同行(搜索过程从上到下自动解决了这个问题)

不能同列

不能同斜线 （45度和135度角）

实现代码与相关解释

  1. package DaiMaSuiXiangLu;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.List;
  6.  
  7. public class N_queen {
  8.     //res用来存储可能的结果
  9.     static List<List<String>> res = new ArrayList<>();
  11.     public static void main(String[] args) {
  12.         int n = 4;
  13.         //画棋盘n*n
  14.         char[][] chessboard = new char[n][n];
  15.         for (char[] c : chessboard) {
  16.             Arrays.fill(c, '.');
  17.         }
  18.         backTrack(n, 0, chessboard);
  19.         for (int i = 0; i < res.size(); i++) {
  20.             System.out.println("方案"+(i+1));
  21.             for (int j = 0; j < res.get(i).size(); j++) {
  22.                 System.out.println(res.get(i).get(j));
  23.             }
  24.         }
  25.     }
  26.  
  27.     /**
  28.      * @param n          棋盘的大小
  29.      * @param row        当初正在处理哪一行
  30.      * @param chessboard 当前棋盘的状况
  31.      */
  32.     public static void backTrack(int n, int row, char[][] chessboard) {
  33.         if (row == n) {
  34.             //将结果赋给的新的list
  35.             //这是因为List是引用类型，需要每次开辟新的空间给一个新的list来保存结果
  36.             res.add(Array2List(chessboard));
  37.             return;
  38.         }
  39.         for (int col = 0; col < n; ++col) {
  40.             //剪枝操作,暴力点也可以不剪枝，对最后保存下来的多个结果去检查他们的合法性
  41.             //尝试对该行的每一列放置皇后
  42.             if (isValid(row, col, n, chessboard)) {
  43.                 chessboard[row][col] = 'Q';
  44.                 backTrack(n, row + 1, chessboard);
  45.                 chessboard[row][col] = '.';
  46.             }
  47.         }
  48.     }
  49.     //用于生成新的list
  50.     public static List Array2List(char[][] chessboard) {
  51.         List<String> list = new ArrayList<>();
  52.  
  53.         for (char[] c : chessboard) {
  54.             list.add(String.copyValueOf(c));
  55.         }
  56.         return list;
  57.     }
  58.  
  59.     /**
  60.      *
  61.      * @param row 当前递归是在row行,col列放置了一个新的皇后
  62.      * @param col 当前递归是在row行,col列放置了一个新的皇后
  63.      * @param n 棋盘大小
  64.      * @param chessboard 当前棋盘的状况
  65.      * @return 是否违背了合法性
  66.      */
  67.     public static boolean isValid(int row, int col, int n, char[][] chessboard) {
  68.         //行无需检查,因为backTrack的递归保证了每一行只有一个皇后
  69.         // 检查列
  70.         for (int i = 0; i < row; ++i) { // 相当于剪枝
  71.             if (chessboard[i][col] == 'Q') {
  72.                 return false;
  73.             }
  74.         }
  75.         // 检查45度对角线
  76.         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
  77.             if (chessboard[i][j] == 'Q') {
  78.                 return false;
  79.             }
  80.         }
  81.         // 检查135度对角线
  82.         for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
  83.             if (chessboard[i][j] == 'Q') {
  84.                 return false;
  85.             }
  86.         }
  87.         return true;
  88.     }
  89.  
  90. }

暴力回溯法模版应用

组合问题

回到文章开头的问题

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

添加的solveCombinationProblem仅仅是用来筛选满足条件的解

  1. package DaiMaSuiXiangLu;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6.  
  7. public class KnapsackProblem1 {
  8.     static List<List<Integer>> result = new ArrayList<>();
  9.     //path记录所有的可能,最后结果总共个数必定为2^N
  10.     static LinkedList<Integer> path = new LinkedList<>();
  11.     //N代表着问题规模的大小,即2^N,最终的叶子结点个数就是2^N
  12.     static int N = 4;
  13.  
  14.     public static void main(String[] args) {
  15.         //组合问题
  16.         int K = 2;
  17.         solveCombinationProblem(K);
  18.  
  19.  
  20.     }
  21.  
  22.     public static void backtracking() {
  23.         if (path.size() == N) {
  24.             //找到了一个叶子结点，就保存下来
  25.             //就算这个叶子结点是不满足题目的要求也保存下来
  26.             result.add(new ArrayList<>(path));
  27.             return;
  28.         }
  29.         path.add(1);
  30.         backtracking();
  31.         path.removeLast();
  32.         path.add(0);
  33.         backtracking();
  34.         path.removeLast();
  35.     }
  36.     public static void solveCombinationProblem(int k) {
  37.         int time = 0;
  38.         for (int i = 0; i < result.size(); i++) {
  39.             //用来记录该叶子结点中1的个数
  40.             time = 0;
  41.             List<Integer> answer = result.get(i);
  42.             for (int j = 0; j < answer.size(); j++) {
  43.                 if (answer.get(j) == 1) {
  44.                     time++;
  45.                 }
  46.             }
  47.             if (time == k) {
  48.                 for (int j = 0; j < answer.size(); j++) {
  49.                     if (answer.get(j) == 1) System.out.print((j + 1) + " ");
  50.                 }
  51.                 System.out.println();
  52.             }
  53.  
  54.         }
  55.     }
  56. }

0-1背包问题 

用之前回溯法的模版会发现终止条件不好写出来

回溯法:0-1背包问题-CSDN博客

但用该文章推荐的模版很好地解决这个问题

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4.  
  5. public class KnapsackProblem1 {
  6.     static List<List<Integer>> result = new ArrayList<>();
  7.     //path记录所有的可能,最后结果总共个数必定为2^N
  8.     static LinkedList<Integer> path = new LinkedList<>();
  9.     //N代表着问题规模的大小,即2^N,最终的叶子结点个数就是2^N
  10.     static int N = 4;
  11.  
  12.     public static void main(String[] args) {
  13.         backtracking();
  14.         //背包问题
  15.         int[] items_weight={8,6,4,3};
  16.         int[] items_value={12,11,9,8};
  17.         int C=13;
  18.         solveKnapsackProblem(items_weight,items_value,C);
  19.  
  20.     }
  21.  
  22.     public static void backtracking() {
  23.         if (path.size() == N) {
  24.             //找到了一个叶子结点，就保存下来
  25.             //就算这个叶子结点是不满足题目的要求也保存下来
  26.             result.add(new ArrayList<>(path));
  27.             return;
  28.         }
  29.         path.add(1);
  30.         backtracking();
  31.         path.removeLast();
  32.         path.add(0);
  33.         backtracking();
  34.         path.removeLast();
  35.     }
  36.  
  37.     public static void solveKnapsackProblem(int[] items_weight, int[] items_value, int C) {
  38.         //值得注意的是items_weight和items_value的长度都为N
  39.         int sum_weight = 0;
  40.         int sum_value = 0;
  41.         //记录现在能达到的最大价值
  42.         int max_value = -1;
  43.         for (int i = 0; i < result.size(); i++) {
  44.             sum_weight = 0;
  45.             sum_value = 0;
  46.             List<Integer> answer = result.get(i);
  47.             for (int j = 0; j < answer.size(); j++) {
  48.                 if (answer.get(j) == 1) {
  49.                     sum_value += items_value[j];
  50.                     sum_weight += items_weight[j];
  51.                 }
  52.             }
  53.             //不高于背包容量且比之前找到的最大价值还大
  54.             if (sum_weight <= C && sum_value > max_value) {
  55.                 max_value = sum_value;
  56.             }
  57.         }
  58.         System.out.println(max_value);
  59.     }
  60. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/1014050
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号