回溯算法和解数独

yedaoxiaodi 2020-04-19

以前自学数据结构和算法的时候,回溯算法一直没涉及到,当时只听过,也没用过,这两天看到一个数独问题的博客,看下来居然一脸懵逼,这肯定是不能接受的,所以一鼓作气把回溯算法好好品了品,赶紧记下来,巩固一下。

回溯算法,简单来说,其实就是对解空间的一种深度优先搜索(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 组合

给定两个整数 nk,返回 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. 检查皇后放置的位置和之前放置的皇后是否有冲突
  3. 如果没有冲突,跳转到下一行继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计算出此时的坐标);

  1. 依次遍历表格上所有的点;
  2. 检查是否满足约束条件(行、列以及3*3的表格内均不含有该数字),如果满足,递归到下一个坐标点,如果不满足,回溯;
  3. 遍历完成结束。
  • 总结

  其实最早接触递归的时候,就考虑过是否可以将每一次递归记录下来,后来学习动态规划的时候,又考虑是否能对递归树进行剪枝操作,减少递归复杂度;而回溯法一定程度就完成了这两步操作,回溯算法其实就是对解空间进行的一次全局搜索,在一定的约束处理手段下,可以完成剪枝操作,缩减算法的复杂度;但是不可避免的,这种算法的核心还是递归,算法复杂度较高,而这种思想也是传统人工智能的思想,依靠的是算力,与现在大火的机器学习、人工智能不一样,依靠的是计算机+大数据+统计学;

最后就是回溯算法完成的一些细节的地方:

  1. 递归终止条件:这是所有使用递归的前提,必须考虑清楚递归终止条件;
  2. 解的保存形式:比如组合问题,需要的是所有解的集合,所以在终止时,将一个解push_back到res里面进行保存,而解数独问题,只需要找到一个解,所有将每一次递归函数的返回值设置为bool型,如果找到正确解,就逐层返回true,结束递归;

相关推荐