谈回溯法

发表于

前言

起先刷到LeetCode中的一题Combination Sum，题目要求是求一组数中如何搭配求和能得到目标值，也就是求目标值的所有解。该题地址，其实就是在一个组合中求所有解集，所以都可以归为一种算法原型，也就是要说的回溯法。

介绍一下它

概念

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。(许多复杂的，规模较大的问题都可以使用回溯法)

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

解题三步骤

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)。1代表选择该物品，0代表不选择该物品
2）确定易搜索的解空间结构
3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

算法思路

我暂时只介绍我所遇到的情况，子集树和排列树。还有一个非子集和排列的类别暂且还未遇到，倘若以后碰到，会再更新。关于N皇后问题，其实就是非子集加排列类型的问题。
其中大部分搜索解集的问题大都可以套下面的算法模板，可能会做一小部分更改。
这里我只讨论递归的算法框架，原因很简单，递归的代码更精简，更优雅。

子集树

典型例子：装载问题；0-1背包问题；最大团问题;求所有子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void backtrack(int t)//t是当前层数   
{  
    if(t>n)//需要判断每一个元素是否加入子集，所以必须达到叶节点，才可以输出  
    {  
        output(x);  
    }  
    else  
    {  
        for(int i=0;i<=1;i++)//子集树是从集合S中，选出符合限定条件的子集，故每个元素判断是（1）否（0）选入即可（二叉树），因此i定义域为{0,1}   
        {  
            x[t]=i;//x[]表示是否加入点集，1表示是，0表示否  
            if(constraint(t)&&bound(t))//constraint(t)和bound(t)分别是约束条件和限定函数   
            {  
                backtrack(t+1);  
            }  
        }  
    }  
}

其中的约束条件和限定函数负责“剪枝”功能，在我刷的关于回溯法的题中，大部分是去除掉关于重复的情况。

排列树

典型例子：全排列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void backtrack(int t)//t是当前层数   
{  
    if(t>n)//n是限定最大层数   
    {  
        output(x);  
    }  
    else  
    {  
        for(int i=t;i<=n;i++)//排列树的节点所含的孩子个数是递减的，第0层节点含num-0个孩子，第1层节点含num-1个孩子，第二层节点含num-2个孩子···第num层节点为叶节点，不含孩子。即第x层的节点含num-x个孩子，因此第t层的i，它的起点为t层数，终点为num，第t层（根节点为空节点，除外），有num-t+1个亲兄弟，需要轮num-t+1回   
        {  
            swap(x[t],x[i]);//与第i个兄弟交换位置，排列树一条路径上是没有重复节点的，是集合S全员元素的一个排列，故与兄弟交换位置后就是一个新的排列  
            if(constraint(t)&&bound(t))//constraint(t)和bound(t)分别是约束条件和限定函数   
            {  
                backtrack(t+1);  
            }  
            swap(x[i],x[t]);  
        }  
    }  
}

LeetCode中的回溯法

Combination Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> results = new ArrayList<List<Integer>>();
        List<Integer> current = new ArrayList<Integer>();
        Arrays.sort(candidates);
        back_track(results,current,candidates,target,0);
        return results;
    }


    public static void back_track(List<List<Integer>> results,List<Integer> current,int[] candidates,int target,int floor){
        if(target == 0){
            results.add(new ArrayList<Integer>(current));
        }else if(target<0){
            return;
        }else {

            for (int i = floor; i < candidates.length; i++) {
                int value = candidates[i];
                current.add(value);
                back_track(results, current, candidates, target - value, i);
                //remove the last one
                current.remove(current.size() - 1);
            }
        }
    }
}

Permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 public List<List<Integer>> permute(int[] nums) {
      List<List<Integer>> results = new ArrayList<List<Integer>>();
        List<Integer> tempResult = new ArrayList<Integer>();
        pailie(results,tempResult,nums,0);
        //System.out.println(results.size());

        return results;
    }

    public static void pailie(List<List<Integer>> results,List<Integer> tempReult,int[] nums,int floor){

        if(floor>nums.length-1){
           // System.out.println(Arrays.toString(nums));
            for(int num:nums){
                tempReult.add(num);
            }
            results.add(new ArrayList<Integer>(tempReult));
            tempReult.clear();
        }else{
            for(int i = floor;i<nums.length;i++){
                swap(nums,floor,i);
                pailie(results,tempReult,nums,floor+1);
                swap(nums,i,floor);
            }
        }
    }

    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

有时间再说下N皇后问题