回溯算法

原创

ge3m0r

发布于 2024-11-24 20:42:34

17200

代码可运行

文章被收录于专栏：数据结构与算法专栏数据结构与算法专栏

运行总次数：0

代码可运行

大多数遍历的算法都离不开深搜或者广搜,当然动态规划是另一种形式的搜索,或者说递推,所以说回溯算法算是另外一种深搜,当然算力在算力有限的情况下,我们需要剪枝优化我们的搜索,不过对于初学者来说,没必要先进行剪枝,先把回溯算法给写出来然后在进行优化.

鉴于回溯的思想用文字讲解比较费力,我们就使用三道例题来简单练习一下回溯算法,鉴于 c 语言的很多数据结构都没有封装,为了简单,这里用 c++ 来实现.

N 皇后问题

N 皇后问题是一个典型的回溯问题,国际象棋中的皇后可以杀死水平垂直斜线上所有的棋子, n 皇后问题就是在一个 n*n 的棋盘上,将 n 个皇后摆在棋盘上,使所有的皇后可以共存.

show me the code

在写代码之前,我们可以先写一个我们的思路

我们可以遍历整个棋盘,找到一个点之后,我们如果确认可以在某个点落子,我们有两种选择,一种是落子,一种是不落子,因此我们先在这个点上落点,如果这个点不会产生问题,我们以加入这个点进行递归,直到搜索所有可能,然后搜索完之后,如果这条搜索不可行,然后我们再将改成落子前的状态.

class Solution {
 public:
  int count = 0;
  int solveNQueues(int n) {
      vector<vector<bool>> board(n, vector<bool>(n, false));
      recur(board, 0);
      return count;
  }

  void recur(vector<string> &board, int step) {
      if (step == board.size()) {
          count++;
          return;
      }

      for (int j = 0; j < board.size(); ++j) {
          if (check(board, step, j)) {
              board[step][j] = true;
              recur(board, step + 1);
              board[step][j] = false;
          }
      }
  }

  bool check(vector<vector<bool>> &board, int row, int col) {
      // 检查列
      for (int i = 0; i < row; ++i) {
          if (board[i][col] == true) return false;
      }
      // 检查行
      for(int i = 0; i < col; i++){
          if(board[row][i] == true) return false;
      }

      // 检查 左上 -> 右下
      for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
          if (board[i][j] == true) return false;
      }

      // 检查 左下 - > 右上
      for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); --i, ++j) {
          if (board[i][j] == true) return false;
      }

      return true;
  }
};

代码较为简单,首先就是检查函数,判断是否可以落点,这里有一个变化就是我们直到每个 step 表示一行, 但是落点到那一列,我们需要通过一个循环进行遍历.

手机号码

老式诺基亚手机按键如图所示，每个 2~9之间的数字按键都对应3或4个不同的小写字母。给定一串数字（只包含数字 2~9），按照字典序从小到大返回可以表示的所有字符串。

关于这一题目思路就不在赘述,就是直接从代码开始.

class solution{
private:
    // 哈希表
    unordered_map<char, string> digitToChars;

    // dfs 深搜函数
    // 我们可以分析一下我们的函数需要什么,首先肯定有我们输入的数组字符串  digits, 另外可以标记我们搜到那个 digits 下标索引  index ,另外就是一个构成的字符串和一个存储所有可能的字符串集合.
    void dfs(const string& digits, int index, string& strs, vector<string> & res){
        // digits.length()-1 表示最后一个字符, 所以退出机制里边是这个
        if(index == digits.length()){
            res.push_back(strs);
            return ;
        }
        // 这个按键里边所有字符串
        string chars = digitToChars[digits[index]];
        for(char ch: chars){
            strs[index] = ch;
            dfs(digits, index + 1, strs, res);
            strs[index] = ' ';
        }

    } 
public:
    // 我们需要在类构造过程中就把哈希表填充好,因此有构造函数
    solution(){
        digitToChars['2'] = "abc"; 
        digitToChars['3'] = "def";
        digitToChars['4'] = "ghi";
        digitToChars['5'] = "jkl";
        digitToChars['6'] = "mno";
        digitToChars['7'] = "pqrs";
        digitToChars['8'] = "tuv";
        digitToChars['9'] = "wxyz";
    }
    // 根据深搜,那么函数就很好些了
    vector<string> digitsToChars(string digits) {
        vector<string> res;
        if (digits.empty()) {
            return res;
        }
        string strtmp(digits.length(), ' ');
        dfs(digits, 0, strtmp, res);
        return res;
    }

};

总体两个题目很难说清楚回溯,但是我们可以体会回溯,其实主要依托深搜,所以练好深搜,那么回溯就很容易理解.

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

算法