Js算法與數據結構拾萃（6）：回溯

2020 年 2 月 25 日
筆記

Js算法與數據結構拾萃（6）：回溯

導言

說起回溯法，筆者就想起曾經有過這麼一件事：

筆者之前公司招了個初級前端小F，馬上就讓他上項目，接着遇到這麼一個問題

後端返回層級結構：

問：如何根據id找到需要的數據，並輸出它的層次路徑?

然後他寫了一個星期沒寫出來。於是混完一個月之後，交接不辦，直接跑路了。

至今同事圈還把他作為笑談。

回溯法（backtracking）是暴力搜索法中的一種。

對於某些計算問題而言，回溯法是一種可以找出所有（或一部分）解的一般性算法，尤其適用於約束滿足問題（在解決約束滿足問題時，我們逐步構造更多的候選解，並且在確定某一部分候選解不可能補全成正確解之後放棄繼續搜索這個部分候選解本身及其可以拓展出的子候選解，轉而測試其他的部分候選解）。

回溯法採用試錯的思想，它嘗試分步的去解決一個問題。在分步解決問題的過程中，當它通過嘗試發現現有的分步答案不能得到有效的正確的解答的時候，它將取消上一步甚至是上幾步的計算，再通過其它的可能的分步解答再次嘗試尋找問題的答案。回溯法通常用遞歸來實現，在反覆重複上述的步驟後可能出現兩種情況：

•找到一個可能存在的正確的答案•在嘗試了所有可能的分步方法後宣告該問題沒有答案

樹形結構遍歷

回到引言的案例，初級前端小F 面臨的是這樣一個結構：

這棵樹不妨稱之為決策樹，在每個節點你都要做決策。我們根據決策的邏輯，在這個樹上遊走。

因此查找的思路是：

1.定義一個空數組（棧）存放層級路徑（path）2.一個while循環：如果 當前節點無目標節點，path出棧，遍歷下一個，3.查找一個節點時，在path中push這個節點，判斷當前節點的name是否為想要的id，•是則返回該節點和path為最終結果，•不是則查找它的children=>如果沒有children，•如果沒有children判定為當前節點無目標節點，回到第二步邏輯

八皇后問題

在經典的教科書中，八皇后問題[1]展示了回溯法的用例。

國際象棋中，皇后橫、直、斜都可以走，步數不受限制，但是，不能越子行棋。該棋也是棋力最強的棋子。

1848年，國際象棋手馬克斯·貝瑟爾提出一個問題，如何能夠在8×8的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？

數學大佬高斯窮盡一生都沒有數清楚八皇后問題到底有幾種可能的放置方法，直到計算機的出現。

該題仍然可以用回溯法來解：決策樹的每一層row表示棋盤上的每一行；每個節點可以做出的選擇是，在該行的任意一列（col）放置一個皇后。

1.入參獲取一個二維數組作為棋盤board，row為當前行，定義返回值res2.當row遍歷完了之後，作為決策的終止條件。返回res。3.遍歷這個棋盤當前行的每列（col），判斷點位是否合法：•不合法：跳過此循環•合法:•落子。board[row][col]=true•把當前棋盤的局勢和row+1作為入參，進行下一行決策•撤銷選擇 board[row][col]=false

至於合不合「法」，可以寫一個獨立的方法來判斷：上邊，右上方，左上方是否有皇后。——下方都不需要判斷。因為沒落子。

解題思路

好了，現在可以小結一下了。回溯算法可以有這麼一個套路：

result = []  function backtrack(路徑, 選擇列表){      if 滿足結束條件:          result.add(路徑)          return result        for 選擇 in 選擇列表:          做選擇          backtrack(路徑, 選擇列表)          撤銷選擇  }

當然很多時候需要具體情況具體分析。

在最壞的情況下，回溯法的算法時間複雜度略大於O( N! ) ，空間複雜度為O( N! )，因為窮舉整棵決策樹是無法避免的。這也是回溯算法的一個特點，不像動態規劃存在重疊子問題可以優化，回溯算法複雜度一般都很高。

案例1：Permutations（全排列）

對應leetcode 46題，難度中等 https://leetcode.com/problems/permutations/

Given a collection of distinct integers, return all possible permutations.

給定一個沒有重複數字的序列，返回其所有可能的全排列。

Example:

Input: ['吃',『飯』,『沒』]  Output:  [    ['吃',『飯』,『沒』],    ['吃',『沒』,『飯』],    ['飯',『沒』,『吃』],    ['飯',『吃』,『沒』]    ['沒',『吃』,『飯』],    ['沒',『飯』,『吃』],  ]

解析

這裡的所謂所謂全排列，就是計算Ann，也就是n!是回溯算法的基本問題。

我們知道 n 個不重複的數，全排列共有 n! 個。以前是高中數學內容，但現在小學生都知道怎麼列舉了。

這張圖就是這道題的決策樹。現在要教會計算機如何像小學生一樣思考。

解決問題的流程（backtack）應該是：

1.定義空數組tmp作為約束條件，list作為返回值。2.遍歷這個樹，•如果滿足約束條件tmp，•push到tmp中•執行temp下的查找•tmp出棧（回溯）•不滿足則，跳過此循環遞歸終止條件：tmp長度和nums一致，此時已經可遍歷。

題解

function backtrack(list, temp, nums) {    // 終止條件    if (temp.length == nums.length) {      return list.push([...temp])    }      for (let i = 0; i < nums.length; i++) {      if (temp.includes(nums[i])) continue      temp.push(nums[i])      backtrack(list, temp, nums)      temp.pop()    }  }    var permute = function(nums) {    let list = []    backtrack(list, [], nums)    return list  }

案例2：N皇后問題

對應leetcode 第51題；難度：困難 https://leetcode.com/problems/n-queens/

給你一個 N×N 的棋盤，讓你放置 N 個皇后，使得它們不能互相攻擊。

題解

每一種解法包含一個明確的N皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

根據很自然地想到，定義一個二維數組去操作這些數據。但是返回值是一維度數組，轉為非引用對象操作起來異常高昂。所以考慮用遞歸遍歷掃描每一行，然後用圖存放盤面。比如[2,4,1]表示：第0行第2列，第1行第4列，第2行第1列，放了皇后。

接下來就是盤面判斷，當每一行遍歷的時候，我們發現

•行不能一樣•列不能一樣•行+列不能一樣•行-列不能一樣

var solveNQueens = function(n) {    let ret = []      // 從第0行開始遍歷    find(0)      // tmp是盤面形勢，它的索引是行數據    // 值是列數據：也就是擺放的棋子    // 比如說[2,4,1]=>表示棋盤第2行第1列，棋盤第4行第2列，棋盤第1行第3列，放了棋子    function find (row, tmp = []) {      // 終止條件      if (row == n) {        // n-1已經是最後一行，tmp就是所有路徑的結果        ret.push(          tmp.map(c => {            // c是擺放的棋子            let arr = new Array(n).fill('.')            arr[c] = 'Q'            return arr.join('')          })        )      }        // 1. 如何查找？遍歷每列      for (let col = 0; col < n; col++) {        let canSet = tmp.some((colIndex, rowIndex) => {          // colIndex和rowIndex是之前擺放的棋子的行列索引          // col和row是當前所在位置的索引            /**           * 判斷條件：           * 1.行不能一樣           * 2.列不能一樣           * 3.行+列 不能一樣           * 4.行-列不能一樣           */          return (            colIndex == col ||            rowIndex - colIndex == row - col ||            rowIndex + colIndex == row + col          )        })        if (canSet) {          continue        }          // 如果能放，直接下一行        find(row + 1, [...tmp, col])      }    }      return ret  }

事實證明，用圖來處理效率相當優秀：

案例3：word search(單詞搜索)

對應leetcode 79題，難度中等 https://leetcode.com/problems/word-search/

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

給定一個二維網格和一個單詞，找出該單詞是否存在於網格中。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中「相鄰」單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

Example:

board =  [    ['A','B','C','E'],    ['S','F','C','S'],    ['A','D','E','E']  ]    Given word = "ABCCED", return true.  Given word = "SEE", return true.  Given word = "ABCB", return false.

題解

中間過程可以簡化為索引值(cur)

請遵循以下的思路：

•怎麼找（雙循環）

var exist = function(board, word) {    if (board.length == 0) {      return false    }    if (word.length == 0) {      return true    }      const row = board.length    const col = board[0].length      // 1. 怎麼找    for (let i = 0; i < row; i++) {      for (let j = 0; j < col; j++) {        const ret = find(i, j, 0, row, col, board, word)        if (ret) {          return true        }      }    }    return false  }

•何時終止（find）

// 判斷終止條件  function find(i, j, cur, row, col, board, word) {    // 越界    if (i >= row || i < 0) return false    if (j >= col || j < 0) return false      // 找到當前字母    const letter = board[i][j]    // 字母不匹配    if (letter !== word[cur]) return false    // 找到最後一個，而且相等    if (cur == word.length - 1) return true        // 進行下一步判斷（上下左右）  }

•如何儲存中間過程，執行下一步?

// 判斷終止條件  function find(i, j, cur, row, col, board, word) {    // 。。。      // 不允許使用已經使用的字母:當前路徑標記為null    // 回溯時，再標記回來    board[i][j] = null      // 上下左右    const ret =      find(i + 1, j, cur + 1, row, col, board, word) ||      find(i - 1, j, cur + 1, row, col, board, word) ||      find(i, j + 1, cur + 1, row, col, board, word) ||      find(i, j - 1, cur + 1, row, col, board, word)      // 把剛標記為null的撤銷。    board[i][j] = letter    return ret  }

References

[1] 八皇后問題: https://w.upupming.site/wiki/八皇后問題