首页 > 编程语言 >c++ 回溯算法

c++ 回溯算法

时间：2024-11-10 21:14:41浏览次数：6  
标签：nums int c++ current 算法 vector result 回溯 board

概念

回溯算法（Backtracking）是一种用于寻找所有可能解的算法。它通过递归构建解，并在发现当前解不符合条件时进行“回溯”撤销部分选择，直到找到有效的解或没有更多可能性时停止。回溯算法常用于求解组合、排列、子集、图的遍历等问题。

基本思想

  1. 选择：在某个阶段做出一个选择。
  2. 约束：判断当前选择是否符合问题的约束条件。
  3. 递归：如果当前选择符合约束，则递归进行下一阶段的选择。
  4. 回溯：如果当前选择不符合约束或者所有可能的选择都已经尝试过，就回到上一个阶段，撤销当前选择，进行新的选择。

通用模板

void backtrack(状态变量) {
    // 终止条件：如果满足终止条件，输出解或做其他操作
    if (满足终止条件) {
        return;
    }
    
    // 遍历所有可能的选择
    for (每一个选择) {
        // 做出选择
        做出选择();
        
        // 递归进入下一层
        backtrack(更新后的状态);
        
        // 撤销选择
        撤销选择();
    }
}

步骤：

  1. 定义状态变量：定义能够描述当前解空间的变量。

  2. 递归过程：根据当前状态进行选择，进入下一层递归。

  3. 终止条件：当当前状态满足某个条件时，输出结果。

  4. 回溯过程：当递归返回时，需要撤销当前选择，回到上一步。

经典算法

全排列问题

给定一个没有重复数字的数组，返回其所有可能的全排列。

#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

相关文章

  • C++中string字符串的基础操作，学习
    string字符串常用函数substring()string.length()&&string.size()string.find()string.replace()string.substr()string初始化和声明#include<bits/stdc++.h>usingnamespacestd; intmain(){stringstr1;//空字符串stringstr2="hello,w......
  • 【优化参数】粒子群算法PSO求解三轴稳定航天器姿态控制PD参数优化问题【含Matlab源码
    ......
  • 【优化求解】蚁群算法ACO求解经济损失的航班延误恢复优化问题（目标函数：航班延误成本最
    ......
  • 哈希算法（开散列）- 支持string（this指针指向的理解）
    一.开散列的定义闭散列（开放地址法）的缺点是线性探测和二次探测都会存在哈希冲突的问题，数据越多冲突就会越明显，导致查询数据的时间复杂度大幅度提升个人思路：创建一个指针数组，当某个位置要插入一个数据，就再创建一个数组，指针数组对应位置的指针指向此数组的首元素（数组地址），......
  • C++实现命令行文本计数统计程序
    附上一位博主写的关于git的使用（个人感觉非常完整，对新手很友好）：Git及Tortoisegit下载安装及使用详细配置过程_tortoisegit下载远程代码-CSDN博客 Gitee地址：https://gitee.com/wnmdsqwnhkmc/second-assignment注：本文并不包含主函数，完整代码请移步Gitee路径：[项目>>ConsoleAppl......
  • C++中的RAII与内存管理
    C++中的RAII与内存管理引言资源获取即初始化（ResourceAcquisitionIsInitialization，简称RAII）是C++编程中一种重要的编程范式，它通过对象生命周期来管理资源，确保资源在不再需要时能够被正确释放。本文将从C++的内存布局入手，逐步深入到栈区、堆区的概念，new和delete的操作原理，最终......
  • 浅谈C++（2）
    hi，大家好，我们又见面了今天我继续来讲C++2:变量变量是什么？变量像一个盒子，里面的内容是可以更改的变量的定义：inta;如上代码段，是定义了一个为整数类型的变量a你可以使用cin>>a;来使它变成另一个值解释int是一种变量类型，只储存整数a是变量名;分号，分隔每一......
  • 找质数程序C++
    找质数程序C++今天看报纸时看到目前算出来最大的质数是2136279841-1于是自编了一串代码，分享给大家（ps:怕电脑冒烟的慎用）#include<iostream>usingnamespacestd;intmain(){ for(longlongi=9574463;;i+=2){ if(i%2!=0&&i%3!=0&&i%5!=0&&i%7!=0&&i%......
  • c++程序设计基础实验三
    任务1：源代码：button.hpp:#pragmaonce#include<iostream>#include<string>usingstd::string;usingstd::cout;//按钮类classButton{public:Button(conststring&text);stringget_label()const;voidclick();priva......
  • (5)---【DDA画线算法】C语言-OpenGL库-计算机图形学
    本次实验项目         DDA画线算法理解与运用。算法介绍        DDA（DigitalDifferentialAnalyzer）画线算法是一种基于数值微分原理的直线生成算法。它主要用于在光栅系统中绘制直线，即在像素点阵中生成直线。DDA算法的核心思想是从一个端点开始，通过增量，逐......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99