江苏龙网

  1. 主页 > 生活百科 > >

什么叫回溯算法，一看就会，一写就废( 三 )

回溯算法


什么叫回溯算法，一看就会，一写就废

文章插图
 
然后第2行从第1列开始在不冲突的位置再放一个皇后 ， 然后第3行……一直这样放下去 ， 如果能放到第8行还不冲突说明成功了 ， 如果没到第8行的时候出现了冲突就回到上一步继续查找合适的位置……来看下代码
//row表示的是第几行public void solve(char[][] chess, int row) {//终止条件 ， row是从0开始的 ， 最后一行都可以放 ， 说明成功了if (row == chess.length) {//自己写的一个公共方法 ， 打印二维数组的 ， //主要用于测试数据用的Util.printTwoCharArrays(chess);System.out.println();return;}for (int col = 0; col < chess.length; col++) {//验证当前位置是否可以放皇后if (valid(chess, row, col)) {//如果在当前位置放一个皇后不冲突 ， //就在当前位置放一个皇后chess[row][col] = 'Q';//递归 ， 在下一行继续……solve(chess, row + 1);//撤销当前位置的皇后chess[row][col] = '.';}}}全排列问题给定一个没有重复数字的序列 ， 返回其所有可能的全排列 。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这道题我们可以把它当做一棵3叉树 ， 所以每一步都会有3种选择 ， 具体过程就不在分析了 ， 直接根据上面的模板来写下代码
public List<List<Integer>> permute(int[] nums) {List<List<Integer>> list = new ArrayList<>();backtrack(list, new ArrayList<>(), nums);return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {//终止条件if (tempList.size() == nums.length) {//说明找到一一组组合list.add(new ArrayList<>(tempList));return;}for (int i = 0; i < nums.length; i++) {//因为不能有重复的 ， 所以有重复的就不能选if (tempList.contains(nums[i]))continue;//选择当前值tempList.add(nums[i]);//递归backtrack(list, tempList, nums);//撤销选择tempList.remove(tempList.size() - 1);}}是不是感觉很简单 。
子集问题给定一组不含重复元素的整数数组 nums ， 返回该数组所有可能的子集（幂集） 。
说明：解集不能包含重复的子集 。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
我们还是根据模板来修改吧
public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> list = new ArrayList<>();//先排序Arrays.sort(nums);backtrack(list, new ArrayList<>(), nums, 0);return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {//注意这里没有写终止条件 ， 不是说递归一定要有终止条件的吗 ， 这里怎么没写 ， 其实这里的终止条件//隐含在for循环中了 ， 当然我们也可以写if(start>nums.length) rerurn;只不过这里省略了 。list.add(new ArrayList<>(tempList));for (int i = start; i < nums.length; i++) {//做出选择tempList.add(nums[i]);//递归backtrack(list, tempList, nums, i + 1);//撤销选择tempList.remove(tempList.size() - 1);}}所以类似这种题基本上也就是这个套路 ， 就是先做出选择 ， 然后递归 ， 最后再撤销选择 。在讲第一道示例的时候提到过撤销的原因是防止把前一个分支的结果带到下一个分支造成结果错误 。不过他们不同的是 ， 一个是终止条件的判断 ， 还一个就是for循环的起始值 ， 这些都要具体问题具体分析 。下面再来看最后一到题解数独 。
解数独数独大家都玩过吧 ， 他的规则是这样的
一个数独的解法需遵循如下规则：
  • 数字 1-9 在每一行只能出现一次 。
  • 数字 1-9 在每一列只能出现一次 。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次 。
过程就不在分析了 ， 直接看代码 ， 代码中也有详细的注释 ， 这篇讲的是回溯算法 ， 这里主要看一下backTrace方法即可 ， 其他的可以先不用看
//回溯算法public static boolean solveSudoku(char[][] board) {return backTrace(board, 0, 0);}//注意这里的参数 ， row表示第几行 ， col表示第几列 。private static boolean backTrace(char[][] board, int row, int col) {//注意row是从0开始的 ， 当row等于board.length的时候表示数独的//最后一行全部读遍历完了 ， 说明数独中的值是有效的 ， 直接返回trueif (row == board.length)return true;//如果当前行的最后一列也遍历完了 ， 就从下一行的第一列开始 。这里的遍历//顺序是从第1行的第1列一直到最后一列 ， 然后第二行的第一列一直到最后//一列 ， 然后第三行的……if (col == board.length)return backTrace(board, row + 1, 0);//如果当前位置已经有数字了 ， 就不能再填了 ， 直接到这一行的下一列if (board[row][col] != '.')return backTrace(board, row, col + 1);//如果上面条件都不满足 ， 我们就从1到9中选择一个合适的数字填入到数独中for (char i = '1'; i <= '9'; i++) {//判断当前位置[row ， col]是否可以放数字i ， 如果不能放再判断下//一个能不能放 ， 直到找到能放的为止 ， 如果从1-9都不能放 ， 就会下面//直接return falseif (!isValid(board, row, col, i))continue;//如果能放数字i ， 就把数字i放进去board[row][col] = i;//如果成功就直接返回 ， 不需要再尝试了if (backTrace(board, row, col))return true;//否则就撤销重新选择board[row][col] = '.';}//如果当前位置[row ， col]不能放任何数字 ， 直接返回falsereturn false;}//验证当前位置[row ， col]是否可以存放字符cprivate static boolean isValid(char[][] board, int row, int col, char c) {for (int i = 0; i < 9; i++) {if (board[i][col] != '.' && board[i][col] == c)return false;if (board[row][i] != '.' && board[row][i] == c)return false;if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)return false;}return true;}


推荐阅读


上一篇：金银花露不能连续服用,金银花茶的保留先容

下一篇：加盟福鼎白茶条件,福鼎白茶加盟资质