回溯
大约 11 分钟
回溯
回溯算法
回溯算法是一种通过穷举法来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录下来，直到找到解或尝试了所有可能的选择都无法找到解为止。
回溯算法通常采用“深度优先搜索”来遍历空间。
例题一：给定一颗二叉树，搜索并记录所有值为7的节点，请返回节点列表。
/* 给定一颗二叉树，搜索并记录所有值为7的节点，请返回节点列表 */
class TreeNode {
value; // 节点值
left; // 左子节点引用
right; // 右子节点引用
constructor(value, left, right) {
this.value = value === undefined ? undefined : value;
this.left = left === undefined ? undefined : left; // undefined 表示不存在子节点
this.right = right === undefined ? undefined : right; // undefined 表示不存在子节点
}
}
let node1 = new TreeNode(1);
let node2 = new TreeNode(7);
let node3 = new TreeNode(3);
let node4 = new TreeNode(4);
let node5 = new TreeNode(5);
let node6 = new TreeNode(6);
let node7 = new TreeNode(7);
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node1.left = node2;
node1.right = node3;
let res = [];
let target = 7;
function search(root) {
if (root == undefined) return;
if (root.value == target) {
res.push(root);
}
search(root.left);
search(root.right);
}
search(node1);
console.log(res);
尝试与回退
之所以称为回溯算法，是因为该算法在搜索空间时会采取“尝试”与“回退”的策略。 当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回之前的状态，并尝试其它的选择。
例题二：在二叉树中搜索所有值为7的节点，请返回根节点到这些节点的途径。
/* 回溯 */
class TreeNode {
value; // 节点值
left; // 左子节点引用
right; // 右子节点引用
constructor(value, left, right) {
this.value = value === undefined ? undefined : value;
this.left = left === undefined ? undefined : left; // undefined 表示不存在子节点
this.right = right === undefined ? undefined : right; // undefined 表示不存在子节点
}
}
let node1 = new TreeNode(1);
let node2 = new TreeNode(7);
let node3 = new TreeNode(3);
let node4 = new TreeNode(4);
let node5 = new TreeNode(5);
let node6 = new TreeNode(6);
let node7 = new TreeNode(7);
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node1.left = node2;
node1.right = node3;
let path = [];
let res = [];
let target = 7;
function preOrder(root) {
if (root === undefined) return;
// 尝试当前值
path.push(root.value);
if (root.value == target) {
// 向res中推送
res.push([...path]);
}
// 查询左右子树
preOrder(root.left);
preOrder(root.right);
// 回退
console.log("执行了pop");
console.log(path);
path.pop();
}
preOrder(node1);
console.log(res);
剪枝
复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。
例题三：在二叉树中搜索所有值为7的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为3的节点。
/* 回溯 */
class TreeNode {
value; // 节点值
left; // 左子节点引用
right; // 右子节点引用
constructor(value, left, right) {
this.value = value === undefined ? undefined : value;
this.left = left === undefined ? undefined : left; // undefined 表示不存在子节点
this.right = right === undefined ? undefined : right; // undefined 表示不存在子节点
}
}
let node1 = new TreeNode(1);
let node2 = new TreeNode(7);
let node3 = new TreeNode(3);
let node4 = new TreeNode(4);
let node5 = new TreeNode(5);
let node6 = new TreeNode(6);
let node7 = new TreeNode(7);
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node1.left = node2;
node1.right = node3;
let path = [];
let res = [];
let target = 7;
function preOrder(root) {
if (root === undefined || root.value === 3) return;
// 尝试当前值
path.push(root.value);
if (root.value == target) {
// 向res中推送
res.push([...path]);
}
// 查询左右子树
preOrder(root.left);
preOrder(root.right);
path.pop();
}
preOrder(node1);
console.log(res);
常用术语
解：满足问题特定条件的答案，可能有一个或多个。 约束条件：限制解的可行性条件，通常用于剪枝。 状态：表示问题再某一时刻的状态，包括已经做出的选择。 尝试：根据可用选择来探索解空间的过程。 回退：遇到不满足约束条件，撤回前面做出的选择，回到上一状态。 剪枝：根据问题的特性以及约束条件来避免无意义的搜索路径，可提高搜索效率。
优点与局限性
回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解，这种方法的优点是能够找到所有可能的解，并且在合理的剪枝条件下，具有很高的效率。
运行效率分析：
时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
空间：在递归调用中需要保存当前的状态，深度很大时，空间需求很大。
常见的效率优化方法：剪枝、启发式搜索（在搜索过程中引入一些策略或者估计值，从而优化搜索最有可能产生有效解的路径）
回溯经典例题
搜索问题：
全排列问题：给定一个集合，求出其中所有可能的排列组合。
子集和问题：给定一个集合和一个目标值，找出集合中所有和为目标值的子集。
汉诺塔问题：给定三根柱子和一系列大小不一的圆盘，从第一根柱子移动到第三根柱子，每次只能移动一个圆盘，并且每次只能把小圆盘放在大圆盘上。
约束满足问题：
n皇后：在n x n的棋盘上摆放n个皇后，要求任意两个皇后不能处于同一行、同一列或同一斜线上。
数独：在9 x 9的网格中填入数字1~9，使得每行、每列和每3x3网格中的数字不重复。
图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。
组合优化问题：
0-1背包问题：给定一组物品和一个背包，每个物品都有一定的价值和重量，要求在背包容量限制内，选择物品总价值最大。
旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径。
最大团问题：给定一个无向图，找出最大的完全子图，即子图中的任意两个顶点之间都有边相连。
全排列问题
全排列问题是回溯算法中的一个典型应用，指给定一个集合的情况下，找出其中元素所有可能的排列。
无相等元素的情况
给定一个整数数组，其中不包含重复元素，返回所有可能的排列。
/* 全排列问题：无相等元素的情况 */
function fullPermutation(nums = []) {
let res = [];
backtrack([], nums, Array(nums.length).fill(false), res);
return res;
}
/**
* state：已被选择元素
* choices：可选择元素
* selected：已被选择元素
* res：结果集
*/
function backtrack(state, choices, selected, res) {
// 当状态长度等于元素数量时，记录解
if (state.length === choices.length) {
res.push([...state]);
return;
}
// 遍历所有选择
choices.forEach((choice, i) => {
// 剪枝：不允许重复选择元素
if (!selected[i]) {
// 尝试：做出选择，更新状态
selected[i] = true;
state.push(choice);
// 进行下一轮选择
backtrack(state, choices, selected, res);
// 回退：撤销选择，恢复到之前的状态
selected[i] = false;
state.pop();
}
});
}
console.log(fullPermutation([1, 2, 3, 4, 5]));
考虑相等元素的情况
输入一个整数数组，数组中可能包含重复元素，返回所有不重复的排列。
解法：使用剪枝，提前剔除重复。
/* 考虑重复元素的情况 */
function fullPermutation(nums = []) {
let res = [];
backtrack([], nums, Array(nums.length).fill(false), res);
return res;
}
/**
* state：已被选择元素
* choices：可选择元素
* selected：已被选择元素
* res：结果集
*/
function backtrack(state, choices, selected, res) {
// 当状态长度等于元素数量时，记录解
if (state.length === choices.length) {
res.push([...state]);
return;
}
// 记录所有选择
let duplicated = [];
// 遍历所有选择
choices.forEach((choice, i) => {
// 剪枝：不允许重复选择元素
if (!selected[i] && !duplicated.includes(choice)) {
duplicated.push(choice);
// 尝试：做出选择，更新状态
selected[i] = true;
state.push(choice);
// 进行下一轮选择
backtrack(state, choices, selected, res);
// 回退：撤销选择，恢复到之前的状态
selected[i] = false;
state.pop();
}
});
}
console.log(fullPermutation([1, 1, 2, 2]));
子集和问题
无重复元素的情况
给定一个正整数的数组nums和一个目标元素target，请找出所有可能的组合，使得组合中的元素之和等于target。给定数组中无重复元素，每个元素可以被重复选择多次，请以列表形式返回这些组合，列表中不应包含重复的组合。
/* 子集和问题：无重复元素 */
/**会存在重复子集 */
function subsetSum(nums = [], target) {
let state = []; // 当前
let total = 0; // 和
let res = []; // 结果集
backTrack(state, target, total, nums, res);
return res;
}
function backTrack(state, target, total, nums, res) {
if (total == target) {
res.push([...state]);
return;
}
nums.map((num) => {
// 和大于目标时，跳过
if (num + total <= target) {
// 小于时，进行尝试
state.push(num);
backTrack(state, target, total + num, nums, res);
// 回退
state.pop();
}
});
}
/**剪枝：剔除重复 */
function subsetSum(nums = [], target) {
let state = []; // 当前
const start = 0; // 遍历起始点
let res = []; // 结果集
backTrack(state, target, nums, start, res);
return res;
}
function backTrack(state, target, nums, start, res) {
// 子集和等于 target 时，记录解
if (target === 0) {
res.push([...state]);
return;
}
for (let i = start; i < nums.length; i++) {
if (target - nums[i] < 0) {
break;
}
state.push(nums[i]);
backTrack(state, target - nums[i], nums, i, res);
state.pop();
}
}
console.log(subsetSum([3, 4, 5], 9));
存在重复元素的情况
给定一个正整数数组nums和目标元素target，请找出所有可能的组合，使得组合中的元素之和等于target。给定数组中可能包含重复元素，每个元素可以被重复选择多次，请以列表形式返回这些组合，列表中不应包含重复的组合。
/* 考虑相等元素 */
/* 回溯算法：子集和 II */
function backtrack(state, target, choices, start, res) {
// 子集和等于 target 时，记录解
if (target === 0) {
res.push([...state]);
return;
}
// 遍历所有选择
// 剪枝二：从 start 开始遍历，避免生成重复子集
// 剪枝三：从 start 开始遍历，避免重复选择同一元素
for (let i = start; i < choices.length; i++) {
// 剪枝一：若子集和超过 target ，则直接结束循环
// 这是因为数组已排序，后边元素更大，子集和一定超过 target
if (target - choices[i] < 0) {
break;
}
// 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
if (i > start && choices[i] === choices[i - 1]) {
continue;
}
// 尝试：做出选择，更新 target, start
state.push(choices[i]);
// 进行下一轮选择
backtrack(state, target - choices[i], choices, i + 1, res);
// 回退：撤销选择，恢复到之前的状态
state.pop();
}
}
/* 求解子集和 II */
function subsetSumII(nums = [], target) {
const state = []; // 状态（子集）
nums.sort((a, b) => a - b); // 对 nums 进行排序
const start = 0; // 遍历起始点
const res = []; // 结果列表（子集列表）
backtrack(state, target, nums, start, res);
return res;
}
console.log(subsetSumII([4, 4, 5], 9));
n皇后问题
根据国际象棋的规则，皇后可攻击与其同一行、一列或一条斜线上的棋子。给定n个皇后和一个nxn的棋盘，寻找使得所有皇后之间无法相互攻击的摆放方案。
如下图所示，当n为4时，共可以找到两个解。从回溯算法的角度来看，nxn大小的棋盘共有个格子，给出了所有选择choices，在逐个防止皇后的过程中，棋盘的状态在不断的变化，每个时刻的棋盘的状态就是state。
- 逐行放置策略
皇后的数量和棋盘的行数都是n，因此我们很容易得到一个推论：棋盘每行都允许且只允许放置一个皇后。
从本质上看，逐行放置策略起到了剪枝的作用，它避免了同一行出现多个皇后的所有搜索分支。
- 列与对角线剪枝
为了满足约束条件，我们可以利用长度为n的布尔型数组cols记录每一列是否有皇后。在每次决定放置前，通过cols将已有皇后的列剪枝，并在回溯中动态更小cols的状态。
假设棋盘中的某个格子索引为(row,col)，选定矩阵中某条对角线，我们会发现在该对角线上的所有格子行索引减去列索引都相等，即对角线上所有格子的row-col都相等。同时发现次对角线上的行索引+列索引相等。
/* n皇后问题 */
function nQueens(n) {
// 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
let state = Array.from({ length: n }, () => Array(n).fill("#"));
// cols记录每行是否有皇后
let cols = Array(n).fill(false);
// 主对角线是否存在皇后
let diags1 = Array(2 * n - 1).fill(false);
let diags2 = Array(2 * n - 1).fill(false);
// 记录结果
let res = [];
backtrack(0, n, state, res, cols, diags1, diags2);
console.log(res);
return res;
}
/**
* @param row：当前行数
* @param n：皇后数量
* @param state：当前棋盘
* @param res：结果集
* @param cols：每行是否有皇后
* @param diags1：主对角线是否存在皇后
* @param diags2：次对角线是否存在皇后
*/
function backtrack(row, n, state, res, cols, diags1, diags2) {
// 当放置完所有行时，记录解
if (row === n) {
// 复制
res.push(state.map((row) => row.slice()));
return;
}
// 遍历列
for (let col = 0; col < n; col++) {
// 计算该格子对应的主对角线和次对角线
const diag1 = row - col + n - 1;
const diag2 = row + col;
// 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
// 尝试：将皇后放置在该格子
state[row][col] = "Q";
cols[col] = diags1[diag1] = diags2[diag2] = true;
// 放置下一行
backtrack(row + 1, n, state, res, cols, diags1, diags2);
// 回退：将该格子恢复为空位
state[row][col] = "#";
cols[col] = diags1[diag1] = diags2[diag2] = false;
}
}
}
nQueens(4);
Loading...