详解回溯法

详解回溯法

references:

回溯算法

回溯算法

详细讲解回溯算法（一）

回溯法-素数环问题

素数环（java实现）

回溯算法详解

算法入门6：回溯法

【算法】用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle)

概念

回溯（backtracking）法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.

适用条件

1. 问题的解用向量表示

X = (x1, x2, ..., xn)

2. 需要搜索一个或一组解
3. 满足约束条件的最优解

回溯法中，首先需要明确下面三个概念：

• 约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
• 状态空间树：一个问题的解可以表示成解向量X = (x1, x2, ..., xn)，X中每个分量xi所有取值的组合构成问题的解向量空间，简称解空间或者解空间树，又称为状态空间树，是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
• 扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
• 由于采用回溯法求解时存在退回到祖先结点的过程，所以需要保存搜索过的结点。通常采用：
  • 定义栈来保存
  • 采用递归方法
• 用回溯法通常采用两种策略（均称为剪枝函数）避免无效搜索。
  • 用约束函数在扩展结点处剪除不满足约束条件的路径
  • 用限界函数剪去得不到问题的解或最优解的路径

解题步骤

(1)描述解的形式，定义一个解空间，它包含问题的所有解，这一步主要明确问题的解空间树。

(2)确定结点的扩展搜索规则。

(3)构造约束函数（用于杀死节点）。然后就要通过DFS思想完成回溯，DFS可以采用递归回溯或者非递归（迭代）回溯。

确定问题的解空间 –> 确定结点的扩展搜索规则–> 以DFS方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

通用代码

// 递归版 const backtrack= (t)=>{ 
    if (t>n) console.info(x); //叶子节点，输出结果，x是可行解  else{ 
    // //当前节点的所有子节点  for (let i=0;i<k;i++){ 
    x[t]=value(i); //每个子节点的值赋值给x  //满足约束条件和限界条件  if (constraint(t)&&bound(t)) backtrack(t+1); //递归下一层  } } } 

//针对N叉树的迭代回溯方法  const iterativeBacktrack=()=>{ 
    let t=1; while (t>0) { 
    if(ExistSubNode(t)) //当前节点的存在子节点  { 
    for(let i=0;i<k;i++){ 
    x[t]=value(i);//每个子节点的值赋值给x  if (constraint(t)&&bound(t))//满足约束条件和限界条件  { 
    //solution表示在节点t处得到了一个解  if (solution(t)){ 
    console.info(x);//得到问题的一个可行解，输出  }else{ 
    t++;//没有得到解，继续向下搜索  } } } } else //不存在子节点，返回上一层  { 
    t--; } } } 

子集树和排列树

子集树

所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。如素数环问题，背包问题

// 算法范式 const backtrack=t=>{ 
    if (t>n) console.info(x); else{ 
    for (let i=0;i<=k;i++) { 
    // k的大小取决于子集树的分支多少，比如素数环可以取1-n， k=n 而背包问题是0-1 k=1 x[t]=i; if (constraint(t)){ 
    // 满足约束条件 backtrack(t+1); // 下面代码进行回溯 // 一般是恢复到原值即可 } } } } 

排列树

// 算法范式 const backtrack=t=>{ 
    if (t>n) console.info(x); else{ 
    for (let i=t;i<=n;i++) { 
    swap(x[t], x[i]); if (constraint(t)&&bound(t)) backtrack(t+1); swap(x[t], x[i]); } } } 

回溯法和DFS的区别

• 访问次序不同：深度优先遍历的目的是“遍历”，本质是无序的，重要的是是否被访问过，因此在实现上只需要对于每个位置是否被访问就足够了。回溯法的目的是“求解过程”，本质是有序的，也就是说必须每一步都是要求的次序。
• 访问次数不同：深度优先遍历对已经访问过的顶点不再访问。回溯法中已经访问过的顶点可能再次访问。
• 剪枝不同：深度优先遍历不含剪枝。

实际上，除了剪枝是回溯法的一个明显特征外（并非任何回溯法都包含剪枝部分），很难严格区分回溯法 与深度优先遍历。因为这些算法很多是递归算法，在递归调用中隐含着状态的自动回退和恢复。

常见题型

素数环

• Q1:解空间是什么？
  • 应该是一个长度为n的数组，数组可能为多个。
• Q2:扩展搜索原则是什么？
  • 每一个位置的值都可以是1-n中间的数
• Q3:约束函数是什么？
  • check0检查当前加进来的值是否和索引前有重复？是否和前一位的和为素数？若为最后一位是否和第一位的和为素数？

迭代

 / * 问题描述：输入正整数n，把整数1，2，3，…n组成一个环，使得相邻两个整数之和均为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。N<=16。 输入样例：6 输出样例： 1 4 3 2 5 6 1 6 5 2 3 4 素数就是质数，因数只有1和它自己。 */ / * 判断一个数是不是素数，只需要折半判断即可 * @param num * @returns {boolean} */ const testPrime=num=>{ 
    let mid=Math.floor(Math.sqrt(num)); for(let i=2;i<=mid;i++){ 
    if(num%i===0){ 
    return false; } } return true; }; / * 判断当前加进去的数字是否满足条件 * 1. 是否与之前重复 * 2. 相邻之和是否为素数 * 3. 第一个和最后一个相加是否为素数 * @param a * @param k * @param n * @returns {boolean} */ const check=(a,k,n)=>{ 
    let flag = false ; for (let i =0;i<k;i++) //检查是否重复 if (a[i] === a[k]) return false; flag = testPrime(a[k]+a[k-1]); //检验与相邻之和是否是素数 if (flag ===1&&k ===n-1) //如果是最后一个，需要检查与开始值得和 flag = testPrime(a[k]+a[0]); return flag; }; / * 1：如果填入一个数是成立的，我们就继续填写下一个位置，如果这个数不成立，我们就换下一个数填写，相当于我们剪掉了这个数的树枝，去寻找下一个； * 2：填写最后一个数时，应该考虑其应该和第一个数之和是素数； * 使用迭代法实现:虽然代码比较多，但是思路还是比较清晰的，回溯的位置也很清晰 * @param n */ const primeRing=n=>{ 
    if(n===1) return [1]; let res=[]; // initialize arr let arr=new Array(n).fill(0); let k=1; arr[0]=1; while(k>=1) { 
    arr[k]=arr[k]+1; while(arr[k]<n){ 
    if(check(arr,k,n)){ 
    break; }else{ 
    // 否则进行叠加 arr[k]=arr[k]+1; } } if(arr[k]<=n&&k===n-1){ 
    console.info(arr); let temp=JSON.parse(JSON.stringify(arr)); res.push(temp); } if(arr[k]<=n&&k<n-1&&check(arr,k,n)){ 
    k+=1; }else{ 
    arr[k--]=0;//剪枝回溯 } } return res; }; 

递归

 / * 回溯法通常使用递归来实现， * vis用来保存每一个1-n的元素是否在一个解向量中用过 */ const primeRing1=n=>{ 
    let arr=[],vis=[],res0=[]; arr[0] = 1; vis[0]=true; for(let i = 1; i <n;i++){ 
    vis[i] = false; } / * check0的难点在于检测的永远是idx指针前面的数是否和k重复以及k和idx-1所在位置的数的和是否为素数 * 这也是能够回溯的关键 */ const check0=(arr,k,idx)=>{ 
    let flag; for(let i=0;i<idx;i++){ 
    if(arr[i]===k) return false; } flag=testPrime(arr[idx-1]+k); return flag; }; / * vis[i-1] = false;是不满足条件回溯的过程 * @param cur */ const dfs=cur=>{ 
    if(cur >= n&&testPrime(arr[n]+arr[0])){ 
    let temp=JSON.parse(JSON.stringify(arr)); res0.push(temp); // console.info(arr); // console.info(res0); }else{ 
    for(let i = 1; i <= n; i++){ 
    // //尝试放置每个数i 使用这个代码或者下面的判断语句 // if(!vis[i-1] && testPrime(i+arr[cur-1])){//如果这个数没有被使用，并且与前一个数的和是质数 // vis[i-1] = true;//标明这个数被使用 // arr[cur] = i;//将这个数加入队列 // // console.info(arr); // dfs(cur+1);//求下一个数 // vis[i-1] = false;//取消这个数 // } // if(check0(arr,i,cur)){ 
   //如果这个数没有被使用，并且与前一个数的和是质数 arr[cur] = i;//将这个数加入队列 dfs(cur+1);//求下一个数 } } } }; dfs(1); return res0; }; 

// 用子集树的思路 const primeRing=n=>{ 
    let res=new Array(n).fill(0); res[0]=1; const testPrime=num=>{ 
    let temp=Math.sqrt(num); for(let i=2;i<=temp;i++){ 
    if(num%i===0){ 
    return false; } } return true; }; const check=(arr,idx,val)=>{ 
    let flag; // 不用forEach 避免无法跳出循环出现错误 for(let i=0;i<idx;i++){ 
    if(arr[i]===val){ 
    return false; } } flag=testPrime(arr[idx-1]+val); if(idx===n-1){ 
    flag=flag&&testPrime(arr[0],val); } return flag; }; const dfs=k=>{ 
    if(k>n-1){ 
    console.info(res); }else{ 
    for(let i=1;i<=n;i++){ 
    if(check(res,k,i)){ 
    res[k]=i; dfs(k+1); // 此处不必另外加回溯语句是因为每次遍历都给res[k]重新赋值了而不必再更改赋初始值 默认进入回溯状态 //res[k]=0; } } } }; dfs(1); }; 

背包问题

问题：给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

 const knapsack=(tWeight,n,obj)=>{ 
    let curWeight=0,curVal=0,maxVal=0,compose=new Array(n).fill(0) ,max=[]; let w=Object.keys(obj),v=[]; w.forEach(item=>{ 
    v.push(obj[item]); }); console.info(w,v); const dfs=t=>{ 
    if(t>n-1&&curWeight<=tWeight){ 
    console.info('==>',compose,curVal); // 控制输出条件 if(curVal>maxVal){ 
    maxVal=curVal; max=JSON.parse(JSON.stringify(compose)); } }else{ 
    for(let i=0;i<=1;i++){ 
    if(i===0){ 
    // 不放入背包 dfs(t+1); }else{ 
    // 放入背包 if(curWeight+Number(w[t])<=tWeight){ 
    curWeight+=Number(w[t]); curVal+=v[t]; compose[t]=w[t]; dfs(t+1); // 回溯 compose[t]=0; curWeight-=Number(w[t]); curVal-=v[t]; } } } } }; dfs(0); console.info('result==>',max,maxVal); return maxVal; }; 

N皇后问题

 / * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 * 显然从测试用例上看符合问题的解用向量表示，需要搜索一组解的情况,因此满足用回溯法解题的要求 * 解空间自然就是子集树 * 扩展规则是n个皇后可以放在任意位置 * 约束条件是：该位置无皇后，行方向没有，列方向没有，斜方向也没有皇后 * 但是时间复杂度过高，无法AC * 修改回溯法之后：用k参数代表所在行， * 时间复杂度：\mathcal{O}(N!)O(N!). 放置第 1 个皇后有 N 种可能的方法，放置两个皇后的方法不超过 N (N - 2) ，放置 3 个皇后的方法不超过 N(N - 2)(N - 4) ，以此类推。总体上，时间复杂度为 \mathcal{O}(N!)O(N!) . * 空间复杂度：\mathcal{O}(N)O(N) . 需要保存对角线和行的信息。 作者：LeetCode 链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 * @param n */ const solveNQueens =n=>{ let res=new Array(n),res0=[]; for(let i=0;i 
  
    { // todo 位置不合理，已经限制过，不再处理 // todo 已经有皇后了 if(res0[i][j]==='Q'){ return false; } // todo 横向纵向有皇后 for(let k=0;k 
   
     =0&&t>=0){ if(res0[s][t]==='Q'){ return false; }else{ s--; t--; } } // 右上角 s=i;t=j; while(s 
    
      =0){ if(res0[s][t]==='Q'){ return false; }else{ s++; t--; } } // // 左下角 s=i;t=j; while(s>=0&&t 
     
       { if(k>n-1){ res0.push(JSON.stringify(res)); }else{ // 怎么去考虑第k个皇后的摆放位置呢，显然需要双层循环,时间复杂度过高，无法AC // 但其实我们的k可以拿来充当k,试探每一个k行的每一列 // for(let i=0;i 
      
        { let arr=new Array(n),res0=[],res=new Array(n); const check=(row,col)=>{ for(let i=0;i 
       
         { if(k>n-1){ arr.forEach((item,idx)=>{ res[idx]=new Array(n).fill('.'); res[idx][item]='Q'; res[idx]=res[idx].join(''); }); res0.push(JSON.parse(JSON.stringify(res))); }else{ // 试探每一个k行的每一列 // for(let i=0;i 
         
        
       
      
     
    
  

leetcode-282-给表达式添加运算符

以下是两种方法，优化前的暴力遍历法和优化后的方法

• 问题的解是一组，即解用向量表示,因此用回溯法来解决，并且观察其特征应该是排列树(确定n个元素是满足某种性质的排列
• 以下是第一版代码。无法通过所有测试用例，原因实则是暴力遍历了所有可能结果，复杂度过高.
• 主要思路是通过最初用eval判断结果是否为target，但是每次eval运算耗费时间较长，优势是代码极其简单清晰，且不用单独处理乘法。

/* * @param {string} num * @param {number} target * @return {string[]} */ const addOperators = (num, target)=>{ 
    let res=[],ans=[]; const findRes=(num0,k)=>{ 
    if(num0.length<1) return; let flag=(num0.length>1&&num0[0]!=='0')||(num0.length===1); if(flag&&eval(`${ 
     res.slice(0,k).join('')}${ 
     num0}`)===target){ 
    res[k]=num0; ans.push(res.slice(0,k+1).join('')); }else{ 
    for(let i=0;i<num0.length;i++){ 
    res[k]=num0.slice(0, i + 1); res[k+1]='+'; findRes(num0.slice(i + 1), k+2); res[k+1]='-'; findRes(num0.slice(i + 1), k+2); res[k+1]='*'; findRes(num0.slice(i + 1),k+2); if(num0[0]==='0') break; } } }; findRes(num,0); return ans; }; 

======> 优化

• 合理降低暴力遍历的复杂度，暂存每次计算的val
• 优化方案中关键一步是如何处理像1-2*3*4*5这种情况，其若从1-2*3*4过渡需要：1-2*3*4-(-2*3*4)+(-2*3*4*5)
• 但在暴力求解的方法中通过校验最后一位加上后是否满足target的方式不容易取得pre即234的值
• 因此转而改变思路：通过判断最终结果是否符合条件，而像上面例子中暂存的结果如何判断呢，此时会非常容易(私以为本思路相对于官方思路更加清晰

/ * @param num * @param target * @returns {number} */ const addOperators2 = (num, target)=>{ 
    let res=[],ans=[]; const backTrack=(num0,val,pre,k)=>{ 
    if(num0.length<1){ 
    if(val===target){ 
    ans.push(res.slice(0,k).join('')); } return; } for(let i=0;i<num0.length;i++){ 
    if(k===0){ 
    res[k]=(num0.slice(0,i+1)); backTrack(num0.slice(i+1),Number(res[k]),Number(res[k]),k+1); }else{ 
    res[k]=('+'); res[k+1]=num0.slice(0,i+1); backTrack(num0.slice(i+1),val+Number(res[k+1]),Number(res[k+1]),k+2); res[k]=('-'); res[k+1]=num0.slice(0,i+1); backTrack(num0.slice(i+1),val-Number(res[k+1]),-Number(res[k+1]),k+2); res[k]=('*'); res[k+1]=num0.slice(0,i+1); backTrack(num0.slice(i+1),val-pre+pre*Number(res[k+1]),pre*Number(res[k+1]),k+2); } if(num0[0]==='0') break; } }; backTrack(num,0,0,0); return ans; };