回溯算法和解数独
以前自学数据结构和算法的时候,回溯算法一直没涉及到,当时只听过,也没用过,这两天看到一个数独问题的博客,看下来居然一脸懵逼,这肯定是不能接受的,所以一鼓作气把回溯算法好好品了品,赶紧记下来,巩固一下。
回溯算法,简单来说,其实就是对解空间的一种深度优先搜索(DFS:Depth-First-Search),采用递归的方式,选择方式就是递归树模型,每次做出选择并记录,当进行到某一步,如果由于约束条件限制,无法继续进行时,就退回到上一步重新进行选择,直到找到满足要求的解,这就是回溯算法。
直接上题,做两题就理解了:
- leetcode17 电话号码的字母组合
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
//每一个数字与所能代表的字母的映射关系 vector<string> list = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" }; vector<string> res; void func(const string & digits , int index , const string& s){ //设置终止条件 if(index == digits.size()){ res.push_back(s); //保存一种组合 return ; } char c =digits[index]; string letters = list[c - ‘2‘]; for(int i = 0 ;i < letters.size();++i){ func(digits , index + 1 , s + letters[i]); } }
这题其实没有体现回溯的步骤,主要是采用了值传递和const引用的一些技巧,而且没有约束条件限制,其实就是进行了一次全部解空间的递归遍历;
- leetcode46 全排列
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
vector<vector<int>> res; void func(const vector<int>& nums , int index ,vector<int>& one_res , vector<bool>& mark){ //设置终止条件 if(index == nums.size()) { res.push_back(one_res); return; } for(int i = 0 ; i < nums.size() ; ++i){ if(!mark[i]){ //如果i没有被使用 one_res.push_back(nums[i]); mark[i] = true; //标记 func(nums , index+1 , one_res , mark); one_res.pop_back(); mark[i] = false; //回溯 } } }
- leetcode77 组合
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
vector<vector<int>> res; void func( const int& n , const int& k , int start , vector<int>& p){ if(p.size() == k){ res.push_back(p); return ; } //start=i,此时还需要k-p.size()个元素完成操作,从i到N的闭区间中选择k-p.size()个元素 //i最大为n-(k-p.size())+1 //i从start开始,因为包含start之前数字的解已经包含在res中了,比如[1,4]和[4,1]就是同一个解,避免重复 for(int i = start ; i <= n-(k-p.size())+1; ++i){ p.push_back(i); func(n , k , i + 1 , p); p.pop_back(); } }
上面这几题都比较简单,如果弄懂了这几题,应该对回溯算法就有了一定的理解了,上面这几题对于每一步递归选择都没有使用约束,接下来我们来考虑带约束的递归选择;
- leetcode51 N皇后问题(最出名的就是八皇后问题了)
class Solution { vector<vector<string>> res; vector<bool> col; vector<bool> diag1; vector<bool> diag2; vector<string> transteranswer(int n ,vector<int>& row){ vector<string> oneway (n,string(n,‘.‘)); for(int i = 0 ; i < n ; ++i){ oneway[i][row[i]] = ‘Q‘; } return oneway; } void func(int n ,int index, vector<int>& row){ if(index == n){ res.push_back(transteranswer(n,row)); return ; } for(int i = 0 ;i < n; ++i){ if(!col[i] && !diag1[index+i] && !diag2[index-i+n-1]){//判断是否可以放置皇后 col[i] = true; diag1[index+i] = true; diag2[index-i+n-1] = true; //这三步是标记,表明这一列和两条斜对角线都占用 row.push_back(i); func(n , index+1 , row); col[i] = false; diag1[index+i] = false; diag2[index-i+n-1] = false; row.pop_back(); //这三步是表示选择错误,回溯 } } return ; } public: vector<vector<string>> solveNQueens(int n) { if(n == 0 ) return res; col=vector<bool>(n,false); diag1 = vector<bool>(2*n-1,false); diag2 = vector<bool>(2*n-1,false); vector<int> row; func(n,0,row); return res; } };
这次贴上了完整代码,看着很长,其实思路很简单:
- 遍历每一行所有位置,尝试在每一个位置放置皇后
- 检查皇后放置的位置和之前放置的皇后是否有冲突
- 如果没有冲突,跳转到下一行继1、2操作,直到遍历完最后一行,结束
其实N皇后问题的核心是检查该点是否有冲突,这里引入了三个vector<bool>进行标记,col=vector<bool>(n,false)表示的是该列是否被占用,diag1和diag2分别表示所在对角线是否被占用,这里使用了一点小技巧,位于正对角线上的坐标,其横纵坐标差值都相等,位于反对角线上的坐标,其横纵左边相加的和都相等;
- leetcode37 解数独
其实数独的思路和N皇后问题十分相似,先上代码:
class Solution { char list[9] = {‘1‘,‘2‘,‘3‘,‘4‘,‘5‘,‘6‘,‘7‘,‘8‘,‘9‘}; bool check(vector<vector<char>>& board, int x, int y ,char ch){ //检查第x行中无重复 for(int i = 0 ; i <9 ; i++){ if(board[x][i] == ch){ return false; } } //检查第y行中无重复 for(int i = 0 ; i < 9 ; i++){ if(board[i][y] == ch){ return false; } } //检查坐标(x,y)所位于的3*3中无重复 for(int i = 3*(x/3) ; i <3*(x/3+1);++i){ for(int j = 3*(y/3) ; j <3*(y/3+1);++j){ if(board[i][j]==ch){ return false; } } } return true; } bool func(vector<vector<char>>& board, int num ){ if(num == 81) return true ; int i = num / 9; //当前行数 int j = num % 9; //当前列数 if(board[i][j] != ‘.‘){ if(func(board , num+1)) return true; }else{ for(int k = 0 ; k < 9; k ++){ if(check(board, i , j , list[k])){ board[i][j] = list[k] ; if(func(board , num+1 )) return true; board[i][j] =‘.‘; } } } return false; } public: void solveSudoku(vector<vector<char>>& board) { func(board , 0); } };
整体思路还是很简单的(小技巧:使用num来记录遍历深度,同时也可以用num计算出此时的坐标);
- 依次遍历表格上所有的点;
- 检查是否满足约束条件(行、列以及3*3的表格内均不含有该数字),如果满足,递归到下一个坐标点,如果不满足,回溯;
- 遍历完成结束。
- 总结
其实最早接触递归的时候,就考虑过是否可以将每一次递归记录下来,后来学习动态规划的时候,又考虑是否能对递归树进行剪枝操作,减少递归复杂度;而回溯法一定程度就完成了这两步操作,回溯算法其实就是对解空间进行的一次全局搜索,在一定的约束处理手段下,可以完成剪枝操作,缩减算法的复杂度;但是不可避免的,这种算法的核心还是递归,算法复杂度较高,而这种思想也是传统人工智能的思想,依靠的是算力,与现在大火的机器学习、人工智能不一样,依靠的是计算机+大数据+统计学;
最后就是回溯算法完成的一些细节的地方:
- 递归终止条件:这是所有使用递归的前提,必须考虑清楚递归终止条件;
- 解的保存形式:比如组合问题,需要的是所有解的集合,所以在终止时,将一个解push_back到res里面进行保存,而解数独问题,只需要找到一个解,所有将每一次递归函数的返回值设置为bool型,如果找到正确解,就逐层返回true,结束递归;