深入淺出回溯算法

語言: CN / TW / HK

開啟掘金成長之旅!這是我參與「掘金日新計劃 · 12 月更文挑戰」的第23天,點擊查看活動詳情

一,如何理解回溯算法

深度優先搜索算法利用的就是回溯算法思想,但它除了用來指導像深度優先搜索這種經典的算法設計之外,還可以用在很多實際的軟件開發場景中,比如正則表達式匹配、編譯原理中的語法分析等。

除此之外,很多經典的數學問題都可以用回溯算法解決,比如數獨、八皇后、0-1 揹包、圖的着色、旅行商問題、全排列等等。

回溯的處理思想,有點類似枚舉搜索。暴力枚舉所有的解,找到滿足期望的解。為了有規律地枚舉所有可能的解,避免遺漏和重複,我們把問題求解的過程分為多個階段。每個階段,我們都會面對一個岔路口,我們先隨意選一條路走,當發現這條路走不通的時候(不符合期望的解),就回退到上一個岔路口,另選一種走法繼續走。

回溯算法的模板代碼總結如下:

cpp void backtracking(參數) { if (終止條件) { 存放結果; return; } for (選擇:本層集合中元素(樹中節點孩子的數量就是集合的大小)) { 處理節點; backtracking(路徑,選擇列表); // 遞歸 回溯,撤銷處理結果 } }

二,回溯算法的經典應用

2.1,八皇后問題

有一個 8x8 的棋盤,希望往裏放 8 個棋子(皇后),每個棋子所在的行、列、對角線都不能有另一個棋子。這裏的“對角線”指的是所有的對角線,不只是平分整個棋盤的那兩條對角線。

解決思路:可以把這個問題劃分成 8 個階段,依次將 8 個棋子放到第一行、第二行、第三行……第八行,每一行都有 8 中放法(8 列)。在放置的過程中,我們不停地檢查當前放法,是否滿足要求。如果滿足,則跳到下一行繼續放置棋子;如果不滿足,那就再換一種放法,繼續嘗試。這裏用的是回溯思想,而回溯算法也非常適合用遞歸代碼實現。

```cpp // N 皇后問題 leetcode 51 https://leetcode-cn.com/problems/n-queens/ class Solution { private: vector> result; void backtracking(int n, int row, vector& chessboard){ if(row == n) { result.push_back(chessboard); return; } for(int column=0; column < n; column++){ // 每一行都有8中放法 if (isOK(row, column, n, chessboard)){ chessboard[row][column] = 'Q'; // 放置皇后 backtracking(n, row+1, chessboard); chessboard[row][column] = '.'; // 回溯,撤銷處理結果 } } } // 判斷 row 行 column 列放置皇后是否合適 bool isOK(int row, int column, int n, vector& chessboard){

    int leftup = column - 1; int rightup = column + 1;  // 左上角和右上角

    for(int i = row-1; i>=0; i--){  // 逐行網上考察每一行
        // 判斷第 i 行的 column 列是否有棋子
        if(chessboard[i][column] == 'Q') {
            return false;
        }
        // 考察左上對角線:判斷第i行leftup列是否有棋子   
        if(leftup >=0 ){
            if(chessboard[i][leftup] == 'Q') return false;
        }
        // 考察左上對角線:判斷第i行rightup列是否有棋子
        if(rightup < n){
            if(chessboard[i][rightup] == 'Q') return false;
        }
        --leftup;
        ++rightup;
    }
    return true;
}

public: vector> solveNQueens(int n) { result.clear(); std::vector chessboard(n, std::string(n, '.'));

    backtracking(n, 0, chessboard);
    return result;
}

}; ```

2.2,0-1 揹包問題

0-1 揹包是非常經典的算法問題。0-1 揹包問題有很多變體,這裏介紹一種比較基礎的。我們有一個揹包,揹包總的承載重量是 W kg。現在我們有 n 個物品,每個物品的重量不等,並且不可分割,即對於每個物品來説,都有兩種選擇,裝進揹包或者不裝進揹包,對於 n 個物品來説,總的裝法就有 2^n 種。

我們現在期望選擇幾件物品,裝載到揹包中。在不超過揹包所能裝載重量 W 的前提下,如何讓揹包中物品的總重量最大?

0-1 揹包問題為什麼不能用貪心算法求解?

因為不可分割,所以無法判斷當前情況下,哪種物品對期望值貢獻更大,即不存在當前最優的選擇,所以就無法使用貪心算法了。

0-1 揹包問題的高效解法是動態規劃算法,但也可用沒那麼高效的回溯方法求解。我們可以把物品依次排列,整個問題就分解為了 n 個階段,每個階段對應一個物品怎麼選擇。先對第一個物品進行處理,選擇裝進去或者不裝進去,然後再遞歸地處理剩下的物品。

```cpp int maxW = 0;

// cw 表示當前裝進揹包的物品的重量和,w 表示揹包承載的重量 // items 表示物體的重量數組,n 表示總的物品個數, i 表示考察到第 i 個物品 int f(int i, int cw, vector items, int n, int w){ // 遞歸結束條件:cw == w 表示揹包已經裝滿,i==n 表示考察完所有物品 if(cw == w || i == n){ if(cw > maxW) maxW = cw; return; } f(i+1, cw, items, n, w); // 不裝 // 剪枝過程,當裝入的物品重量大於揹包的重量,就不繼續執行 if(cw+items[i] <= w){ f(i+1, cw+items[i], items, n, w); // 裝 } } ```

要理解 0-1 揹包問題回溯解法的關鍵在於:對於一個物品而言,只有兩種情況,不裝入揹包和裝入揹包兩種情況。對應的就是 f(i+1, cw, items, n, w)f(i+1, cw + items[i], items, n, w) 兩個函數。

2.3,通配符匹配

假設正則表達式中只包含 “*”“?” 這兩種通配符,並且對這兩個通配符的語義稍微做些改變,其中,“*” 匹配任意多個(大於等於 0 個)任意字符,“?” 匹配零個或者一個任意字符。基於以上背景假設,如何用回溯算法,判斷一個給定的文本,是否和給定的正則表達式匹配?

如果遇到特殊字符的時候,我們就有多種處理方式了,也就是所謂的岔路口,比如 “*” 有多種匹配方案,可以匹配任意個文本串中的字符,我們就先隨意的選擇一種匹配方案,然後繼續考察剩下的字符。如果中途發現無法繼續匹配下去了,我們就回到這個岔路口,重新選擇一種匹配方案,然後再繼續匹配剩下的字符。

```cpp // 暴力遞歸 --> 記憶化 --> DP --> 狀態壓縮DP;

class Solution{ private: bool matched = false;

void backtracking(int ti, int pj, string text, string pattern){
    if (matched) return;

    if(pj == pattern.size()){  // 正則表達式到末尾了
        if(ti == text.size())
            matched = true;
        return;
    }
    // *匹配任意個字符
    if(pattern[pj] == '*'){
        for(int k=0; k< text.size()-ti;k++)
            backtracking(ti+k, pj+1, text, pattern);
    }
    // ?匹配0個或者1個字符
    else if(pattern[pj] == '?'){
        backtracking(ti, pj+1, text, pattern);
        backtracking(ti+1, pj+1, text, pattern);
    }
    // 純字符匹配才行      
    else if(ti < pattern.size() && pattern[pj] == text[ti]) { 
        backtracking(ti+1, pj+1, text, pattern);
    }
}

public: bool isMatch(string text, string pattern){ matched = false; backtracking(0, 0, text, pattern); return matched; } }; ```

2.4,leetcode 正則表達式匹配

leetcode 也有變形題(leetcode10:正則表達式匹配)如下:

其他變形題:leetcode44-通配符匹配

給你一個字符串 s 和一個字符規律 p,請你來實現一個支持 '.' 和 '*' 的正則表達式匹配。

  • '.' 匹配任意單個字符
  • '*' 匹配零個或多個前面的那一個元素

所謂匹配,是要涵蓋整個字符串 s 的,而不是部分字符串。

方法一:回溯(分階段分情況討論,暴力搜索和剪枝)

首先,考慮特俗字符只有 '.' 的情況。這種情況會很簡單:我們只需要從左到右依次判斷 s[i] 和 p[i] 是否匹配。

```python def isMatch(self,s:str, p:str) -> bool: """字符串 s 和字符規律 p""" if not p: return not s # 邊界條件

first_match = s and p[0] in {s[0],'.'}  # 比較第一個字符是否匹配

return first_match and self.isMatch(s[1:], p[1:])

```

最後,考慮有 ’*' 的情況,它會出現在 p[1] 的位置,匹配過程中會出現兩種情況:

  • 星號代表匹配 0 個前面的元素。如 '##'a*##,這時我們直接忽略 pa*,比較 ####,也就是繼續遞歸比較 sp[i + 2:]
  • 星號代表匹配一個或多個前面的元素。如 aaaba*b,這時我們將忽略 s 的第一個元素,比較 aaba*b,也就是繼續遞歸比較 s[i + 1:]p。(這裏默認要檢查 s[0]p[0] 是否相等)。

Python3 代碼如下:

```python class Solution: def isMatch(self, s: str, p: str) -> bool: if not p: return not s first_match = bool(s and p[0] in {s[0],'.'}) # 比較第一個字符是否匹配

    if len(p) >=2 and p[1] == '*':
        # * 匹配前面一個字符 0 次或者多次
        return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
    else:
        return first_match and self.isMatch(s[1:], p[1:])

```

C++ 代碼如下:

```cpp // letcode10 正則表達式匹配

include

include

using namespace std;

class Solution{ public: bool isMatch(string s, string p){ // 如果正則串 p 為空字符串,s 也為空,則匹配成功 if(p.empty()) return (s.empty()); // 判斷 s 和 p 的首字符是否匹配,注意要先判斷 s 不為空 bool match = (!s.empty()) && (s[0] == p[0] || p[0] == '.'); // 如果p的第一個元素的下一個元素是 ,則分別對兩種情況進行判斷 if(p.size() >= 2 && p[1] == ''){ // * 匹配前面一個字符 0 次或者多次 return isMatch(s, p.substr(2)) || (match && isMatch(s.substr(1), p)); } else{ // 單個匹配 return match && isMatch(s.substr(1), p.substr(1)); }

}

}; ```

直接遞歸時間複雜度太大(指數級),可以把之前的遞歸過程記錄下來,用空間換時間。記憶化遞歸C++ 代碼如下:

```cpp class Solution{ public: bool isMatch(string s, string p){ unordered_map memo; return backtracking(s, 0, p, 0, memo); }

bool backtracking(string s, int i, string p, int j, unordered_map<int, bool> & memo){
    // # 檢查 s[i] 是否能被匹配,注意要先判斷 s 不為空
    bool match = (i < s.size()) && (s[i] == p[j] || p[j] == '.');

    if(j >= p.size()) return i >= s.size();  // p 和 s 同時遍歷完

    int key = i * (p.size() + 1) + j; // 哈希鍵
    if (memo.find(key) != memo.end()) // 這個狀態之前經歷過,可以返回結果
        return memo[key];

    else if (i == s.size() && j == p.size()) // 如果s和p同時用完,匹配成功
        return memo[key] = true;

    else if((p.size()-j) >= 2 && p[j+1] == '*'){
        // * 匹配前面一個字符 0 次或者多次
        if(backtracking(s, i, p, j+2, memo) || match && backtracking(s, i+1, p, j, memo))
            return memo[key] = true;
    }
    else { // 單個匹配
        if(match && backtracking(s, i+1, p, j+1, memo))
            return memo[key] = true;
    }
    return memo[key] = false; // 沒轍了,匹配失敗
}

}; ```

方法二:動態規劃法

  • [ ] 算法思路
  • [ ] 代碼

三,總結

回溯算法的思想非常簡單,大部分情況下,都是用來解決廣義的搜索問題,也就是,從一組可能的解中,選擇出一個滿足要求的解。回溯算法非常適合用遞歸來實現,在實現的過程中,剪枝操作是提高回溯效率的一種技巧。利用剪枝,我們並不需要窮舉搜索所有的情況,從而提高搜索效率。

儘管回溯算法的原理非常簡單,但是卻可以解決很多問題,比如我們開頭提到的深度優先搜索、八皇后、0-1 揹包問題、圖的着色、旅行商問題、數獨、全排列、正則表達式匹配等等。

回溯算法能解決的問題,基本用動態規劃也能解決,其時間複雜度更低,空間複雜度更高,用空間換時間。

參考資料