39 | 回溯算法：从电影《蝴蝶效应》中学习回溯算法的核心思想

精选留言(101)

• 

  纯洁的憎恶

  回溯算法本质上就是枚举，优点在于其类似于摸着石头过河的查找策略，且可以通过剪枝少走冤枉路。它可能适合应用于缺乏规律，或我们还不了解其规律的搜索场景中。

  作者回复: 👍

  2018-12-24

   1

   104
• 

  slvher

  0-1 背包问题的回溯实现技巧：
  
  第 11 行的递归调用表示不选择当前物品，直接考虑下一个（第 i+1 个），故 cw 不更新
  
  第 13 行的递归调用表示选择了当前物品，故考虑下一个时，cw 通过入参更新为 cw + items[i]
  
  函数入口处的 if 分支表明递归结束条件，并保证 maxW 跟踪所有选择中的最大值

  2018-12-24

   2

   67
• 

  G.S.K

  0-1背包问题根据老师下边这句话的讲解，代码再加两行注释就非常容易理解了
  
  我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
  
  public int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
  // cw 表示当前已经装进去的物品的重量和；i 表示考察到哪个物品了；
  // w 背包重量；items 表示每个物品的重量；n 表示物品个数
  // 假设背包可承受重量 100，物品个数 10，物品重量存储在数组 a 中，那可以这样调用函数：
  // f(0, 0, a, 10, 100)
  public void f(int i, int cw, int[] items, int n, int w) {
    if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
      if (cw > maxW) maxW = cw;
      return;
    }
    f(i+1, cw, items, n, w); //当前物品不装进背包
    if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
      f(i+1,cw + items[i], items, n, w); //当前物品装进背包
    }
  }
  

  2019-03-03

  

   32
• 

  纯洁的憎恶

  0-1背包的递归代码里第11行非常巧妙，它借助回溯过程，实现了以每一个可能的物品，作为第一个装入背包的，以尝试所有物品组合。但如果仅按从前向后执行的顺序看，是不太容易发现这一点的。

  2018-12-24

   1

   23
• 

  www.xnsms.com小鸟接码

  看不懂背包问题代码同学，请好好仔细看看下面这句话，再结合代码你就看懂了
  
  我们可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。

  作者回复: 👍

  2019-01-06

   2

   22
• 

  Shawn

  0-1背包问题理解：
  假设三个物品，每个物品在考虑时有两种选择，1-放进包，0-不放
  11行代码表示不放进包里。13行代码表示放进包里。
  三个物品遍历过程如下：
  0 0 0 update maxW
  0 0 1 update maxW
  0 1 0 update maxW
  0 1 1 update maxW
  1 0 0 update maxW
  1 0 1 update maxW
  1 1 0 update maxW
  1 1 1 update maxW

  作者回复: 👍

  2019-05-30

  

   18
• 

  传说中的成大大

  今天又读了一遍这个文章,又写一遍八皇后,写的更快，更流畅,背包和正则匹配的代码也理解得更透彻了

  2018-12-27

   1

   11
• 

  siegfried

  回溯就是暴力枚举的解法吧？遍历所有情况，当满足情况就停止遍历（剪枝）。

  作者回复: 是的

  2018-12-24

  

   11
• 

  Monday

  8皇后以前提到就觉得难懂，今天硬着头皮去写，竟虽然难还是写出来了。多写多写多写

  2018-12-25

  

   8
• 

  猫头鹰爱拿铁

  总觉得背包问题11行代码应该写在14行后，那个if条件后面。

  2018-12-28

  

   7
• 

  叶明

  老师，你好，背包问题，貌似只记录了可以放进去的最大值，没有记录放进最大值对应的放法，我稍微
  改了下，算出了最大值对应的所有放法，不知道可行不，希望老师回复下。
  private int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
      // 下标表示物品序号，值表示是否放进背包:1放，0不放
      private int[] currentAnswer;
      //存储所有解(map key表示放进去的重量，value表示对应重量的物品放法)，
      //最终所有最优解为bestAnswerMap.get(maxW)
      private Map<Integer, List<int[]>> bestAnswerMap = new HashMap();
  
      // cw 表示当前已经装进去的物品的重量和；i 表示考察到哪个物品了；
      // w 背包重量；items 表示每个物品的重量；n 表示物品个数
      // 假设背包可承受重量 100，物品个数 10，物品重量存储在数组 a 中，那可以这样调用函数：
      // f(0, 0, a, 10, 100)
      public void f(int i, int cw, int[] items, int n, int w) {
          if(currentAnswer == null){
              currentAnswer = new int[n];
          }
  
          if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
              if (cw >= maxW) {
                  maxW = cw;
                  int[] bestAnswer = new int[currentAnswer.length];
                  for(int j=0; j<currentAnswer.length; j++){
                      bestAnswer[j] = currentAnswer[j];
                  }
                  if(bestAnswerMap.containsKey(cw)){
                      bestAnswerMap.get(cw).add(bestAnswer);
                  }else{
                      List<int[]> list = new ArrayList<int[]>();
                      list.add(bestAnswer);
                      bestAnswerMap.put(cw, list);
                  }
              }
              return;
          }
          currentAnswer[i] = 0;
          f(i+1, cw, items, n, w);
          if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
              currentAnswer[i] = 1;
              f(i+1,cw + items[i], items, n, w);
          }
      }
  
  最终maxW 对应的所有最优解为bestAnswerMap.get(maxW)

  2019-01-30

   1

   6
• 

  AllenGFLiu

  8皇后的Python代码是按照争哥的JAVA代码翻译的，写完之后并没有深刻的理解“回溯”这个动作发生在哪里，后来在微信公众小灰上又看了一遍图解，决定debug跑一下。
  借助着VSCode显示出来的递归栈终于明白了“回溯”是怎么执行的。
  简单来说，当前几个循环皇后按照要求站好位之后，已经产生了对应数量的递归栈，此时一致是递归中的递，当走到当前循环时检查发现 一行中8个位置检查isOK都是false时，栈顶的cal8queens这个函数就结束了，这个时候就该递归中的归了，所以就回到上一行，为该行的皇后换另外一个符合条件的位置，这就是所谓的枚举搜索啊。
  我太高兴了，哈哈。

  2019-08-27

  

   5
• 

  Joker

  老师，我经过查资料，找到，其实判断是否在一条斜线上还有更加简便的做法，就是如果行互减的绝对值等于列互减的绝对值，那么就是在一条斜线上的。
  if (Math.abs(row - i) == Math.abs(column - result[i])) {
                  return false;
              }

  作者回复: 是的，我写的时候也查过资料。

  2019-02-01

   4

   4
• 

  传说中的成大大

  我今天也把8皇后写出来了 虽然是第一次

  作者回复: 写多了你就会发现 这玩意贼简单

  2018-12-25

  

   4
• 

  peng

  八皇后我一开始一直没想明白一个问题，就是每当print一种结果之后，并没有重置result数组，那再穷举下一种结果时，result中的脏数据会影响到isOK()函数的判断吗？
  经过一番调试思考后，发现我的担心多余了。每次穷举下一种结果时，都会在上一种结果的基础上进行穷举，所以result中<row之前的结果都是有用的，不是脏数据, 也不应该清掉它。
  而isOK()每次都寻找正上，左上，右上的占用结果进行判断，因此result中>=row的结果也不会影响到isOK()的判断，很快就可能被后续的穷举重新设置，遂而形成新的穷举结果。
  有这些疑问只能说明我对递归回溯理解得还不到位，只能通过一步步调试来寻找答案

  2019-08-03

  

   3
• 

  Geek_bd613f

  看完这篇文章，写了个求n位逐位整除数的题，发现剪枝技巧其实在考虑题目限制条件时自然就用上了，比如背包问题会判断weigh＜背包最大载重，如果不判断，递归到最后就不能直接取maxW了，因为这个值可能超过背包最大载重。

  2019-06-19

  

   3
• 

  饺子

  流程大概就是：
  第一个不放，第二个不放，……，第n-1个不放，第n个不放。
  第一个不放，第二个不放，……，第n-1个不放，
  第n个放。
  第一个不放，第二个不放， ……，第n-1个放，
  第n个不放。
  第一个不放，第二个不放， ……，第n-1个放，
  第n个放。
  ……
  以此类推
  感觉这些问题就是将概率论知识转化成代码实现。
  

  2019-02-23

  

   3
• 

  Kudo

  0-1背包python实现：
  maxW = -1 # tracking the max weight
  
  def backpack(i, cw, items, w):
      '''
      # i: the ith item, integer
      # cw: current weight, integer
      # items: python list of item weights
      # w: upper limit weight the backpack can load
      '''
      global maxW
      
      if cw==w or i==len(items): # base case
          if cw > maxW:
              maxW = cw
          return
      
      # There are 2 states, traverse both!!!
      backpack(i+1, cw, items, w) # do not choose
      if (cw + items[i] <= w):
          backpack(i+1, cw+items[i], items, w) # choose
      
  # how to use
  items = [2, 2, 4, 6, 3]
  backpack(0, 0, items, 10)
  print(maxW)

  2018-12-27

  

   3
• 

  森码

  今天正好发现一个算法的示例，大家结合看看，应该能更好的理解https://algorithm-visualizer.org/backtracking/n-queens-problem

  2018-12-27

  

   3
• 

  一个工匠

  难道只有我把回溯理解成多叉树的“后序排序”？
  之所以会回溯，是因为在一个结点，有多个选择，每个选择就是一叉，那多个选择就是多叉。选择一叉后，下一个结点又有多叉。这就是一个多叉树嘛。
  return，就是叶子结点。
  当return的时候，叶子结点访问完了，就要出栈了。依据“后序排序”的规则，开始回到上一个结点的下一叉进行入栈，然后又return了，又出栈了。
  最后，把所有可能性全部遍历了一遍，game over了。

  2019-09-10

   1

   2