概念
回溯算法(Backtracking)是一种用于寻找所有可能解的算法。它通过递归构建解,并在发现当前解不符合条件时进行“回溯”撤销部分选择,直到找到有效的解或没有更多可能性时停止。回溯算法常用于求解组合、排列、子集、图的遍历等问题。
基本思想
- 选择:在某个阶段做出一个选择。
- 约束:判断当前选择是否符合问题的约束条件。
- 递归:如果当前选择符合约束,则递归进行下一阶段的选择。
- 回溯:如果当前选择不符合约束或者所有可能的选择都已经尝试过,就回到上一个阶段,撤销当前选择,进行新的选择。
通用模板
void backtrack(状态变量) {
// 终止条件:如果满足终止条件,输出解或做其他操作
if (满足终止条件) {
return;
}
// 遍历所有可能的选择
for (每一个选择) {
// 做出选择
做出选择();
// 递归进入下一层
backtrack(更新后的状态);
// 撤销选择
撤销选择();
}
}
步骤:
-
定义状态变量:定义能够描述当前解空间的变量。
-
递归过程:根据当前状态进行选择,进入下一层递归。
-
终止条件:当当前状态满足某个条件时,输出结果。
-
回溯过程:当递归返回时,需要撤销当前选择,回到上一步。
经典算法
全排列问题
给定一个没有重复数字的数组,返回其所有可能的全排列。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
vector<bool> used(nums.size(), false);
backtrack(nums, current, used, result);
return result;
}
private:
void backtrack(vector<int>& nums, vector<int>& current, vector<bool>& used, vector<vector<int>>& result) {
if (current.size() == nums.size()) {
result.push_back(current);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue; // 跳过已使用的元素
current.push_back(nums[i]);
used[i] = true;
backtrack(nums, current, used, result); // 递归
current.pop_back(); // 撤销选择
used[i] = false;
}
}
};
int main() {
vector<int> nums = {1, 2, 3};
Solution solver;
vector<vector<int>> result = solver.permute(nums);
for (const auto& perm : result) {
for (int num : perm) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
代码说明:
permute
方法返回所有的排列。- 使用一个布尔数组
used
来标记当前数字是否已经使用,避免重复选择。 - 每次递归选择一个数字,直到当前的排列长度达到
nums.size()
,此时就添加一个解。 - 回溯是通过撤销选择来完成的。
组合问题
给定一个数组 candidates
和一个目标值 target
,返回所有和为 target
的组合,要求数组中的数字可以重复选择。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> current;
backtrack(candidates, target, 0, current, result);
return result;
}
private:
void backtrack(vector<int>& candidates, int target, int start, vector<int>& current, vector<vector<int>>& result) {
if (target == 0) {
result.push_back(current);
return;
}
if (target < 0) return; // 剪枝,目标值已小于0,不需要继续
for (int i = start; i < candidates.size(); ++i) {
current.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], i, current, result); // 允许重复选择,i不变
current.pop_back(); // 撤销选择
}
}
};
int main() {
vector<int> candidates = {2, 3, 6, 7};
int target = 7;
Solution solver;
vector<vector<int>> result = solver.combinationSum(candidates, target);
for (const auto& comb : result) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
代码说明:
- 允许重复使用元素,递归过程中通过
start
来控制每次从当前数字开始选择。 - 剪枝条件:当
target
小于 0 时,递归立即返回。 - 当
target
等于 0 时,当前组合是一个有效解。
子集问题
给定一个整数数组 nums
,返回所有可能的子集(即幂集)。子集中的元素可以出现多次。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
backtrack(nums, 0, current, result);
return result;
}
private:
void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
result.push_back(current); // 每次递归都会产生一个子集
for (int i = start; i < nums.size(); ++i) {
current.push_back(nums[i]);
backtrack(nums, i + 1, current, result); // 不允许重复选择相同的元素
current.pop_back(); // 撤销选择
}
}
};
int main() {
vector<int> nums = {1, 2, 3};
Solution solver;
vector<vector<int>> result = solver.subsets(nums);
for (const auto& subset : result) {
for (int num : subset) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
代码说明:
subsets
方法返回所有的子集。- 每次递归都会将当前子集添加到结果中。
- 通过
start
控制从哪个位置开始选择元素,避免重复选择。
数独问题
给定一个数独的未完成的棋盘,填写空格使其符合数独规则。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool solveSudoku(vector<vector<char>>& board) {
return backtrack(board);
}
private:
bool backtrack(vector<vector<char>>& board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') { // 找到一个空格
for (char num = '1'; num <= '9'; ++num) {
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (backtrack(board)) return true; // 递归
board[i][j] = '.'; // 撤销选择
}
}
return false; // 如果没有合法数字,返回false
}
}
}
return true; // 如果所有空格都填满,返回true
}
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;
}
// 检查列是否有重复数字
for (int i = 0; i < 9; ++i) {
if (board[i][col] == num) return false;
}
// 检查3x3的小方块是否有重复数字
int startRow = row / 3 * 3;
int startCol = col / 3 * 3;
for (int i = startRow; i < startRow + 3; ++i) {
for (int j = startCol; j < startCol + 3; ++j) {
if (board[i][j] == num) return false;
}
}
return true;
}
};
int main() {
vector<vector<char>> board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '8', '.', '.', '.', '3', '7'},
{'4', '.', '8', '.', '.', '3', '.', '.', '2'},
{'7', '.', '.', '5', '.', '6', '8', '.', '9'},
{'.', '6', '.', '.', '.', '2', '3', '.', '.'},
{'.', '.', '4', '1', '8', '.', '.', '5', '6'},
{'.', '9', '5', '.', '.', '.', '7', '.', '.'}
};
Solution solver;
solver.solveSudoku(board);
for (const auto& row : board) {
for (char cell : row) {
cout << cell << " ";
}
cout << endl;
}
return 0;
}
代码说明:
solveSudoku
方法通过回溯填充数独棋盘。- 对每个空格,尝试放入 1 到 9 中的数字,并检查是否合法(行、列、3x3子网格没有重复)。
- 如果某个数字合法,递归继续。如果不能填入合法数字,撤销并尝试其他数字。
八皇后问题
八皇后问题: 在一个8x8的棋盘上放置8个皇后,使得它们互不攻击。
#include <iostream>
#include <vector>
using namespace std;
class NQueens {
public:
NQueens(int n) : n(n) {
board = vector<vector<char>>(n, vector<char>(n, '.'));
}
// 回溯算法的入口
void solve() {
backtrack(0); // 从第0行开始
}
private:
int n; // 皇后数目
vector<vector<char>> board; // 棋盘
// 打印当前棋盘
void printBoard() {
for (const auto& row : board) {
for (char c : row) {
cout << c << " ";
}
cout << endl;
}
}
// 判断当前行、列和对角线上是否有冲突
bool isSafe(int row, int col) {
// 检查列是否有皇后
for (int i = 0; i < row; ++i) {
if (board[i][col] == 'Q') return false;
}
// 检查主对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') return false;
}
// 检查副对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') return false;
}
return true;
}
// 回溯算法,尝试放置皇后
void backtrack(int row) {
if (row == n) { // 如果所有皇后都已经放置好了,打印棋盘
printBoard();
cout << "-------------------" << endl;
return;
}
for (int col = 0; col < n; ++col) {
if (isSafe(row, col)) {
board[row][col] = 'Q'; // 放置皇后
backtrack(row + 1); // 尝试放置下一行的皇后
board[row][col] = '.'; // 撤销选择,回溯
}
}
}
};
int main() {
int n = 8;
NQueens solver(n);
solver.solve(); // 解8皇后问题
return 0;
}
代码说明:
-
isSafe():检查某个位置
(row, col)
是否安全,即该位置是否被其他皇后攻击。需要检查同一列、主对角线和副对角线。 -
backtrack():递归地尝试在每一行放置一个皇后。如果当前行的某个列没有冲突,就将皇后放到该位置,并递归尝试下一行的放置;如果某个位置放置失败,撤销该选择,继续尝试下一个列。
-
printBoard():打印当前棋盘的状态。
应用
回溯算法广泛应用于以下几类问题:
- 排列问题:如全排列、排列组合等。
- 子集问题:如给定一个集合,求其所有子集。
- 图的遍历:如深度优先搜索(DFS)等。
- 数独问题:通过回溯求解数独。
- N皇后问题:如上面提到的8皇后问题。
总结
回溯算法通过递归地构建解,并在发现当前路径不符合要求时回退并尝试其他路径。它非常适用于解空间较大。
标签:nums,int,c++,current,算法,vector,result,回溯,board From: https://blog.csdn.net/www_dong/article/details/143530840