美文网首页
回溯法讲解(结合图和案例)

回溯法讲解(结合图和案例)

作者: kimedison | 来源:发表于2019-10-13 17:40 被阅读0次

    一、简述

    回溯法,以穷举的形式,对问题有可能出现的解罗列出来,必要的时候会包含剪枝的操作。根据罗列的形式不一样,又有分为两种:

    • 子集树 回溯

    • 排列树 回溯

    二、步骤

    1. 根据题目,找到相应解空间,即解可能的组合
    2. 选择相应的解空间树(子集 or 排列),这一步最好画出来,便于理解分析
    3. 使用深度优先搜索(dfs)搜索树(必要的时候带上剪枝

    如上,因为第 3 步可以直接套用 三、解题模型,因此重要的一步便是 2,选择什么样的结构去解决题目,那么该如何确定选择哪种结构呢?如下分析:

    • 子集树:从给出集合中,找出满足某些条件的子集。
      如: 01 背包问题,就是从物品集合中,找出最大重量的子组合、

    • 排列树:将集合中的元素,给出按照某些条件进行排列的子集
      如:排列数字,就是将集合({1, 2, 3})进行排序,给出所有可能的排序。

    三、解题模型

    由于树的搜索(这里是 dfs)可以选用或者递归的方式,因此也有两种模型

    1. 栈

    pass,持续更新后补

    2. 递归(常用)

    使用递归的方式进行通解,通常要定义如下参数:

    • int k - 当前层
    • int n - 总层数 (如果总层数使用解的个数,则无需定义)
    • vector<T>& x - 解
    • vector<T>& res - 记录的结果

    以及剪枝函数(有时候也叫限界函数):

    • constraint(k) 即判断是否有必要进行下一次的hui's

    2.1 子集树

    void backtrack(int k, vector<T>& x, vector<T>& res) {
    
      if (k >= x.size()) {
          // 此处做记录
          res.push_back(x);
      } else {
          // 继续深入
          for (int i=0; i<=1; i++) {
              x[t] = i; // 选 0 或者 1
    
              if (constraint(k)) {
                   backtrack(k+1, x, res);
              }
          }
      }
    
    }
    

    2.2 排列树

    void backtrack(int k, vector<T>& x, vector<T>& res) {
    
      if (k >= x.size()) {
          // 此处做记录
          res.push_back(x);
      } else {
          // 继续深入
          for (int i=k; i<=x.size(); i++) {
              
              swap(x[t], x[i]);
              if (constraint(k)) {
                   backtrack(k+1, x, res);
                   swap(x[t], x[i]);
              }
          }
      }
    
    }
    

    排列树主要是通过 swap(a: T, b: T) 方法对元素交叉排列,在结束之后再交换回来(恢复状态)。

    四、案例

    TODO 持续更新

    相关文章

      网友评论

          本文标题:回溯法讲解(结合图和案例)

          本文链接:https://www.haomeiwen.com/subject/vpqkmctx.html