本篇文章主要总结一下笔者学习的两种算法：回溯法和分支限界法。这两种算法其实在OI界中很少用到，因为简单粗暴，本质上就是暴力+剪枝。两者都是暴力搜索的一种方法，只不过分别对应二叉树遍历中的DFS和BFS思想。为什么会联系到二叉树呢？因为一个可以用回溯法或分支限界法解决的问题，实际上就是一个决策树的遍历过程。

那么我们逐一详细介绍一下两种算法。

回溯法

前文提到，解决回溯问题，实际上就是一个决策树的遍历过程。

Q：什么是决策树？

A：决策树（Decision Tree）是一种常用的数据结构，也是一种常见的机器学习模型。在这个上下文中，我们可以将决策树理解为一个图，其中每个节点代表一个决策，每个边代表基于该决策的结果。根节点（root）代表初始状态，叶节点（leaf）代表决策结果。

在回溯法中，决策树被用来枚举所有可能的解决方案。每个节点代表一个部分解决方案，每个边代表一个选择，从根节点到叶节点的路径代表一个完整的解决方案。回溯法通过深度优先搜索（DFS）策略，进行决策树的遍历，寻找所有可能的解决方案。

例如，假设我们正在解决一个简单的迷宫问题。我们可以将每个位置视为一个决策（向上、向下、向左或向右移动），并将整个迷宫视为一个决策树。然后，我们可以使用回溯法来遍历这个决策树，找到从入口到出口的路径。

那么我们只需要搞懂三个问题，就能把握住问题的核心：

  1. 路径：就是已经做出的选择
  2. 选择列表：就是你在当前节点可以做出的选择
  3. 结束条件：就是你到达决策树底层，无法再继续做选择的条件。（也可以是一些额外的约束条件，用于剪枝减少选择提高算法效率）

代码方面，回溯问题的伪代码框架大致如下：

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

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

回溯算法代码的核心，就是一个for循环中的递归。首先检查结束条件，决定是否退出；如果没有退出，就在递归调用之前，「做选择」；在递归调用之后「撤销选择」。就是这么简单。

接下来用两个问题来理解回溯法：全排列和N皇后问题。

全排列

46. 全排列 - 力扣（LeetCode）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

我们抛开算法来看，自己想想怎么对三个数进行全排列：首先固定1不变，排列2,3和3,2；然后固定2为第一个元素，排列1,3和3,1；最后固定3为第一个元素，排列1,2和2,1。

这种穷举的思想，就是一个决策树的过程。

img

你可以把选择列表与属性视为节点的两个属性，每个节点都储存着你做出这个选择时的情况。定义的backtrack函数更像是一个指针，在决策树上用DFS的遍历方式游走，同时要不断的正确维护每个节点的属性。当我们走到决策树的底层时，我们走过的路径就是一个全排列。

为什么要撤销选择？

正如我们前文提到的，要在决策树游走，需要我们正确的维护每一个决策节点的属性。

每当我们做出一个决策，我们就做出了一个选择：也就是改变了路径。那么，当我们走到这个选择的决策树底层，回到该节点时，需要恢复原路径信息，这样我们才能在不受干扰的条件下做出另一个选择。

img

那我们可以不撤销选择吗？也可以。

我们之所以要撤销选择，是因为我们更改了节点的信息。但如果我们每次做选择时都生成一个节点的副本，在这上面进行的改变不会影响到原有节点，此时就不需要进行选择撤回操作。但是这么做需要给遍历到的每个节点都创建一个副本，带来的空间开销很大，不利于函数的性能。

那么用回溯法解决问题的思路就很显而易见了：首先我们做出选择，然后进入到下一层决策树继续选择；如果track列表中出现了重复的数字，说明该数字已经被选择过，丢弃该选择；如果最后路径列表的长度等于全排列的长度，说明排列已完成，返回路径结束递归。

代码如下：

package 全排列

func permute(nums []int) [][]int {
	res := make([][]int, 0)
	track := make([]int, 0)
	var backtrack func(nums []int, track []int)
	backtrack = func(nums []int, track []int) {
		//结束条件 路径和初始的选择列表长度相同，说明已经全部排列完成
		if len(track) == len(nums) {
			res = append(res, append([]int{}, track...))
			return
		}

		for i := 0; i < len(nums); i++ {
			//排除不合法的选择
			if contains(track, nums[i]) {
				continue
			}
			//做选择
			track = append(track, nums[i])
			//进入下一层决策树
			backtrack(nums, track)
			//取消选择
			track = track[:len(track)-1]
		}
	}
	backtrack(nums, track)
	return res
}

func contains(slice []int, item int) bool {
    //检查切片中是否包含指定的元素
	for _, a := range slice {
		if a == item {
			return true
		}
	}
	return false
}

必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

N皇后

51. N 皇后 - 力扣（LeetCode）

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

套用框架可得代码如下：

func solveNQueens(n int) [][]string {
	var res [][]string
	var board [][]byte
	for i := 0; i < n; i++ {
		board = append(board, make([]byte, n))
		for j := 0; j < n; j++ {
			board[i][j] = '.'
		}
	} //初始化棋盘为全'.'，即空
	var backtrack func(row int) 
	backtrack = func(row int) {
		if row == n {//结束条件
			var tmp []string
			for i := 0; i < n; i++ {
				tmp = append(tmp, string(board[i]))
			}
			res = append(res, tmp)//找到一个解，将解加入结果集
			return
		}
		for col := 0; col < n; col++ {
			if !isValid(board, row, col) {//剪枝
				continue
			}
			board[row][col] = 'Q'//进行选择
			backtrack(row + 1)//递归
			board[row][col] = '.'//撤销选择
		}
	}
	backtrack(0)
	return res
}

func isValid(board [][]byte, row, col int) bool {
	n := len(board)
	for i := 0; i < n; i++ {
		if board[i][col] == 'Q' {//如果同一列有皇后
			return false
		}
	}
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if board[i][j] == 'Q' {//如果左上角有皇后
			return false
		}
	}
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if board[i][j] == 'Q' {//如果右上角有皇后
			return false
		}
	}
	return true
}

函数 backtrack 依然像个在决策树上游走的指针，通过 row 和 col 就可以表示函数遍历到的位置，通过 isValid 函数可以将不符合条件的情况剪枝。

总结

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作。写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

其实想想看，回溯算法和动态规划是不是有点像呢？我们在动态规划系列文章中多次强调，动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？

某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。

拓展部分

以下内容来源于课件，偏理论，猜测整理自《算法导论》。

主要介绍解空间树的子集树和排列树的概念。

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

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。—— 系统性

算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。——跳跃性

这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，
它适用于解一些组合数较大的问题。许多复杂的、规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

其实我觉得就是一种更加科学、附带剪枝的暴力搜索法。

要了解子集树和排列树，我们先对问题的解空间做一个定义。

问题的解向量：回溯法希望一个问题的解能够表示成一个n元式

(x1, x2, …, xn) 的形式。

显约束：对分量xi的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组， 构成了该实例的一个解空间。

注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。

关于搜索空间主要有三种表示方法：

  • 表序表示：搜索对象通过线性表数据结构来表示
  • 显示图表示：搜索对象在搜索开始前就通过图（树）的数据结构来表示
  • 隐式图表示：除了初始节点，其他的节点在搜索过程中全部动态生成。因为搜索空间可能很大，难以全部储存。

image-20240606162410585

对解空间的遍历方法可以参照二叉树的遍历方法，即前中后序遍历。一般我们使用中序遍历，因为这样就可以很方便的在搜索完左子树后撤销选择再进入右子树。

有了以上概念，我们就可以根据解空间树对回溯法的操作进行更加详细的定义：

  1. 首先针对问题定义问题的解空间
  2. 接着确定易于搜索的解空间结构（子集树还是排列树）
  3. 以深度优先搜索的方式遍历解空间树，并在搜索过程中用剪枝函数避免无效搜索。
    • 常常用剪枝函数在扩展节点减去不满足约束的子树
    • 减去得不到最优解的子树

两类常见的解空间树定义如下：

子集树:当所给的问题是从几个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶子结点，其总结点个数为2n+1-1，遍历子集树时间为Ω(2n)。如0-1背包问题

排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子结点，因此，遍历排列树需要Ω(n!)的计算时间。如TSP问题 (Traveling Salesman Problem，推销员问题) ，叶结点数为n!，遍历时间为Ω(n!)。

子集树

假设现在有一列数a[0],a[1], …a[n-1]，如果一个问题的解的长度不是固定的，并且解和元素顺序无关，即可以从中选择0个或多个，那么解空间的个数将是指数级别的，为2^n,可以用下面的子集树来表示所有的解(假设这里n=4)

image-20240606213615107

void backtrack(int t){ // 表示访问到第t层，t从0开始
	if (t == n) // 如上图（PIC、子集树）n=4时就可以输出结果
		output(x);
	else
		for (int i = 0; i<=l; i++){ 
		//表示选或者不选a[t]，l代表选项的范围，可能是0到某个上限
			x[t] = i;
			if (constraint(t) && bound(t))
				backtrack(t + 1);
		}
}

排列树

如果解空间是由n个元素的排列形成，即n个元素的每一个排列都是解空间中的一个元素，那么，最后解空间的组织形式是排列树。

image-20240606213643074

void backtrack(int t){ //t代表当前层数，从0开始，n代表总层数
	if (t == n)  // t==n时表示已经生成了一组全排列，输出结果
		output(x); // x是储存当前排列结果的数组
	else
		for (int i = t; i<=n; i++){ 
			swap(x[t],x[i]);
			if (constraint(t) && bound(t))
			{
				backtrack(t + 1);
				swap(x[t],x[i]); // 每次递归后恢复原状
			}
		}
}
//这里的n表示层数！

例题

下面给出用回溯法求解01背包问题的代码，出自我的课程实验报告：

//回溯法解决01背包问题
//结束条件：背包装满或者所有物品都放入背包
#include <iostream>
#include <vector>
using namespace std;

struct Item{
    int weight;
    int value;
};

void backtrack(int i,int weight,int value,const vector<Item>& items,int capacity,int& maxValue){
    //结束条件
    if(weight==capacity||i==items.size()){
        maxValue=max(value,maxValue);
        return;
    }

    //不选择物品
    backtrack(i+1,weight,value,items,capacity,maxValue);
    //选择物品
    if(weight+items[i].weight<=capacity){
        backtrack(i+1,weight+items[i].weight,value+items[i].value,items,capacity,maxValue);
    }
}

int main() {
    int capacity,count,maxValue;
    vector<Item>Items;
    maxValue=0;
    //第一行输入背包总容量和物品数量
    cin>>capacity>>count;
    for (int i = 0; i < count; ++i) {
        struct Item Item;
        cin>>Item.weight>>Item.value;
        Items.emplace_back(Item);
    }
    backtrack(0,0,0,Items,capacity,maxValue);
    cout<<"The max value is "<<maxValue<<endl;

    return 0;
}

可以看出设计理念参照的是解空间树的子集树，因为01背包问题是一个组合问题，与顺序无关，所以不需要撤销选择而直接遍历所有的解就行了。

分支限界法

回溯算法的思想其实和深度优先搜索也就是DFS有共通之处，一个要走到决策树底层才退出，一个是根据深度遍历，都是“打破南墙才回头”。这无疑是一种经典的暴力搜索的方式，但是这种方式具有盲目性，接下来我们来介绍基于BFS宽度优先搜索的分支限界法。

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

i) 对已处理的各结点根据限界函数估算目标函数的可能取值，

ii) 从中选出目标函数取得极大(极小) 值的结点优先进行广度优先搜索,

iii) 不断地调整搜索方向，尽快找到解，裁剪那些不能得到最优解的子树以提高搜索效率。

其中的限界函数是针对具体问题的目标函数，比如对于01背包问题，可以预设限界函数为背包剩余空间的平均价值。

求解步骤

  1. 定义解空间/对解编码
  2. 确定解空间的树结构
  3. 按照BFS的方式对解空间树进行遍历：
    1. 每个活节点只有一次方式变为扩展节点
    2. 由扩展节点生成一步可达的新节点，即宽度搜索
    3. 在新节点中，删除不可能导出最优解的节点，这点可以利用限界函数辅助判断
    4. 将剩余的节点加入活动表（队列）中
    5. 从活动表中选择节点再进行扩展（分支）
    6. 直到活动表（队列）为空

在选择队列时有两种选择，对应两种分支限界法：

  1. 队列式FIFO分支限界法：节点进入与取出顺序与普通队列相同
  2. 优先队列（代价最小或者效益最大）分支限界法：每个节点都可以借助限界函数来预估一个价值，以此决定节点处理的优先级，一般要用到堆来实现优先队列。

例题

这里给出对01背包应用分支限界法的解法，包括FIFO式和优先队列式。

//分支限界法 FIFO普通队列管理 解决01背包问题
package main

import "fmt"

type Node struct {
	level    int     // 表示当前决策层的层数
	weight   float64 // 表示目前为止所选择物品的重量总和
	value    float64 // 表示目前为止所选择物品的价值总和
	bound    float64 // 表示此节点的价值上界
	included bool    // 表示该节点所对应的对象是否被放到背包中
}

func bound(node Node, n int, W float64, weights []float64, values []float64) float64 { // 计算节点的价值上界
	if node.weight >= W { // 如果当前节点的重量已经超过了背包的容量，则无需继续探索，直接剪枝
		return 0
	}
	bound := node.value      // 计算当前节点的价值上界
	j := node.level + 1      // 初始化下一个物品的索引
	totWeight := node.weight // 计算当前节点的重量总和
	for ; j < n; j++ {       // 遍历剩余物品
		if totWeight+weights[j] <= W { // 如果当前节点的重量加上下一个物品的重量小于等于背包的容量
			bound += values[j]      // 则加上下一个物品的价值
			totWeight += weights[j] // 并更新当前节点的重量总和
		} else { // 如果当前节点的重量加上下一个物品的重量大于背包的容量
			break // 则停止遍历
		}
	}
	if j < n {
		bound += (W - totWeight) * (values[j] / weights[j]) // 计算剩余物品的价值上界
	}
	return bound
}

func knapsack01(n int, W float64, weights []float64, values []float64) float64 {
	var maxValue float64
	var queue []Node
	var initNode Node
	initNode.level = -1
	initNode.weight = 0
	initNode.value = 0
	queue = append(queue, initNode) // 加入初始节点到队列中

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		if node.level == -1 {
			node.bound = bound(node, n, W, weights, values) // 计算初始节点的价值上界
		}

		if node.bound > maxValue { // 如果当前节点的价值上界大于最大值
			leftNode := Node{ // 左节点代表选择当前物品
				level:  node.level + 1,
				weight: node.weight + weights[node.level+1], // 加上当前物品的重量
				value:  node.value + values[node.level+1]}
			leftNode.bound = bound(leftNode, n, W, weights, values)
			if leftNode.weight <= W && leftNode.value > maxValue {
				maxValue = leftNode.value
			}
			if leftNode.bound > maxValue { // 如果左节点的价值上界大于最大值
				queue = append(queue, leftNode) // 加入左节点到队列中
			}

			rightNode := Node{ // 右节点代表不选择当前物品
				level:  node.level + 1,
				weight: node.weight,
				value:  node.value}
			rightNode.bound = bound(rightNode, n, W, weights, values) // 计算右节点的价值上界
			if rightNode.bound > maxValue {                           // 如果右节点的价值上界大于最大值，事实上永远都可以进入右节点
				queue = append(queue, rightNode) // 加入右节点到队列中
			}
		}
	}
	return maxValue
}

func main() {
	//输入物品数量
	var n int
	fmt.Scan(&n)
	//输入背包容量
	var W int
	fmt.Scan(&W)
	//输入物品重量
	var weights = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&weights[i])
	}
	//输入物品价值
	var values = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&values[i])
	}

	result := knapsack01(n, float64(W), weights, values)
	fmt.Println("Maximum value that can be obtained is:", result)
}

//分支限界法 优先队列管理 解决01背包问题
package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	level    int     // 表示当前决策层的层数
	weight   float64 // 表示目前为止所选择物品的重量总和
	value    float64 // 表示目前为止所选择物品的价值总和
	bound    float64 // 表示此节点的价值上界
	included bool    // 表示该节点所对应的对象是否被放到背包中
}

// PriorityQueue 优先队列实现最大堆功能
type PriorityQueue []Node

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].bound > pq[j].bound
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(Node)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func bound(node Node, n int, W float64, weights []float64, values []float64) float64 { // 计算节点的价值上界
	if node.weight >= W { // 如果当前节点的重量已经超过了背包的容量，则无需继续探索，直接剪枝
		return 0
	}
	bound := node.value      // 计算当前节点的价值上界
	j := node.level + 1      // 初始化下一个物品的索引
	totWeight := node.weight // 计算当前节点的重量总和
	for ; j < n; j++ {       // 遍历剩余物品
		if totWeight+weights[j] <= W { // 如果当前节点的重量加上下一个物品的重量小于等于背包的容量
			bound += values[j]      // 则加上下一个物品的价值
			totWeight += weights[j] // 并更新当前节点的重量总和
		} else { // 如果当前节点的重量加上下一个物品的重量大于背包的容量
			break // 则停止遍历
		}
	}
	if j < n {
		bound += (W - totWeight) * (values[j] / weights[j]) // 计算剩余物品的价值上界
	}
	return bound
}

func knapsack01(n int, W float64, weights []float64, values []float64) float64 {
	var maxValue float64
	var queue = make(PriorityQueue, 0)
	heap.Init(&queue)
	var initNode Node
	initNode.level = -1
	initNode.weight = 0
	initNode.value = 0
	queue.Push(initNode)

	for queue.Len() > 0 {
		node := heap.Pop(&queue).(Node)

		if node.level == -1 {
			node.bound = bound(node, n, W, weights, values) // 计算初始节点的价值上界
		}

		if node.bound > maxValue { // 如果当前节点的价值上界大于最大值
			leftNode := Node{ // 左节点代表选择当前物品
				level:  node.level + 1,
				weight: node.weight + weights[node.level+1], // 加上当前物品的重量
				value:  node.value + values[node.level+1]}
			leftNode.bound = bound(leftNode, n, W, weights, values)
			if leftNode.weight <= W && leftNode.value > maxValue {
				maxValue = leftNode.value
			}
			if leftNode.bound > maxValue { // 如果左节点的价值上界大于最大值
				heap.Push(&queue, leftNode) // 加入左节点到队列中
			}

			rightNode := Node{ // 右节点代表不选择当前物品
				level:  node.level + 1,
				weight: node.weight,
				value:  node.value}
			rightNode.bound = bound(rightNode, n, W, weights, values) // 计算右节点的价值上界
			if rightNode.bound > maxValue {                           // 如果右节点的价值上界大于最大值，事实上永远都可以进入右节点
				heap.Push(&queue, rightNode) // 加入右节点到队列中
			}
		}
	}
	return maxValue
}

func main() {
	//输入物品数量
	var n int
	fmt.Scan(&n)
	//输入背包容量
	var W int
	fmt.Scan(&W)
	//输入物品重量
	var weights = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&weights[i])
	}
	//输入物品价值
	var values = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&values[i])
	}

	result := knapsack01(n, float64(W), weights, values)
	fmt.Println("Maximum value that can be obtained is:", result)
}

不同于回溯法，我们在分支限界法一般都需要显示的指定树的数据结构，因为涉及到树的层次遍历（宽度优先搜索）。

这里的重点是限界函数的应用，值得仔细揣摩。

参考文章

回溯算法套路详解 - 知乎 (zhihu.com)

IMG_20240609_195030