回溯算法第二篇（全排列【基于排列树实现】、旅行售货员问题【基于排列树实现】、N皇后【基于子集树实现的】）

目录1. 全排列2. 旅行售货员问题3. N 皇后1. 全排列全排列力扣链接题目描述给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。示例 1输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2输入nums [0,1]输出[[0,1],[1,0]]示例 3输入nums [1]输出[[1]]提示1 nums.length 6-10 nums[i] 10nums中的所有整数互不相同解决方案如下1首先画出决策树① 开始挖了3个空如分别对这3个问号填入数字可以是各个位置可以是1、2或者3。② 如果第一个位置选1那么第二个位置就不能选1了只能选2和3。第一个位置选2或者3也是同理。③ 总结每个位置都是独一无二的在之前不能出现过的。2设计代码① 设计三个全局变量。int[][] ret 一个二维数组用来存储找到的所有排列结果。int[] path 这个变量用来存储已经选择的结果例如一个排列结果是1,2,3那么 path 数组就存储1,2,3。boolean[] check 这个变量用来实现“剪枝”操作。将已经归入 path 数组的元素设置为true标记为已经使用过不能再次选择。② dfs函数回溯算法的核心注意仅需关系某一个结点在干什么事情。例如在第一次选择可以选择三个元素第二次只能选择两个元素第三次只能选择一个元素这就是每一步需要干的事情。③ 细节问题回溯有两点第一点干掉 path 最后一个元素第二点修改check数组。剪枝递归出口遇到叶子结点的时候直接添加结果。class Solution { //定义全局变量 ret 用来收集结果 ListListInteger ret;//用集合来表示二维数组 ListInteger path;//用来保存每一次结果 boolean[] check;//用来表示某个元素是不是已经被选取过 public ListListInteger permute(int[] nums){ //1.初始化 ret new ArrayList(); path new ArrayList(); check new boolean[nums.length]; //2.调用dfs(回溯的核心) dfs(nums); return ret; } public void dfs(int[] nums){ //1.当path的长度和nums的长度一样那么就是将nums的所有元素已经排列在path里 if(nums.length path.size()){ ret.add(new ArrayList(path)); return; } //每一次都有3个选择只是符不符合的问题 for(int i 0;i nums.length;i){ //正面这个元素还没选取 if(check[i] false){ path.add(nums[i]);//将这个元素添加到数组中 /* check还能这么理解如果一个check的元素为true也就是来到树的第一层看上图有层数注解 有两个check的元素为true也就是来到树的第二层 有三个check的元素为true也就是来到树的第三层 */ check[i] true;//将当前位置的元素标记为true表示已经被选取过了 dfs(nums); check[i] false;//将当前位置改为还未选择具体解析看上图 path.remove(path.size() - 1);//移除最后一个元素 } } } }2. 旅行售货员问题题目描述如下图一个售货员从0号城市出发要到1号、2号、3号这几个城市去推销商品已知各城市之间的路程问应该如何选定一条从0号城市出发经过每个城市一遍最后回到0号城市的路线使得总的周游路程最小如下图所示汉密尔顿回路说白了这就是一个求最短汉密尔顿回路的问题。我们先来了解一下汉密尔顿路径汉密尔顿回路还有汉密尔顿图汉密尔顿路径G (V,E)是一个图若G中一条路径通过且仅通过每一个顶点一次称这条路径为哈密顿路径。汉密尔顿回路若G中一个回路通过且仅通过每一个顶点一次称这个环为哈密顿回路。汉密尔顿图若一个图存在哈密顿回路就称为哈密顿图。解决方案如下1首先画出决策树2代码设计① 设计五个全局变量int[][] ret用来保存结果。boolean[] check用来检查哪个城市已经走过了。int[] path用来记录当前的路径。int[] minPath用来保存最短路径的数组int minValue用来记录最小的总路程② 有如下几个方法public void initGraph()对图进行初始化。public boolean legal()对路径进行初始判断是否合法也就是两个城市zhij。import java.util.ArrayList; import java.util.List; public class Test14 { //定义全局变量 ret 用来收集结果 int N 4; int[] nums {0, 1, 2, 3}; ListListInteger ret;//用集合来表示二维数组 ListInteger path;//用来保存每一次结果 boolean[] check;//用来表示某个元素是不是已经被选取过 ListInteger minPath;//用来保存最短的路径进过的城市 int minValue Integer.MAX_VALUE;//用来保存最短路程 int[][] graph new int[N][N];//用来存储图的路径 //为图初始化 public void addEdge(int v1, int v2, int weight) { graph[v1][v2] graph[v2][v1] weight; } public void initGraph() { addEdge(0, 1, 30); addEdge(0, 2, 6); addEdge(0, 3, 4); addEdge(1, 3, 21); addEdge(2, 3, 11); } public ListListInteger permute(int[] nums) { //1.初始化 ret new ArrayList(); path new ArrayList(); path.add(0); check new boolean[nums.length]; minPath new ArrayList(); //2.调用dfs(回溯的核心) dfs(0, nums); return ret; } //判断路径是否合法 public boolean legal(int index, int n) { int v1 path.get(n);//得到当前城市的前一个城市的数组下标 int v2 index;//当前城市的数组下标 return graph[v1][v2] ! 0 check[index] false; } //判断最后一个城市到达0号城市是否有路径 public boolean legalLast() { int v1 path.get(0); int v2 path.get(path.size() - 1); return graph[v1][v2] ! 0; } public void dfs(int n, int[] nums) { //证明到达了0号城市之前的最后一个城市 if (n nums.length - 1) { //判断最后一个城市到达0号城市是否有路径 if (legalLast()) { ListInteger tmp new ArrayList(); for (int i 0; i path.size(); i) { tmp.add(path.get(i)); } path.add(0); tmp.add(path.get(path.size() - 1)); ret.add(new ArrayList(tmp)); int tmpRoad 0; // tmpRoad 计算本次路程的总和然后和minValue进行比较 for (int i 1; i path.size(); i) { int v1 path.get(i - 1); int v2 path.get(i); tmpRoad graph[v1][v2]; } //保留上次的最短路径 int minTmp minValue; minValue Math.min(minValue, tmpRoad); //如果最短路程和有改变就将最短路程保留到minPath中 if (minValue ! minTmp) { for (int i 0; i path.size(); i) { minPath.add(path.get(i)); } } } }else{ //开始匹配 //从1号城市开始 for (int i 1; i nums.length; i) { if (legal(i, n)) { check[i] true; path.add(i); dfs(n 1, nums); //恢复现场 check[i] false; path.remove(n); } } } } public static void main(String[] args) { Test14 test14 new Test14(); test14.initGraph(); test14.permute(test14.nums); System.out.println(test14.minValue); for (int i 0; i test14.minPath.size(); i) { System.out.print(test14.minPath.get(i) ); } } }3. N 皇后基于子集树实现N 皇后力扣链接题目描述按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n 皇后问题的棋子放置方案该方案中Q和.分别代表了皇后和空位。解决方案如下1算法思路⾸先我们在棋盘第⼀⾏放置第⼀个皇后然后遍历棋盘的第⼆⾏在可⾏的位置放置第⼆个皇后然后再遍历第三⾏在可⾏的位置放置第三个皇后以此类推直到放置了 n 个皇后为⽌。我们需要⽤⼀个数组来记录每⼀⾏放置的皇后的列数。在每⼀⾏中我们尝试放置⼀个皇后并检查是否会和前⾯已经放置的皇后冲突。如果没有冲突我们就继续递归地放置下⼀⾏的皇后直到所有的皇后都放置完毕然后把这个⽅案记录下来。在检查皇后是否冲突时我们可以⽤⼀个数组来记录每⼀列是否已经放置了皇后并检查当前要放置的皇后是否会和已经放置的皇后冲突。对于对⻆线我们可以⽤两个数组来记录从左上⻆到右下⻆的每⼀条对⻆线上是否已经放置了皇后以及从右上⻆到左下⻆的每⼀条对⻆线上是否已经放置了皇后。对于对⻆线是否冲突的判断可以通过以下流程解决1. 从左上到右下相同对⻆线的⾏列之差相同。2. 从右上到左下相同对⻆线的⾏列之和相同。因此我们需要创建⽤于存储解决⽅案的⼆维字符串数组ret⽤于存储每个皇后的位置的⼀维整数数组? queens 以及⽤于记录每⼀列和对⻆线上是否已经有皇后的布尔型数组columns 、diagonals1 和 diagonals2 。2 递归函数流程如下① 结束条件如果 row 等于 n 则表⽰已经找到⼀组解决⽅案此时将每个皇后的位置存储到字符串数组 path 中并将 path 存储到 ret 数组中然后返回② 枚举当前⾏的每⼀列判断该列、两个对⻆线上是否已经有皇后a. 如果有皇后则继续枚举下⼀列b. 否则在该位置放置皇后并将 columns 、diagonals1 和 diagonals2 对应的位置设为 true 表⽰该列和对⻆线上已经有皇后递归调⽤ dfs 函数搜索下⼀⾏的皇后位置。如果该⽅案递归结束则在回溯时需要将 columns 、 diagonals1 和 diagonals2 对应的位置设为 false 然后继续枚举下⼀列。class Solution { //1.定义全局变量 /* column用来判断列的 diagonals1用来判断正对角线 diagonals2用来判断反对角线 */ boolean[] columns, diagonals1, diagonals2; //结果收集的二维数组 ListListString ret; //收集本次皇后位置的数组因为棋盘是二维的所以path是二维数组 char[][] path; //表示棋盘的行或者列 int n; //如果要得到八皇后的结果只需要调用这个方法时传入8即可 public ListListString solveNQueens(int _n) { //2.初始化 n _n; columns new boolean[n]; diagonals1 new boolean[2 * n]; diagonals2 new boolean[2 * n]; ret new ArrayList(); path new char[n][n]; //把path的所有位置先该为. for (int i 0; i n; i) { Arrays.fill(path[i], .); } //开始回溯算法的核心部分 dfs(0);//从第一行开始 return ret; } public void dfs(int row) { //如果到了棋盘的最后一行了证明本次皇后们的位置是合法的 if (row n) { //添加结果 ListString tmp new ArrayList(); for (int i 0; i n; i) { tmp.add(new String(path[i])); } ret.add(new ArrayList(tmp)); } //开始匹配 for (int col 0; col n; col) { //判断能不能放 if (columns[col] false diagonals1[col - row n] false diagonals2[col row] false) { path[row][col] Q; columns[col] diagonals1[col - row n] diagonals2[col row] true; //寻找下一行 dfs(row 1); //恢复现场 path[row][col] .; columns[col] diagonals1[col - row n] diagonals2[col row] false; } } } }