常用算法:回溯算法

发表于 | 分类于

要用回溯算法解决问题需要将问题抽象为一个决策序列，一步步做决策，直到问题解决。如果发现某一步已经没有可以解决问题的决策了，或者决策序列已经到头但问题还未解决，就退回上一步进行其它的决策。

1.基本解决问题的思路

解决一个回溯问题，实际上就是一个决策树的遍历过程。需要关注的几个问题：

  1. 决策路径：也就是已经做出的决策序列，最终的决策序列就是问题的解。
  2. 选择列表：当前可以做的选择。
  3. 成功条件：完成任务的条件。
  4. 结束条件：一般是决策序列到头了或者已经确定必然无法完成任务了。

典型的回溯算法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
result = []
choice = []   //选择序列
condition = xxxx   //约束条件
backtrack(当前任务状态, 选择路径):
	if 满足结束条件:
		result.add(选择路径)
		return
	for 选择 in 选择列表:
	  if 选择不合理    //提前剪枝
	  	cotinue;
	  else
	  	做选择，计算新状态
	  	选择路径.add(当前选择)
			backtrack(新状态, 选择路径)
	  	选择路径.delete(当前选择)

2.回溯VS枚举

穷举法，先要把一个问题的所有可能解都列举出来，再一一检查是否满足问题条件，丢弃不满足的的解，剩下符合条件的解。

回溯法，一个解的生成是逐步进行的，当途中发现该解已经不可能满足需求了，就会提前放弃这个解，避免接下来不必要的解生成计算。可以理解为剪枝，剪掉了提前发现的不必要的计算分支。

因此在实际使用中，回溯法会比枚举法有更优秀的性能表现。

3. 0-1背包问题

题目：一个背包的总容量是9个单位。几个物品的重量分别为 2，2，4，6，2。选择几样商品装进背包，使得装进背包的物品总重量最大。之所以称之为0-1背包，意思是这个物品要么选择整个放进背包，要么选择整个不放进背包，不能选择部分放入背包。

每次考察一件商品，选择为 放 or 不放。如果放入某件商品，会造成背包总量溢出，则直接可以选择不放。如果达到终止条件，则和当前记录的最大总量对比，选择更大的那个。

3.1 如果只要求出最大值，不要求找出选择的物品

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
34
35
36
public class ZeroOneBag {
    private int maxWeight = Integer.MIN_VALUE;  //结果放到maxWeight中
    private int[] weight = {2, 2, 4, 6, 2};  //物品重量记录集合
    private int capacity = 9;  //背包容量
    /**
     * @param totalWeightNow 当前的累计重量
     * @param step 考察的物品下标
     */
    private void putIn(int totalWeightNow, int step) {
        //达到总重量 or 已经考察到最后一件商品,则终止
        if (totalWeightNow == capacity || step == weight.length) {
            //终止时比较重量和当前记录的最大值,取大的进行记录
            if (totalWeightNow > maxWeight) {
                maxWeight = totalWeightNow;
            }
            return;
        }
        //选择不放入当前考察的物品,总量不增加,考察下一个物品
        putIn(totalWeightNow, step + 1);
        //选择放入当前考察的物品,先判断是否超限
        if (totalWeightNow + weight[step] <= capacity) {
            //不超限,进行总量累加,考察下一个物品
            putIn(totalWeightNow + weight[step], step + 1);
        }
    }
    public static void main(String[] args) {
        final ZeroOneBag zeroOneBag = new ZeroOneBag();
        //初始状态,考察第一个下标为0的接口,总重量为0
        zeroOneBag.putIn(0, 0);
        System.out.println(zeroOneBag.maxWeight);
    }
}

3.2 如果同时要求找出任一个使得总重量最大的物品下标

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
34
35
36
37
38
39
40
41
42
43
44
public class ZeroOneBag2 {
    private List<Integer> result = new ArrayList<>();  //记录结果
    private int maxWeight = Integer.MIN_VALUE;  //结果放到maxWeight中
    private int[] weight = {2, 2, 4, 6, 2};  //物品重量记录集合
    private int capacity = 9;  //背包容量
    /**
     * @param totalWeightNow 当前的累计重量
     * @param step 考察的物品下标
     * @param temp 选择的物品的下标临时记录
     */
    private void putIn(int totalWeightNow, int step, ArrayList<Integer> temp) {
        //达到总重量 or 已经考察到最后一件商品,则终止
        if (totalWeightNow == capacity || step == weight.length) {
            //终止时比较重量和当前记录的最大值,取大的进行记录,并记录序列到result中
            if (totalWeightNow > maxWeight) {
                maxWeight = totalWeightNow;
                result = new ArrayList<>(temp);
            }
            return;
        }
        //选择不放入当前考察的物品,总量不增加,考察下一个物品
        putIn(totalWeightNow, step + 1, temp);
        //选择放入当前考察的物品,先判断是否超限
        if (totalWeightNow + weight[step] <= capacity) {
            //在临时记录区放入当前选择的物品下标
            temp.add(step);
            //不超限,进行总量累加,考察下一个物品
            putIn(totalWeightNow + weight[step], step + 1, temp);
            //拿出当前物品的下标
            temp.remove(temp.size() - 1);
        }
    }
    public static void main(String[] args) {
        final ZeroOneBag2 zeroOneBag = new ZeroOneBag2();
        //初始状态,考察第一个下标为0的接口,总重量为0
        zeroOneBag.putIn(0, 0, new ArrayList<>());
        System.out.println(zeroOneBag.maxWeight);
        System.out.println(zeroOneBag.result);
    }
}