好的建筑设计网站推荐,备案 网站备注,dokuwiki wordpress 整合,策划推广活动方案文章目录 算法介绍回溯算法能解决的问题解题模板1. 组合问题2. N皇后问题 算法介绍
回溯法#xff08;Back Tracking Method#xff09;#xff08;探索与回溯法#xff09;是一种选优搜索法#xff0c;又称为试探法#xff0c;按选优条件向前搜索#xff0c;以达到目标… 文章目录 算法介绍回溯算法能解决的问题解题模板1. 组合问题2. N皇后问题 算法介绍
回溯法Back Tracking Method探索与回溯法是一种选优搜索法又称为试探法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法而满足回溯条件的某个状态的点称为 “回溯点”。
回溯算法实际上一个类似枚举的搜索尝试过程主要是在搜索尝试过程中寻找问题的解当发现已不满足求解条件时就 “回溯” 返回尝试别的路径。
可以把回溯法看成是递归调用的一种特殊形式。
回溯法思路的简单描述是把问题的解空间转化成了图或者树的结构表示然后使用深度优先搜索策略进行遍历遍历的过程中记录和寻找所有可行解或者最优解。
回溯算法能解决的问题
组合问题N个数里面按一定规则找出k个数的集合排列问题N个数按一定规则全排列有几种排列方式切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集棋盘问题N皇后解数独等等
解题模板
代码方面回溯算法的框架
result []
def backtracking(路径, 选择列表):// 确定终止条件if 满足结束条件:result.add(路径)return// 单层搜索for 选择 in 选择列表:做选择backtracking(路径, 选择列表)撤销选择核心就是 for 循环里面的递归在递归调用之前「做选择」在递归调用之后「撤销选择」。
总结就是
循环 递归 回溯
1. 组合问题 class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) {continue;}sum candidates[i];path.push_back(candidates[i]);used[i] true;backtracking(candidates, target, sum, i 1, used); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};这个组合问题中最主要的问题是搞清楚 树层去重 和 树枝去重
2. N皇后问题 class Solution {
public:// 存放不同解法vectorvectorstring result;void backtracking(int n, int row, vectorstring chessboard) {if(row n) {result.push_back(chessboard);return;}for(int colu 0; colu n; colu) {if(IsValid(n, row, colu, chessboard)) { // 验证合法就可以放chessboard[row][colu] Q; // 放置皇后backtracking(n, row 1, chessboard);chessboard[row][colu] .; // 回溯撤销皇后}}}bool IsValid(int n, int row, int colu, vectorstring chessboard) {// 检查放到此处是否有效 同列、对角是否有其他皇后回溯时每行只取一次所以不用检查同行// 向上检查同列是否有皇后for(int i 0; i row; i) {if(chessboard[i][colu] Q) {return false;}}// 检查 135°左上是否有皇后for(int i row-1, j colu - 1; i 0 j 0; i--, j--) {if(chessboard[i][j] Q) {return false;}}// 检查 45°右上是否有皇后for(int i row-1, j colu 1; i 0 j n; i--, j) {if(chessboard[i][j] Q) {return false;}}return true;}vectorvectorstring solveNQueens(int n) {// 棋盘初始化vectorstring chessboard(n, string(n, .));// n:棋盘大小 0从棋盘0行开始选backtracking(n, 0, chessboard);return result;}
};
