本文共 2836 字，大约阅读时间需要 9 分钟。

回溯算法入浅

回溯算法（Backtracking）是一种在搜索过程中，当发现某条路径不满足条件时，能智能地撤回一步，尝试其他可能性。这种方法类似于枚举，但比简单枚举更高效，因为它能够在发现问题早期就剪枝，不再继续走不必要的路。

在《》一文中，解决回溯问题实际上是一个决策树的遍历过程。要想高效地实现回溯算法，我们需要思考以下三个关键问题：

以下是改编后的算法通用结构：

function backtrack(路径, 选择列表) {
    if 满足结束条件
        console.log(路径)
        return
    for 选择 of 选择列表
        做选择
        backtrack(路径, 选择列表)
        撤销选择
}

回溯算法的典型应用

1. N皇后问题

N皇后问题是回溯算法的经典应用之一。目标是将N个皇后放置在N×N的棋盘上，使得它们彼此之间不能相互攻击。每个皇后所在的行、列以及对角线都不能有其他皇后。

实现思路：

const N = 4;
function backtrack(route, row) {
    if (row == N) {
        console.log(route);
        return;
    }
    for (let column = 0; column < N; column++) {
        if (!isValid(route, row, column)) {
            continue;
        }
        route[row] = column;
        backtrack(route, row + 1);
        route[row] = null;
    }
}
function isValid(route, row, column) {
    let leftup = column - 1;
    let rightup = column + 1;
    for (let i = row - 1; i >= 0; i--) {
        if (route[i] == column) {
            return false;
        }
        if (leftup >= 0) {
            if (route[i] == leftup) {
                return false;
            }
        }
        if (rightup < N) {
            if (route[i] == rightup) {
                return false;
            }
        }
        leftup--;
        rightup++;
    }
    return true;
}

2. 0-1背包问题

0-1背包问题是一个经典的回溯问题。目标是从给定的物品中选择不超过背包容量的物品，使得背包中的物品总重量最大。

实现思路：

• 递归地尝试将物品装入背包或不装。
• 在每一步选择中，检查当前物品是否超出背包容量或是否已经选过。
• 当当前物品装入背包后，递归处理剩余物品。
• 撤销选择后，继续尝试其他可能性。

let max = Number.MIN_VALUE;
let W = 100;
function backtrack(route, goods) {
    let weight = route.length ? route.reduce((acc, cur) => acc + cur, 0) : 0;
    if (weight == W || route.length == goods.length) {
        if (weight > max && weight <= W) {
            max = weight;
        }
        console.log(route);
        return;
    }
    for (let i = 0; i < goods.length; i++) {
        if (weight + goods[i] > W || route.indexOf(goods[i]) > -1) {
            continue;
        }
        route.push(goods[i]);
        backtrack(route, goods);
        route.pop();
    }
}

3. 全排列问题

全排列问题要求输出给定数字序列的全部可能排列。假设序列中的数字都是唯一的，可以利用回溯算法枚举出所有排列。

实现思路：

• 递归地尝试将数字放入排列中。
• 在每一步选择中，检查当前数字是否已经被选过。
• 当排列长度等于数字数量时，记录当前排列。
• 撤销选择后，继续尝试其他可能性。

function backtrack(route, nums) {
    if (route.length == nums.length) {
        console.log(route);
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (route.indexOf(nums[i]) > -1) {
            continue;
        }
        route.push(nums[i]);
        backtrack(route, nums);
        route.pop();
    }
}

面试题解析

• 面试题12 和 面试题13：在二维方格或矩阵的运动中，可以用回溯法解决。
• 面试题17：将问题转换成数字排列，用递归实现。

通过以上例子可以看出，回溯算法在解决组合优化问题时表现出色，尤其是在需要枚举所有可能解的情况下。

转载地址：http://cdafz.baihongyu.com/