数据结构与算法（五）回溯算法（Java）

一、简介

1.1 定义

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

1.2 特性

回溯法是一个既带有 系统性 又带有 跳跃性 的搜索算法。

系统性： 它在包含问题的所有解的解空间树中，按照 深度优先的策略，从根节点出发搜索解空间树。
跳跃性： 算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其始祖结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。

这种以深度优先的方式系统地搜索问题解的算法称为回溯法，它 适用于解一些组合数较大的问题。

1.3 结点知识补充

扩展结点： 一个 正在生成儿子 的结点，称为扩展结点。
活结点： 一个 自身已生成但其儿子还没有全部生成 的结点，称为活结点。
死结点： 一个 所有儿子已经全部生成 的结点，称为死结点。

深度优先策略：

如果对一个扩展结点 R，一旦生成了它的一个儿子 C，就把 C 当作新的扩展结点。
在完成对子树 C（以 C 为根的子树）的穷尽搜索之后，将 R 重新变成扩展结点，继续生成 R 的下一个儿子（如果存在）。

广度优先策略：

在一个扩展结点变成死结点之前，它一直是扩展结点。

回溯法：

为了避免生成那些不可能产生最佳解的问题状态，要不断地利用 限界函数（bounding function）来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。
具有剪枝函数的深度优先生成法称为回溯法。

那什么是限界函数呢？限界函数是剪枝函数的一种，下面我们一起来看下剪枝函数。

1.4 剪枝函数

剪枝函数：当某个顶点没有希望，则其所在的树枝可以减去。

剪枝函数一般有两种：

约束函数： 剪去不满足约束条件的路径。
限界函数： 减去不能得到最优解的路径。

1.5 使用场景

回溯就是递归的副产品，只要有递归就会有回溯。 其实回溯就是 递归搜索+剪枝，并不是什么高效的算法。

回溯算法的应用：

当问题是要满足某种性质（约束条件）的所有接或最优解时，往往使用回溯法。

1.6 解空间

当确定回溯后，问题的关键转化为如何定义问题的解空间，且转化为树结构，可以称之为 解空间树。

解空间树分为：

子集树： 当所给的问题是 从 n 个元素的集合中找到某种性质的子集 时，相应的解空间变为子集树。如：0-1 背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。
排列数： 所给的问题是确定 n 个元素满足某种性质的排列时，相应的解空间就是排列树。如：旅行问题，一个人把几个城市旅游一遍，要求走的路程最小，它的解法就是几个城市的排列。

1.7 实现模板

// 一定要分成横纵两个方面思考问题
public void backTracking(参数) {
    if (终止条件) {
        // 存放结果
        return;
    }
    
    // 注意 i=0,i=start 的区别
    for (选择：本层集合中元素（树中结点孩子的数量就是集合的大小）) {
        // 处理节点
        backTracking(路径，选择列表); // 递归，注意 i 和 i++ 的区别
        // 回溯，撤销处理结果
    }
}

二、经典示例

2.1 0-1 背包问题

题目：

有一个背包，容量由你自己输入，有n个物品，每个物品都具有容量与价值，这些都是由你自己输入的，请问，要怎么放物品到背包里，才能使得总价值最大呢，放入背包的总容量要小于等于背包的总容量。（如果一个物品放不下，则可以拆分成多个小块）
背包：M：100
物品：N：7
重量价值
10 20
20 40
30 30
25 20
50 40
10 35
60 70

思路：

迭代进行深度优先遍历；
如果重量超出容量不予考虑；
不超出容量情况下，获取价值最大值。

代码实现：

public static void main(String[] args) {
    int[][] items = new int[7][2];
    // 重量 价值
    items[0][0] = 10; items[0][1] = 20;
    items[1][0] = 20; items[1][1] = 40;
    items[2][0] = 30; items[2][1] = 30;
    items[3][0] = 25; items[3][1] = 20;
    items[4][0] = 50; items[4][1] = 40;
    items[5][0] = 10; items[5][1] = 35;
    items[6][0] = 60; items[6][1] = 70;
    int capacity = 100;
    System.out.println("背包的容量：" + capacity);
    StringBuilder builder = new StringBuilder();
    for (int[] item : items) {
        builder.append(Arrays.toString(item));
    }
    System.out.println(items.length + " 个物品的重量、价值：" + builder.toString());
    int maxValue = maxValue(items, capacity);
    System.out.println("最大价值：" + maxValue);
}

private static int maxValue(int[][] items, int capacity) {
    // 0-未放入背包 1-放入背包
    int[] flag = new int[items.length];
    List<int[]> record = new ArrayList<>();
    int maxValue = maxValue(items, capacity, flag, 0, 0, record);
    for (int[] item : record) {
        capacity = capacity - item[0];
        System.out.println("重量为 " + item[0] + "，价值为 " + item[1] + " 的物品被放入背包，剩余容量：" + capacity);
    }
    return maxValue;
}

private static int maxValue(int[][] items, int capacity, int[] flag, int weightSum, int oldMaxValue, List<int[]> record) {
    if (weightSum > capacity) {
        return -1;
    }

    int maxValue = oldMaxValue;
    for (int i = 0; i < items.length; i++) {
        if (flag[i] == 0) {
            flag[i] = 1;
            int tmpValue = maxValue(items, capacity, flag, weightSum + items[i][0], oldMaxValue + items[i][1], record);
            if (tmpValue != -1) {
                if (tmpValue > maxValue) {
                    maxValue = tmpValue;
                    record.clear();
                    // 用于记录日志
                    for (int j = 0; j < flag.length; j++) {
                        if (flag[j] == 1) {
                            record.add(items[j]);
                        }
                    }
                }
            }
            flag[i] = 0;
        }
    }
    return maxValue;
}

执行结果：

在这里插入图片描述

2.2 N皇后问题

N皇后

题目：

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展

示例:

 输入：4
 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

代码实现：

public static void main(String[] args) {
    List<List<String>> result = solveNQueens(4);
    result.forEach(o -> {
        o.forEach(System.out::println);
        System.out.println("----");
    });
}

public static List<List<String>> solveNQueens(int n) {
    List<List<String>> list = new ArrayList<>();
    handleQueens(n, 0, new int[n], new ArrayList<>(), new HashSet<>(), new HashSet<>(), list);
    return list;
}

private static void handleQueens(int n, int level, int[] flag, List<String> queens, Set<Integer> diagonalSet, Set<Integer> reverseDiagonalSet, List<List<String>> list) {
    if (level >= n) {
        list.add(new ArrayList<>(queens));
        return;
    }

    for (int i = 0; i < n; i++) {
        int diagonal = i - level;
        int reverseDiagonal = i + level;
        if (flag[i] == 0 && !diagonalSet.contains(diagonal) && !reverseDiagonalSet.contains(reverseDiagonal)) {
            flag[i] = 1;
            queens.add(getLineStr(i, n));
            diagonalSet.add(diagonal);
            reverseDiagonalSet.add(reverseDiagonal);
            handleQueens(n, level + 1, flag, queens, diagonalSet, reverseDiagonalSet, list);
            reverseDiagonalSet.remove(reverseDiagonal);
            diagonalSet.remove(diagonal);
            queens.remove(queens.size() - 1);
            flag[i] = 0;
        }
    }
}

private static String getLineStr(int i, int n) {
    StringBuilder builder = new StringBuilder();
    for (int j = 0; j < n; j++) {
        builder.append(j == i ? "Q" : ".");
    }
    return builder.toString();
}