以前自學資料結構和演算法的時候，回溯演算法一直沒涉及到，當時只聽過，也沒用過，這兩天看到一個數獨問題的博客，看下來居然一臉懵逼，這肯定是不能接受的，所以一鼓作氣把回溯演算法好好品了品，趕緊記下來，鞏固一下，
回溯演算法，簡單來說，其實就是對解空間的一種深度優先搜索(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，結束遞回；
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/199359.html
標籤：其他