专栏首页一Li小麦Js算法与数据结构拾萃(6):回溯

Js算法与数据结构拾萃(6):回溯

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/八皇后问题

本文分享自微信公众号 - 一Li小麦(gh_c88159ec1309),作者:一li小麦

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Js算法与数据结构拾萃(6.5):回溯法解决数独问题

    回顾N皇后问题的解决方案,并没有采用二维数组。但实际上思路依然和所谓“回溯法通用解决模板”是一致的。

    一粒小麦
  • Js算法与数据结构拾萃(1)

    算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。

    一粒小麦
  • Js算法与数据结构拾萃(2)

    Given a string containing just the characters '(', ')', '{', '}', '[' and ']', d...

    一粒小麦
  • Js算法与数据结构拾萃(3):链表

    对于一个数组,想要做篡改是复杂度是非常高的,设想你接到一个需求,让你记录存储一个人的简历,你用数组储存,可能是这样的:

    一粒小麦
  • Js算法与数据结构拾萃(5):二分法

    也许你在《幸运52》看过这样的游戏,假设一台iPhone x 标价8300元,某人让你尽可能快地猜出它的价格。

    一粒小麦
  • Js算法与数据结构拾萃(4):二叉树

    因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转...

    一粒小麦
  • JS数据结构与算法-栈

    Ewall
  • JS数据结构与算法-队列

    Ewall
  • JS数据结构与算法-集合

    Ewall
  • JS数据结构与算法-链表

    一个链表的结构 现实中的举例说明就是火车。每节车厢是链表的元素,车厢间的连接就是指针:

    Ewall
  • js数据结构与算法--散列

    不扯淡了,还是来学技术吧。 散列,是一种常用的数据存储技术,优势在于可以快速的插入或取出,使用它的数据结构,叫散列表。 它的优势哈,插入、删除、取用数据都很快,...

    web前端教室
  • JS 算法与数据结构之栈

    列表是一种最自然的数据组织方式,如果数据存储的顺序不重要,且无需对数据进行查找,那么列表是一种再好不过的数据结构,但对于其它一些应用,列表就显得太过简陋,我们需...

    Leophen
  • JS 算法与数据结构之队列

    队列是一种先进先出(FIFO,First-in-first-out)的数据结构,其数据智能在队尾插入,在队首删除。

    Leophen
  • JS 算法与数据结构之列表

    列表是一组有序的数据,每个列表中的数据项称为元素 在 JS 中,列表的元素可以是任意数据类型,且列表保存多少元素没有事先限定 要设计列表的抽象数据类型,我们...

    Leophen
  • 前端学数据结构与算法(十三):01执行的艺术 - 回溯算法(上)

    在最初尝试学习算法时,对两个算法留下了深刻的印象,一个是动态规划,另一个就是回溯算法。如果说算法思想的艺术,那归于动态规划;但如果说用计算机执行机制解决问题的艺...

    飞跃疯人院
  • 前端学数据结构与算法(十四):01执行的艺术 - 回溯算法(下)

    书接上文,上个章节从递归到回溯的做了递进式介绍,相信已经对回溯有了初步的理解,接下来主要介绍更多与回溯相关的题目,从广度上加深对其理解。

    飞跃疯人院
  • JS面试之数据结构与算法 (5)

    JS面试之函数(1) JS面试之对象(2) JS面试之数组的几个不low操作(3) JS面试之http0.9~3.0对比分析(4)

    火狼1
  • 算法与数据结构

    七月半夏
  • 数据结构与算法

    树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历。

    不作声

扫码关注云+社区

领取腾讯云代金券