Js算法与数据结构拾萃（6）：回溯

一粒小麦

发布于 2020-02-25 10:17:47

1.1K0

发布于 2020-02-25 10:17:47

文章被收录于专栏：一Li小麦一Li小麦

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
}