【算法】回溯

上期回顾: 【算法】分治
个人主页：GUIQU.
归属专栏：算法

目录

• 1. 回溯算法的基本概念
• 2. 回溯算法的原理
• 3. 回溯算法的常见应用场景
• • 3.1 全排列问题
  • 3.2 组合问题
  • 3.3 数独问题
  • 3.4 N 皇后问题
• 4. 回溯算法的优缺点
• 5. 回溯算法的优化技巧与拓展
• • 5.1 剪枝策略
  • 5.2 与其他算法思想的结合
  • 5.3 回溯算法在实际复杂场景中的拓展应用
  • 5.4 并行化回溯算法的思考

正文

1. 回溯算法的基本概念

回溯算法是一种用于搜索问题解空间的通用算法策略，它采用深度优先搜索（DFS）的方式来遍历所有可能的解。其核心思想是在搜索过程中，当发现当前选择无法通向有效解或者无法得到更优解时（取决于具体问题需求），就“回溯”到上一步，撤销之前的选择，然后尝试其他可能的选择，如此反复，直到找到满足条件的解或者遍历完整个解空间为止。

可以把回溯算法想象成走迷宫，当走进一条死胡同或者发现当前路线走下去不符合要求时，就原路返回，换一个岔路口继续探索，直到找到出口或者确定迷宫没有可行的出口。

2. 回溯算法的原理

回溯算法通常基于递归实现，整体过程大致包含以下几个关键部分：

1. 状态表示：定义问题的状态，比如对于排列组合问题，状态可以是已经选择的元素列表；对于数独问题，状态可以是当前已经填入数字的棋盘状态等。
2. 解空间树构建：将问题的所有可能解看作是一棵多叉树的节点，从根节点开始，每一层的分支代表不同的选择，整个树就涵盖了问题的所有解可能性，称为解空间树。例如，对于全排列问题，解空间树的第一层节点表示第一个位置可选的所有元素，第二层节点表示第二个位置在剩余元素中可选的所有元素，以此类推。
3. 约束条件判断：在搜索过程中，每做出一个选择，都需要判断这个选择是否满足问题给定的约束条件，比如在填数独时，填入的数字要满足每行、每列以及每个小九宫格内数字不重复的条件。如果不满足约束条件，就说明当前路径是错误的，需要回溯。
4. 回溯操作：当发现当前选择不符合要求（不满足约束条件或者已经确定无法得到更优解等情况）时，要回退到上一个状态，撤销之前的操作，恢复现场，然后尝试下一个可能的选择。这一步是回溯算法区别于普通深度优先搜索的关键所在，通过不断地回溯和重新选择，系统地遍历整个解空间。

3. 回溯算法的常见应用场景

3.1 全排列问题

• 原理：
  给定一个包含 n 个不同元素的集合，求其所有可能的排列情况。通过回溯算法，从空排列开始，依次在每个位置上选择还未使用过的元素，每添加一个元素就判断当前排列是否满足条件（在全排列问题中只要长度达到 n 就是一个有效排列），如果长度未达到 n 就继续向下搜索添加元素，如果添加某个元素后发现不符合要求（比如导致后续无法填满所有位置），就回溯，撤销该元素的选择，换另一个元素继续尝试，直到生成所有的全排列。
• 代码示例（C++）：

#include <iostream>
#include <vector>
using namespace std;

// 交换两个元素的函数
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 生成全排列的回溯函数
void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

// 全排列主函数
vector<vector<int>> permute(vector<int> nums) {
    vector<vector<int>> result;
    permute(nums, 0, result);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> permutations = permute(nums);
    cout << "全排列结果为: " << endl;
    for (vector<int> permutation : permutations) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

3.2 组合问题

• 原理：
  从 n 个不同元素中选取 m 个元素的所有组合情况（m <= n）。回溯算法解决组合问题时，同样构建解空间树，在树的每一层决定是否选择当前元素进入组合中。通过一个索引来标记当前考虑的元素位置，每选择一个元素，索引向后移动，同时记录已选元素个数，当已选元素个数达到 m 时，就得到一个有效组合；如果在某个位置发现继续选择元素会超出 m 的限制或者不符合其他约束条件（比如有额外的元素筛选条件），就进行回溯，尝试其他选择，直到找出所有满足条件的组合。
• 代码示例（C++）：

#include <iostream>
#include <vector>
using namespace std;

// 生成组合的回溯函数
void combineCore(vector<int>& nums, int start, int m, vector<int>& combination, vector<vector<int>>& result) {
    if (combination.size() == m) {
        result.push_back(combination);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        combination.push_back(nums[i]);
        combineCore(nums, i + 1, m, combination, result);
        combination.pop_back();
    }
}

// 组合主函数
vector<vector<int>> combine(int n, int m) {
    vector<int> nums;
    for (int i = 1; i <= n; i++) {
        nums.push_back(i);
    }
    vector<vector<int>> result;
    vector<int> combination;
    combineCore(nums, 0, m, combination, result);
    return result;
}

int main() {
    int n = 5;
    int m = 3;
    vector<vector<int>> combinations = combine(n, m);
    cout << "组合结果为: " << endl;
    for (vector<vector<int>> combination : combinations) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

3.3 数独问题

• 原理：
  数独是一个 9×9 的方格棋盘，要求每行、每列以及每个 3×3 的小九宫格内都要填入 1 - 9 的数字，且每个数字在每行、每列和每个小九宫格内只能出现一次。回溯算法解决数独问题时，从棋盘的第一个空格开始，依次尝试填入 1 - 9 中满足约束条件的数字，每填入一个数字就继续去填下一个空格，如果发现填入某个数字后导致后续无法填完整个棋盘（即违反了数独的规则），就回溯，将该空格的数字清除，换另一个数字尝试，直到整个棋盘都填满且满足数独规则为止。
• 代码示例（C++，简单示意核心逻辑，可进一步完善细节）：

#include <iostream>
#include <vector>
using namespace std;

// 判断在数独棋盘的 (row, col) 位置填入 num 是否合法
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num) return false;
        if (board[i][col] == num) return false;
        int startRow = 3 * (row / 3);
        int startCol = 3 * (col / 3);
        if (board[startRow + (i % 3)][startCol + (i / 3)] == num) return false;
    }
    return true;
}

// 回溯解决数独问题的函数
bool solveSudoku(vector<vector<char>>& board) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == '.') {
                for (char num = '1'; num <= '9'; num++) {
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num;
                        if (solveSudoku(board)) return true;
                        board[row][col] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };
    if (solveSudoku(board)) {
        cout << "数独求解成功，结果如下: " << endl;
        for (vector<char> row : board) {
            for (char num : row) {
                cout << num << " ";
            }
            cout << endl;
        }
    } else {
        cout << "无法求解该数独" << endl;
    }
    return 0;
}

3.4 N 皇后问题

• 原理：
  在 N×N 的棋盘上放置 N 个皇后，要求任意两个皇后都不能在同一行、同一列以及同一斜线上。回溯算法解决此问题时，从第一行开始，逐行放置皇后，对于每一行，尝试在每一列放置皇后，然后检查是否与之前放置的皇后冲突（即是否满足不在同一列和同一斜线上的条件），如果冲突就回溯，换另一列尝试，直到在所有行都成功放置皇后，即找到了一个有效解；接着继续回溯寻找其他可能的解，遍历完所有可能的放置情况，得到所有满足条件的解。
• 代码示例（C++，简单示意核心逻辑，可进一步完善细节）：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 判断在 (row, col) 位置放置皇后是否与已放置的皇后冲突
bool isSafe(vector<string>& board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
        int diffRow = row - i;
        int diffCol = abs(col - (int)(board[i].find('Q')));
        if (diffRow == diffCol) return false;
    }
    return true;
}

// 回溯解决 N 皇后问题的函数
void solveNQueensCore(vector<string>& board, int row, int n, vector<vector<string>>& result) {
    if (row == n) {
        result.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            solveNQueensCore(board, row + 1, n, result);
            board[row][col] = '.';
        }
    }
}

// N 皇后问题主函数
vector<vector<string>> solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));
    vector<vector<string>> result;
    solveNQueensCore(board, 0, n, result);
    return result;
}

int main() {
    int n = 4;
    vector<vector<string>> solutions = solveNQueens(n);
    cout << "N 皇后问题（N = " << n << "）的解为: " << endl;
    for (vector<string> solution : solutions) {
        for (string row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}

4. 回溯算法的优缺点

• 优点：

  • 通用性强：回溯算法能够解决一大类搜索问题，尤其是那些解空间可以通过树状结构表示，且需要遍历所有可能解或者寻找满足特定约束条件的解的问题，像排列组合、棋盘布局等多种不同类型的问题都可以用回溯算法来处理。
  • 易于理解和实现：基于递归的实现方式以及清晰的回溯思想，使得代码结构相对直观，只要能正确定义问题的状态、解空间树、约束条件等要素，就比较容易编写回溯算法的代码，相比于一些复杂的数学模型或者特定领域的专业算法，回溯算法的入门门槛较低。

• 缺点：

  • 效率问题：回溯算法本质上是一种暴力搜索算法，它需要遍历解空间树中的大部分甚至全部节点，在问题规模较大时，时间复杂度往往会很高，可能会出现计算时间过长甚至无法在合理时间内得到结果的情况。例如，对于较大的 N 值的 N 皇后问题或者规模庞大的全排列问题等，计算量会急剧增加。
  • 空间占用：由于回溯算法通常采用递归实现，递归过程中会占用系统栈空间来保存每一层的调用信息，当搜索深度较大或者问题规模较大时，容易出现栈溢出等空间不足的问题，需要谨慎处理递归深度和空间使用情况，有时可能需要手动模拟栈来优化空间占用。

尽管存在这些缺点，但回溯算法在很多场景下依然是一种非常有效的解决问题的手段，并且可以通过一些剪枝策略（即提前判断某些分支不可能产生有效解，从而跳过对这些分支的搜索）来优化其效率，减少不必要的搜索，使其在实际应用中能发挥更大的作用。

5. 回溯算法的优化技巧与拓展

5.1 剪枝策略

• 原理与应用：
  剪枝是提高回溯算法效率的关键技巧。其核心思路是在搜索过程中，根据问题的约束条件和已有信息，提前判断某些子树（解空间树中的分支）不可能包含有效解，从而直接跳过对这些子树的搜索，减少不必要的计算量。例如，在数独问题中，如果某一行已经确定某个数字只能出现在某些位置，那么在其他位置尝试填入该数字的分支就可以直接剪掉；在组合问题中，如果当前已选元素个数加上剩余可选元素个数都小于要求的组合元素个数 m，那么就可以直接结束当前搜索分支，因为不可能再生成满足条件的组合了。

• 代码示例（以组合问题剪枝为例，对前面组合代码进行优化）：

#include <iostream>
#include <vector>
using namespace std;

// 生成组合的回溯函数（加入剪枝策略）
void combineCore(vector<int>& nums, int start, int m, vector<int>& combination, vector<vector<int>>& result) {
    if (combination.size() == m) {
        result.push_back(combination);
        return;
    }
    // 剪枝判断，剩余可选元素个数不足 m - combination.size() 时直接返回
    int remaining = nums.size() - start;
    if (remaining < m - combination.size()) {
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        combination.push_back(nums[i]);
        combineCore(nums, i + 1, m, combination, result);
        combination.pop_back();
    }
}

// 组合主函数
vector<vector<int>> combine(int n, int m) {
    vector<int> nums;
    for (int i = 1; i <= n; i++) {
        nums.push_back(i);
    }
    vector<vector<int>> result;
    vector<int> combination;
    combineCore(nums, 0, m, combination, result);
    return result;
}

int main() {
    int n = 5;
    int m = 3;
    vector<vector<int>> combinations = combine(n, m);
    cout << "组合结果为: " << endl;
    for (vector<vector<int>> combination : combinations) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

5.2 与其他算法思想的结合

• 回溯与动态规划结合：
  在一些问题中，可以将回溯算法与动态规划思想相结合来提高效率。动态规划通过记录已经求解过的子问题的结果，避免重复计算，而回溯算法在搜索过程中往往会多次遇到相同的子问题情况，尤其是当子问题之间存在重叠时。
  在计算有重复元素的全排列问题时，可以先用动态规划的思想记录每个子排列是否已经被计算过。在回溯生成全排列的过程中，每次要扩展一个新状态时，先检查对应的子排列在动态规划的记录结构（比如一个哈希表）中是否已经存在，如果存在就直接跳过这个重复的分支，避免重复搜索，从而减少计算量。这样结合了回溯的搜索框架和动态规划的“记忆化”优势，提升整体算法效率。

• 回溯与贪心算法结合：
  以任务调度问题为例，假设有多个任务，每个任务有执行时间和截止时间等属性，要安排任务执行顺序使得尽可能多的任务能在截止时间内完成。可以先用贪心算法按照一定的策略（比如按照截止时间从小到大对任务进行排序等）对任务进行一个初步的排序和筛选，得到一个相对较优的初始状态。然后在此基础上运用回溯算法，去搜索可能更好的任务排列顺序，在回溯过程中，由于已经有了贪心算法得到的初始较优解作为参考，就可以更有针对性地进行剪枝操作，比如如果当前尝试的任务排列顺序明显比贪心得到的解还差（完成的任务数量更少等），那就可以提前回溯，不再继续深入搜索这个分支，通过这种结合，既能利用贪心算法快速得到一个近似最优解的优势，又能通过回溯算法进一步探索是否存在更优解。

5.3 回溯算法在实际复杂场景中的拓展应用

• 旅行商问题（TSP - Traveling Salesman Problem）的简化应用：
  旅行商问题要求一名推销员要遍历多个城市且每个城市只能访问一次，并最终回到起始城市，要找到总路程最短的访问路线。回溯算法解决这个问题时，将所有可能的城市访问顺序看作解空间树，从起始城市开始，依次尝试下一个要访问的城市，每选择一个城市就记录下来路径长度，并判断是否满足约束条件（每个城市仅访问一次），如果路径长度已经超过当前已知的最短路径或者违反了城市访问规则，就回溯换其他城市继续尝试。虽然对于大规模的旅行商问题，单纯的回溯算法效率极低，但在一些简化场景下，比如城市数量较少或者对精度要求不是特别高，结合一些有效的剪枝策略（如基于当前已走过的路程和估计剩余城市最短连接路程来判断是否还有继续探索的必要等），回溯算法可以找到可行的旅行路线解。

• 背包问题的变种应用：
  常规的 0 - 1 背包问题是在给定背包容量和若干物品（每个物品有重量和价值属性）的情况下，选择物品放入背包使得背包价值最大且不超重。其变种可能会增加更多约束条件，比如物品有类别限制，某些类别物品只能选几个等。回溯算法处理这类变种问题时，在搜索选择物品放入背包的过程中，除了考虑重量和价值这些常规因素以及新的类别等约束条件外，同样按照回溯的思路，当发现当前选择物品的组合违反了任何约束条件或者不可能得到比当前最优价值更高的情况时，就进行回溯操作，重新选择物品，通过合理定义状态、约束判断和回溯机制，可以解决这类背包问题的复杂变种，尽管同样面临效率问题，但在小规模数据或者特定要求场景下是可行的解决办法。

5.4 并行化回溯算法的思考

随着计算机硬件多核处理器以及分布式计算环境的发展，考虑将回溯算法并行化来提高效率是很有意义的。由于回溯算法搜索解空间树的各分支相对独立（在不考虑剪枝等相互影响的情况下），理论上可以将解空间树的不同分支分配给不同的计算核心或者计算节点去并行搜索。

例如，在全排列问题中，如果有多个处理器核心，可以将生成全排列的不同起始元素分支（比如第一个位置选不同数字的分支）分配给不同核心同时进行搜索，每个核心独立地完成自己负责分支下的回溯搜索过程，最后汇总结果。但实际实现并行化回溯算法时，需要处理好共享数据的访问冲突问题（比如记录当前最优解等全局数据可能被多个并行线程或进程访问修改）、任务分配和协调机制等复杂问题，并且不是所有的回溯问题都能简单高效地实现并行化，需要根据具体问题的特点和计算环境进行合理设计和优化。

结语
感谢您的阅读！期待您的一键三连！欢迎指正！