彻底理解回溯法的精要

给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

问题分析

使用什么方法?

全排列很明显使用回溯法来进行解答

什么是回溯法?

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

怎么使用回溯法?

运用回溯法解题的关键要素有以下三点:

  1. 针对给定的问题,定义问题的解空间;
  2. 确定易于搜索的解空间结构;
  3. 深度优先方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

    什么是深度优先搜索?

    深度优先搜索(缩写DFS)有点类似广度优先搜索,也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底,这种尽量往深处走的概念即是深度优先的概念。

代码模板是什么样子的?

void BackTrace(int t) {
    if(t>n)
        Output(x);
    else
    for(int i = f (n, t); i <= g (n, t); i++ ) {
        x[t] = h(i);
        if(Constraint(t) && Bound (t))
        BackTrace(t+1);
    }
}

其中,t表示递归深度,即当前扩展结点在解空间树中的深度;n用来控制递归深度,即解空间树的高度。当t>n时,算法已搜索到一个叶子结点,此时由函数Output(x)对得到的可行解x进行记录或输出处理

f(n, t)g(n, t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号;h(i)表示在当前扩展结点处x[t]的第i个可选值;函数Constraint(t)Bound(t)分别表示当前扩展结点处的约束函数和限界函数。若函数Constraint(t)的返回值为真,则表示当前扩展结点处x[1:t]的取值满足问题的约束条件;否则不满足问题的约束条件。若函数Bound(t)的返回值为真,则表示在当前扩展结点处x[1:t]的取值尚未使目标函数越界,还需由BackTrace(t+1)对其相应的子树做进一步地搜索;否则,在当前扩展结点处x[1:t]的取值已使目标函数越界,可剪去相应的子树。

回溯法的具体实施

class Solution {
    public List<List<Integer>> permute(int[] nums) {
      //LeetCode代码模板  
    }
}

step 1 定义问题的解空间

什么是解空间?

应用回溯法求解问题时,首先应明确定义问题的解空间,该解空间应至少包含问题的一个最优解。例如,对于有n种物品的 0-1 背包问题,其解空间由长度为n0-1 向量组成,该解空间包含了对变量的所有可能的0-1 赋值。当n=3时,其解空间是{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
在定义了问题的解空间后,还需要将解空间有效地组织起来,使得回溯法能方便地搜索整个解空间,通常将解空间组织成树或图的形式。例如,对于n= 30-1 背包问题,其解空间可以用一棵完全二叉树表示,从树根到叶子结点的任意一条路径可表示解空间中的一个元素,如从根结点A到结点J的路径对应于解空间中的一个元素(1, 0, 1)

定义本题的解空间

全排列问题,因为输入数组的长度为n = nums.length,解空间就是一个森林:

这里需要一个森林的图
假设n=4nums[]={1,2,3,4}则解空间应该是
第一层:1 2 3 4
第二层:12 13 14 /21 23 24/31 32 34
第三层:123 124/132 134/213 214/231 234/241 243/312 314/.....
第四层:略

确定易于搜索的解空间结构

解空间主要对应的是子集树和排列树,依据题意进行选择。(根据题意画个图,就知道了)

什么是子集树???

子集树是一个数学学科词汇,属于函数类,当所给问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间称为子集树。
当所给问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间称为子集树。例如:n个物品的0-1背包问题所相应的解空间是一棵子集树,这类子集树通常有2^n个叶结点,其结点总数为(2^(n+1))-1。遍历子集树的算法通常需O(2^n)计算时间。

什么是排列树??

当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。排列树通常有n!个叶子节点。因此遍历排列树需要O(n!)的计算时间。

上面已经确定,要将解空间构建成子集树的形式

step 2 回溯法的精髓

回溯的精髓

退回原状态
如何回退是回溯的精髓,什么时候回退
就本题而言,第一躺全排列应该是1->2->3->4 ,当走到最后一步4之后,应该回退一步到1->2->3因为3只有一个分支4,再回退一步到1->2,然后满足了约束函数可以进行下一步1->2->4;
对于本题,回退到方法在于,标记未被访问的数组下标,回退则重制标记
因此可以使用一个visited[]数组,数组的长度为nums.length,被访问则对应的下标标记为true,否则标记为false

step 3 回溯函数的设计

void BackTrace(int t)只传递一个参数的话显然是无法满足本题的,因为本题包含了一下5个需要传递的参数:

  1. visited[] 数组;
  2. t 递归深度;
  3. List<List<Integer>> output 保存所有解的大容器
  4. List<Integer> save 保存解的小容器
  5. nums[]原始数据

因此,BackTrace应设计为:

public static void BackTrace( List<Integer> save, List<List<Integer>> out, boolean visited[], int nums[]) {
        if (save.size() == nums.length) {
            out.add(new ArrayList<>(save));
            return;
        } else
            for (int i = 0; i < nums.length; i++) {
                if (visited[i]) continue;
                visited[i] = true;
                save.add(nums[i]);
                BackTrace( save, out, visited, nums);
                save.remove(save.size() - 1);
                visited[i] = false;
            }
    }

怎么写出这段代码需要结合前面的内容反复的思考 =-= 我想了好久才理清楚回溯的思路

回溯法的延伸

子集问题
题目:

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
从上题中我们可以得出结论,这仍然是一道需要使用回溯法的题目。

解空间与解空间结构

很明显这是一个子集数的解空间结构

假设n=3nums[]={1,2,3}则解空间应该是
第一层:1 2 3
第二层:12 13/21 23/31 32
第三层:123 132/213 231/312 321/

关键性问题

  1. 通过什么方法回退?
  2. 约束条件是什么?
  3. 去除重复对象
检测重复

检测重复首先想到的会是哈希表HashMap.因此每一次添加都应该在添加之前查找,如果找到重复则不存入;

约束条件是什么

约束条件应该还是当遍历到最后一个元素时退出?

通过什么方法回退?

由于集合的特殊性。不需要回退;

函数的设计:

public static void BackTrack(int t,int[] nums, List<List<Integer>> out, List<Integer> save) {

        out.add(new ArrayList<>(save));

        for (int i = t; i < nums.length; i++) {

            save.add(nums[i]);

            BackTrack(i+1,nums, out, save);

            save.remove(save.size()-1);
        }
    }
 
posted @ 2020-01-14 22:58  一位神秘丐帮  阅读(...)  评论(...编辑  收藏