vcjmhg 的个人博客

自律者自由

  menu
80 文章
13419 浏览
0 当前访客
ღゝ◡╹)ノ❤️

回溯法套路总结与应用

概述

回溯法常用于遍历一个列表元素的所有所有子集,比如全排列问题。可以说深度优先搜索就是回溯法的一种特殊形式。该方法的时间复杂度比较大一般为 O(N!),它不像动态规划存在重叠子问题可以优化,当然在某些情况下,我们可以通过剪枝来进行优化,当然这个技巧性可能较高。本篇文章主要从回溯法的基本思想入手,总结出一套模板,灵活运用模板便可以讲解大部分回溯算法的问题。

模板与算法

回溯法 其实核心思想就是以深度优先进行暴力穷举,最重要的是做到补充不漏,整个过程跟 决策树 的遍历是类似的。其通用的一个算法模板如下:

 result = []
 def backtrack(路径, 选择列表):
     if 满足结束条件:
         result.add(路径)
         return
 
     for 选择 in 选择列表:
         做选择
         backtrack(路径, 选择列表)
         撤销选择

从这个模板中,我们可以看出,要用好回溯算法其实重点就是解决三个问题:

  1. 路径:也就是已经做出的选择
  2. 选择列表
  3. 结束条件

下边我们通过一个全排列问题来展开说明:

全排列问题

具体题目如下:

image-20201117220437744

问题本身很简单,我们高中的时候可能就会通过画决策树来解决整个问题:

为啥说这是决策树呢,因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上:

你现在就在做决策,可以选择 1 那条树枝,也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢?因为 2 这个树枝在你身后,这个选择你之前做过了,而全排列是不允许重复使用数字的。

通过前边的说明,针对该问题需要解决的三个问题分别为:

  1. 路径:[2]就是路径,记录已经做过的选择
  2. 选择列表:[1,3]就是选择列表,表示接下来可进行选择元素的列表
  3. 结束条件:便利到树的底层,也就是说选择列表为空的时候结束

进而套用上边的模板,我们可以得出如下代码:

   List<List<Integer>> result = new ArrayList<>();
 
     /**
      * 使用回溯法,解决全排列问题
      * @param nums
      * @return
      */
     public List<List<Integer>> permute(int[] nums) {
         LinkedList<Integer> track = new LinkedList<>();
         backtrace(nums, track);
         return result;
    }
 
     private void backtrace(int[] nums, LinkedList<Integer> track) {
         // add track
         if (track.size() == nums.length) {
             result.add(new LinkedList<>(track));
        }
         for (int num : nums) {
             if (track.contains(num)) {
                 continue;
            }
             // make choice
             track.add(num);
             // recursive
             backtrace(nums, track);
             // backtrace choince
             track.removeLast();
        }
    }

应用

同样的再做一道题目练习一下:

image-20201117221202350

该问题,较之上一个问题,最大的不同就是会有重复的元素,因此会增加重复元素的判断,但整体难度也不大,套用模板可以得出如下解决方案:

 List<List<Integer>> result = new ArrayList<>();
   byte[] visited = new byte[22];
 
   public List<List<Integer>> permuteUnique(int[] nums) {
     LinkedList<Integer> track = new LinkedList<>();
     Arrays.sort(nums);
     backtrace(nums, track);
     return result;
  }
 
   private void backtrace(int[] nums, LinkedList<Integer> track) {
     // 倡导到达nums.lenghth则记录路径
     if (nums.length == track.size()) {
       result.add(new LinkedList<>(track));
    }
     for (int i = 0; i < nums.length; i++) {
       //已经添加过的元素直接跳过
       if (visited[i] == 1) {
         continue;
      }
       //与上一个元素相同,且没有添加过直接跳过
       if (i != 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) {
         continue;
      }
       visited[i] = 1;
       track.add(nums[i]);
       backtrace(nums, track);
       track.removeLast();
       visited[i] = 0;
    }
  }

总结

回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,算法框架如下:

 result = []
 def backtrack(路径, 选择列表):
     if 满足结束条件:
         result.add(路径)
         return
 
     for 选择 in 选择列表:
         做选择
         backtrack(路径, 选择列表)
         撤销选择

写 backtrack 函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集。

只要确定了选择的条件,以及记录路径的调整,整个代码很容易便可以实现出来了。

参考

  1. https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban#san-zui-hou-zong-jie
  2. https://greyireland.gitbook.io/algorithm-pattern/suan-fa-si-wei/backtrack#permutations

标题:回溯法套路总结与应用
作者:vcjmhg
地址:https://vcjmhg.top/backtracing