【算法架構套路】回溯算法（暴力窮舉的藝術）

目錄

• 回溯算法介紹
• 架構套路
• 算法示例
  • 全組合
  • 全排列
  • 湊零錢
  • N皇後
  • 最長遞增子序列
  • 最長公共子序列
• 優化思路
  • 備忘錄避免重複計算
  • 向上傳回阻斷其他遞歸

回溯算法可以搜尋一個問題的所有解，本質是用遞歸代替N層for循環來“暴力窮舉”

原理如下：

1. 從根節點出發深度搜尋解空間樹
2. 搜尋到有解的分支時，繼續向下搜尋
3. 搜尋到無解的分支時，回退到上一步，顧名思義“回溯”

talk is cheap，show you the 套路，架構如下

結果集=[]
function dfs(選擇清單，已選擇的數組)
    if 結束條件
        結果集追加
        return
    for 選擇 in 選擇清單
        做選擇
        dfs(選擇清單, 已選擇數組) 進入下一次選擇
        取消選擇
dfs(選擇清單，[])
return 結果集
           

思路來自labuladong的算法小抄，自己改成了個人覺得更通用的版本，預設收集所有的解，便于跟蹤調試。

重點：

1. 選擇清單。目前可以做出的選擇
2. 已選擇路徑。已經做出的選擇
3. 結束條件。無法再做出選擇的條件

有了這架構，以後遇到需要窮舉的算法，把3個重點想通，直接套用，簡直不要太嗨~

以下算法全用python實作，需要注意的是python的數組預設是傳遞引用，引入了copy包來複制數組

全組合是窮舉的代表了吧，給定指定不重複的字元串，比如給定["a","b"]，傳回所有的組合結果應該是

aa

ab

ba

bb

我們來套用架構實作一下，代碼如下

import copy

# 全組合
def combination(str_list):
    res = []

    max_len = len(str_list)

    def dfs(str_list, track_list):
        if len(track_list) == max_len:  # 滿足條件，加入結果集
            res.append(track_list)
            return
        for c in str_list:
            track_list.append(c)  # 選擇
            dfs(str_list, copy.copy(track_list))  # 進入下一次選擇
            track_list.pop()  # 取消選擇

    dfs(str_list, [])
    return res
           

三個重點：

1. 選擇清單。可以選擇的字元串，比如['a','b','c']，對應變量str_list。
2. 已選擇路徑。已經做出的選擇，比如已經選擇了['a']，對應變量track_list。
3. 結束條件。無法再做出選擇的條件，已選擇的數組長度等于最大長度，對應

   len(track_list) == max_len

   。

我們來測試一下

for v in combination(['a', 'b']):
    print(v)
           

運作輸出

全排列和全組合差不多，唯一的差別是已經選擇過的字元串，不讓選擇了。

我們隻需要在全組合代碼的基礎上加上限制即可，代碼如下

import copy


# 全排列
def permute(str_list):
    res = []

    max_len = len(str_list)

    def dfs(str_list, track_list):

        if len(track_list) == max_len:  # 滿足條件，加入結果集
            res.append(track_list)
            return
        for c in str_list:
            if c in track_list:  # 已經存在的不再添加
                continue
            track_list.append(c)  # 選擇
            dfs(str_list, copy.copy(track_list))  # 進入下一次選擇
            track_list.pop()  # 取消選擇

    dfs(str_list, [])
    return res
           

我們隻是改了一下這裡

我們用chenqionghe的簡稱['c','q','h']來測試一下

for v in permute(['c', 'q', 'h']):
    print(v)
           

給定數量N種面值的硬币， 再給定一個金額，傳回硬币湊出這個金額的最少數量。

比如，給定硬币1, 2, 5，總額為10，最少需要2枚硬币5+5=10

代碼實作如下

def coin_change(coins, amount):
    res_list = []

    def dfs(n, track_list):
        if n == 0:
            res_list.append(track_list)  # 滿足條件
            return 0

        if n < 0:
            return -1

        for coin in coins:
            track_list.append(coin)  # 做選擇
            dfs(n - coin, copy.copy(track_list))  # 選擇一個硬币，目标金額就會減少，解變為1+sub
            track_list.pop()  # 取消選擇

    dfs(amount, [])
    return res_list
           

1. 選擇清單。可以選擇的硬币，對應coins數組。
2. 已選擇路徑。已經做出的選擇，對應track_list數組。
3. 結束條件。無法再做出選擇的條件，金額為0和負的時候。

需要注意的是：df函數代表的是：目标金額是n，需要dfs[n]個硬币，比如給定金額10，這次選擇了2，這次選擇能達到的金額數量是1+dfs(10 - 2)，也就是1+dfs(8)

我們來運作一下：

for v in coin_change([2, 3, 5], 10):
    print(v)
           

輸出如下

給出了所有的方案，如果要最小的硬币隻需要統計長度最小的即可。

最典型的是八皇後：

在8×8格的國際象棋上擺放8個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

以4皇後為例，給定數字4，應該給出兩種方案如下

第一種方案
. Q . .
. . . Q
Q . . .
. . Q .
第二種方案
. . Q .
Q . . .
. . . Q
. Q . .
           

套用架構實作如下

# N皇後問題
def solve_n_queens(n):
    res = []

    def dfs(board, row):
        if row == n:  # 到達最後一行，追加結果集
            res.append(board)
        for col in range(n):
            # 排除不合法的選擇
            if not is_valid(board, row, col, n):
                continue
            board[row][col] = 'Q'  # 選擇第row行第col列放Q

            dfs(copy.deepcopy(board), row + 1)

            board[row][col] = '.'  # 撤銷選擇
        return False

    board = [['.'] * n for _ in range(n)]  # 初始化二維數組
    dfs(board, 0)  # 從第0行開始做選擇
    return res

# 判斷是否能在board[row][col]放置Q
def is_valid(board, row, col, n):
    # 垂直方向是否有Q
    for v in range(row):
        if board[v][col] == 'Q':
            return False
    # 左上方是否有Q
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q':
            return False
        i = i - 1
        j = j - 1
    # 右上方是否有Q
    i, j = row - 1, col + 1
    while i >= 0 and j <= n - 1:
        if board[i][j] == 'Q':
            return False
        i = i - 1
        j = j + 1
    return True
           

N皇後的解法是，在每行做選擇，選擇為N列，做出選擇後，進入下一行繼續做選擇

1. 選擇清單。可以選擇的列，對應的是0-n的任意一列。
2. 已選擇路徑。已經做出的選擇，對應board二維數組。
3. 結束條件。無法再做出選擇的條件，也就是已經到達最後一行的時候。

注意：is_valid的函數，主要是判斷檢測目前位置是否能放“皇後”，也就是檢查垂直、左上方向和右上方是不是都沒有“皇後”

res = solve_n_queens(8)
for data in res:
    print('-' * 20)
    for v in data:
        print(" ".join(v))
           

運作輸出如下

給定一個未排序的整數數組，求這個數組的最長遞增子序列

例如

輸入: [10,9,2,5,3,7,101,18]

輸出: 4

解釋: 最長遞增子序列是 [2,3,7,101], 是以長度為 4.

下面用回溯架構實作一下，找出所有的遞增序列和最大的序列

import copy

def long_increasing_subsequence(arr):
    res_list = []
    n = len(arr)

    max_len = 1
    max_sub = []

    # 從第i個元素做選擇
    def dfs(i, track_list):
        # 到達末尾 或 下一個元素比track數組最後一個大
        if i == n or (len(track_list) > 0 and arr[i] < track_list[-1]):
            res_list.append(track_list)  # 滿足條件
            nonlocal max_len, max_sub
            if max_len < len(track_list):
                max_len = len(track_list)
                max_sub = track_list
            return
        for v in range(i, n):
            if len(track_list) > 0 and arr[v] < track_list[-1]:
                continue
            track_list.append(a[v])  # 做選擇
            if v < n:
                dfs(v + 1, copy.copy(track_list))  # 下一次選擇
            track_list.pop()  # 取消選擇

    dfs(0, [])
    return max_sub, res_list


a = [10, 9, 2, 5, 3, 7, 101, 18]
max_sub, res_list = long_increasing_subsequence(a)
print(max_sub)

           

給定兩個字元串 text1 和 text2，傳回這兩個字元串的最長 公共子序列 的長度。如果不存在 公共子序列 ，傳回 0 。

輸入：text1 = "abcde", text2 = "ace"

輸出：3

解釋：最長公共子序列是 "ace"，它的長度為 3。

下面用回溯架構實作一下，找出所有的公共子序列。

這次不太一樣，因為之前都隻有一個選擇數組，這次變成了兩個

import copy


def long_common_subsequence_all(str1, str2):
    len1, len2 = len(str1), len(str2)
    res_list = []

    def dp(i, j, track1, track2):
        if i == len1 or j == len2:
            # 到頭了，收集一下，相同的子序列
            res_list.append("".join(track1))
            return

        c_track1 = copy.copy(track1)
        c_track2 = copy.copy(track2)

        if str1[i] == str2[j]:
            # 找到一個lcs中的元素，str1和str2分别選中，繼續往下找
            c_track1.append(str1[i])
            c_track2.append(str2[j])
            dp(i + 1, j + 1, c_track1, c_track2)
            return
        else:
            dp(i, j + 1, c_track1, c_track2)
            dp(i + 1, j, c_track1, c_track2)

    dp(0, 0, [], [])

    lcs = ""
    for cs in res_list:
        if len(cs) > len(lcs):
            lcs = cs

    return lcs, res_list


s1 = "abcde"
s2 = "ace"
lcs, res_list = long_common_subsequence_all(s1, s2)
print(lcs)
           

以湊零錢為例，裡邊其實會出現很多相同子問題的遞歸

以10舉個例子，當我們選擇了選擇了[2, 3]和[5]的時候，都需要再計算dfs(5)的值。資料越大，重複的遞歸越多，性能越差。

我們可以引入一個map，記錄已經計算出的值，下次遇到相同問題直接傳回結果

def coin_change_optimization(coins, amount):
    memo = {}
    def dfs(n):
        if n in memo:
            return memo[n]
        if n == 0:
            return 0
        if n < 0:
            return -1

        min_res = float('INF')
        for coin in coins:
            sub = dfs(n - coin)  # 選擇一個硬币，目标金額就會減少，解變為1+sub
            if sub == -1:
                continue
            if min_res > 1 + sub:  # 更新最小值
                min_res = 1 + sub

        memo[n] = min_res if min_res != float('INF') else -1
        return memo[n]

    return dfs(amount)
           

以N皇後為例，我們隻需要在得到解的時候return，并在上層接收即可，代碼如下

# N皇後問題
def solve_n_queens(n):
    res = []

    def dfs(board, row):
        if row == n:  # 到達最後一行，追加結果集
            res.append(board)
            return True
        for col in range(n):
            # 排除不合法的選擇
            if not is_valid(board, row, col, n):
                continue
            board[row][col] = 'Q'  # 選擇第row行第col列放Q

            if dfs(copy.deepcopy(board), row + 1):
                return True

            board[row][col] = '.'  # 撤銷選擇
        return False

    board = [['.'] * n for _ in range(n)]  # 初始化二維數組
    dfs(board, 0)  # 從第0行開始做選擇
    return res
           

以上隻是在這裡做了改動

看到沒有，這就是回溯暴力窮舉的藝術，最簡單的架構，解決最難的問題~