回溯演演算法是什麼

回溯演演算法是一種用於求解在某個搜尋空間中的問題的演演算法。它基本思想是從問題的某一種狀態開始不斷地嘗試各種可能的選擇，直到找到一種滿足問題要求的解或者發現這些選擇都無法滿足要求時，就回到上一個狀態，嘗試其他的選擇。

回溯演演算法通常採用遞迴的方法實現，它會不斷地遞迴呼叫自身，同時通過引數來模擬每一種選擇的結果，並在遞迴返回時復原這種選擇，繼續尋找其他可能的選擇。

回溯演演算法通常用於求解組合問題、排列問題、選擇問題等，例如求解 n 皇后問題、數獨問題等。在實際應用中，回溯演演算法往往需要通過一些優化方法來減少搜尋空間，以達到更高的效率和更快的求解速度。

回溯演演算法的應用場景有哪些

回溯演演算法的應用場景包括但不限於：

生成排列和組合問題，如全排列、組合問題等。
解決搜尋問題，如圖的遍歷、迷宮問題等。
解決約束條件滿足問題，如數獨、八皇后、數塔問題等。
解決最佳化問題，如揹包問題、旅行商問題等。
解決字串匹配問題，如正規表示式匹配、萬用字元匹配等。
解決人工智慧領域的問題，如遊戲博弈、機器學習等。
解決決策問題，如規劃和排程問題等。
解決網路流問題。

總之，回溯演演算法可以解決許多複雜的問題，在實際應用中具有廣泛的應用

回溯演演算法的優點和缺點是什麼

回溯演演算法的優點：

適用範圍廣：回溯演演算法可以解決很多問題，如搜尋、排列組合、八皇后、數獨等。
演演算法思路簡單：回溯演演算法的思路簡單，易於理解和實現。
可以找到所有解：回溯演演算法可以找到所有的解，不會漏掉任何一個解。

回溯演演算法的缺點：

時間複雜度高：回溯演演算法的時間複雜度很高，因為它需要遍歷所有的解空間，搜尋時間可能會很長。
空間複雜度高：回溯演演算法的空間複雜度也很高，因為它需要維護一個狀態樹，儲存所有的狀態和路徑。
可能會陷入死迴圈：如果回溯演演算法沒有正確地剪枝，可能會陷入死迴圈，導致程式無法結束。

回溯演演算法的時間複雜度和空間複雜度是多少？

回溯演演算法的時間複雜度和空間複雜度都與問題規模和決策樹的分支情況有關。

時間複雜度：在最壞情況下，回溯演演算法需要遍歷整個決策樹，即每個節點都需要存取一次，所以時間複雜度為O(b^d)，其中b是分支因子，d是決策樹的深度。因此，回溯演演算法的時間複雜度通常比較高，在面對大規模問題時可能需要較長時間。

空間複雜度：在回溯演演算法中，需要維護一個候選解的狀態，通常使用遞迴呼叫棧來實現。因此，空間複雜度也與決策樹的深度相關。在最壞情況下，決策樹的深度與問題規模成正比，因此空間複雜度為O(d)，其中d為決策樹的深度。如果在實現回溯演演算法時沒有使用遞迴，可以使用迴圈和棧來代替遞迴呼叫棧，這樣可以避免遞迴呼叫棧導致的空間限制，但是實現起來相對複雜。

回溯演演算法解決八皇后問題

八皇后問題是電腦科學中的經典問題，涉及將八個皇后放置在一個8x8的棋盤上，以使沒有兩個皇后相互威脅。這意味著不能將兩個皇后放在同一行、列或對角線上。

定義問題：八皇后問題涉及將八個皇后放置在一個8x8的棋盤上，以使沒有兩個皇后相互威脅。
建立棋盤：建立一個8x8的棋盤並將所有方格初始化為0。
放置皇后：從第一列開始，在第一行放置一個皇后。
檢查衝突：檢查皇后是否與棋盤上的任何其他皇后發生衝突。如果存在衝突，則將皇后移到同一列中的下一行。
重複步驟3和4：繼續在每一列中放置皇后並檢查衝突，直到所有皇后都放置在棋盤上。
回溯：如果在列中沒有有效的皇后位置，則回溯到上一列並將皇后移到該列的下一行。重複此過程，直到找到有效的解決方案。

function solveEightQueens(board, col): 
  if col >= 8: 
    return true 
 
  for row in range(0, 8): 
    if isSafe(board, row, col): 
      board[row][col] = 1 
      if solveEightQueens(board, col+1): 
        return true 
      board[row][col] = 0 
 
  return false 
 
function isSafe(board, row, col): 
  for i in range(0, col): 
    if board[row][i] == 1: 
      return false 
 
  for i, j in zip(range(row, -1, -1), range(col, -1, -1)): 
    if board[i][j] == 1: 
      return false 
 
  for i, j in zip(range(row, 8, 1), range(col, -1, -1)): 
    if board[i][j] == 1: 
      return false 
 
  return true 
 
// initialize board to all 0's 
board = [[0 for x in range(8)] for y in range(8)] 
 
// solve the problem 
solveEightQueens(board, 0)

回溯演演算法解決數獨問題

數獨是一個9x9的網格，被分成9個小的3x3的網格。目標是填充網格，使每行、每列和每個3x3網格都包含1到9的數位，且沒有重複。

從一個空的數獨網格開始。
在網格中找到一個空的單元格。
嘗試在該單元格中放置1到9的所有數位。
如果數位有效（即不違反任何數獨規則），則移動到下一個空的單元格並重復步驟3。
如果數位無效，則嘗試下一個數位。
如果所有數位都已嘗試且沒有一個有效，則回溯到上一個單元格並嘗試下一個數位。
重複步驟3到6，直到整個網格都被填滿。

function solveSudoku(grid):
  for i in range(9):
    for j in range(9):
      if grid[i][j] == 0:
        for k in range(1, 10):
          if isValid(grid, i, j, k):
            grid[i][j] = k
            if solveSudoku(grid):
              return True
            grid[i][j] = 0
        return False
  return True
 function isValid(grid, row, col, num):
  for i in range(9):
    if grid[row][i] == num:
      return False
    if grid[i][col] == num:
      return False
    if grid[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
      return False
  return True

solveSudoku函數接受一個9x9的網格作為輸入，並在數獨可解時返回True，否則返回False。它使用巢狀迴圈來迭代網格中的所有單元格。如果一個單元格為空（即其值為0），它使用另一個迴圈嘗試在該單元格中放置1到9的所有數位。如果數位有效（即不違反任何數獨規則），則移動到下一個空的單元格並重復該過程。如果數位無效，則嘗試下一個數位。如果所有數位都已嘗試且沒有一個有效，則回溯到上一個單元格並嘗試下一個數位。isValid函數通過檢查數位是否違反任何數獨規則（即是否已經存在於同一行、列或3x3網格中）來檢查數位是否有效。

回溯演演算法解決全排列問題

給定一個數位序列，要求輸出所有可能的排列組合。

定義一個遞迴函數，用於生成所有可能的排列組合。
在遞迴函數中，先判斷當前生成的排列是否已經包含了所有數位，如果是，則輸出當前排列並返回。
如果當前排列還沒有包含所有數位，就從剩餘的數位中選擇一個，加入當前排列中，並繼續遞迴生成下一個數位的排列。
在遞迴完成後，需要將加入的數位從當前排列中移除，以便繼續生成其他排列組合。

function backtrack(nums, path, res):
    if len(path) == len(nums):
        res.append(path)
        return
    for num in nums:
        if num not in path:
            path.append(num)
            backtrack(nums, path[:], res)
            path.pop()

backtrack函數接受三個引數：nums表示給定的數位序列，path表示當前生成的排列，res表示所有可能的排列組合。在函數中，首先判斷當前生成的排列是否已經包含了所有數位，如果是，則將當前排列加入結果集中並返回。如果當前排列還沒有包含所有數位，就從剩餘的數位中選擇一個，加入當前排列中，並繼續遞迴生成下一個數位的排列。在遞迴完成後，需要將加入的數位從當前排列中移除，以便繼續生成其他排列組合。

回溯演演算法解決組合問題

給定一個陣列和一個目標值，從陣列中選取元素使得它們的和等於目標值。

定義一個遞迴函數，用於生成所有可能的組合。
在遞迴函數中，先判斷當前組合的元素和是否等於目標值，如果是，則輸出當前組合並返回。
如果當前組合的元素和小於目標值，就從剩餘的元素中選擇一個，加入當前組合中，並繼續遞迴生成下一個元素的組合。
在遞迴完成後，需要將加入的元素從當前組合中移除，以便繼續生成其他組合。

function backtrack(nums, target, start, path, res):
    if sum(path) == target:
        res.append(path)
        return
    for i in range(start, len(nums)):
        if sum(path) + nums[i] > target:
            continue
        path.append(nums[i])
        backtrack(nums, target, i, path[:], res)
        path.pop()

backtrack函數接受五個引數：nums表示給定的陣列，target表示目標值，start表示當前開始選擇的位置，path表示當前生成的組合，res表示所有可能的組合。在函數中，首先判斷當前組合的元素和是否等於目標值，如果是，則將當前組合加入結果集中並返回。如果當前組合的元素和小於目標值，就從剩餘的元素中選擇一個，加入當前組合中，並繼續遞迴生成下一個元素的組合。在遞迴完成後，需要將加入的元素從當前組合中移除，以便繼續生成其他組合。

回溯演演算法解決單詞搜尋問題

在一個二維字元陣列中查詢給定單詞是否存在。

定義一個遞迴函數，用於生成所有可能的路徑。
在遞迴函數中，先判斷當前位置是否為單詞的最後一個字元，如果是，則返回True。
如果當前位置不是單詞的最後一個字元，則從當前位置向四周擴充套件，如果擴充套件的位置是合法的並且沒有走過，則將該位置加入當前路徑中，並繼續遞迴生成下一個位置的路徑。
在遞迴完成後，需要將加入的位置從當前路徑中移除，以便繼續生成其他路徑。
如果所有路徑都生成完畢，仍未找到單詞，則返回False。

function backtrack(board, word, row, col, path):
    if len(path) == len(word):
        return True
    if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[len(path)]:
        return False
    temp = board[row][col]
    board[row][col] = "#"
    res = backtrack(board, word, row + 1, col, path + [(row, col)]) or backtrack(board, word, row - 1, col, path + [(row, col)]) or backtrack(board, word, row, col + 1, path + [(row, col)]) or backtrack(board, word, row, col - 1, path + [(row, col)])
    board[row][col] = temp
    return res
 def exist(board, word):
    for i in range(len(board)):
        for j in range(len(board[0])):
            if backtrack(board, word, i, j, []):
                return True
    return False

backtrack函數接受四個引數：

board表示給定的二維字元陣列
word表示要查詢的單詞
row和col表示當前位置的行列座標
path表示當前生成的路徑。

在函數中，首先判斷當前位置是否為單詞的最後一個字元，如果是，則返回True。

如果當前位置不是單詞的最後一個字元，則從當前位置向四周擴充套件，如果擴充套件的位置是合法的並且沒有走過，則將該位置加入當前路徑中，並繼續遞迴生成下一個位置的路徑。

在遞迴完成後，需要將加入的位置從當前路徑中移除，以便繼續生成其他路徑。如果所有路徑都生成完畢，仍未找到單詞，則返回False。

exist函數接受兩個引數：

board表示給定的二維字元陣列
word表示要查詢的單詞。

在函數中，遍歷二維字元陣列中的每一個位置，如果從該位置開始可以找到單詞，則返回True。

如果遍歷完整個二維字元陣列，仍未找到單詞，則返回False。

【技術積累】演演算法中的回溯演演算法【一】