经典算法之回溯法

2019 年 11 月 14 日
笔记

概念

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

基本思想

回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。

剪枝函数包括两类：

1. 使用约束函数，剪去不满足约束条件的路径；

2.使用限界函数，剪去不能得到最优解的路径。

问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。

解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。

实现思路

回溯法的实现方法有两种：递归和迭代。一般来说，一个问题两种方法都可以实现，只是在算法效率和设计复杂度上有区别。

1. 递归

思路简单，设计容易，但效率低，其设计范式如下：

//针对N叉树的递归回溯方法  void backtrack (int t){      if (t>n) output(x);      //叶子节点，输出结果，x是可行解          else          for i = 1 to k          //当前节点的所有子节点          {              x[t]=value(i);              //每个子节点的值赋值给x              //满足约束条件和限界条件               if (constraint(t)&&bound(t))                   backtrack(t+1);              //递归下一层            }  }

2.迭代

算法设计相对复杂，但效率高。

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

经典实例-八皇后问题

背景：八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

演算推理：八皇后比较多，那么先从4皇后（在4X4的棋盘上放4个皇后）开始

一开始，棋盘是空的，第1个皇后可以任意放置，但为了思考方便，最好是按照秩序来尝试，于是先将第1个皇后放置在棋盘第1行第1列格子里。

第1行已经有了皇后，下一步是寻找第2行皇后的位置。在这之前，需要计算出第2行此时未被第1个皇后攻击的棋格分布。

上图中呈现的是整个棋盘的状态，但此时关注的重点在第2行。接下来，将第2个皇后放置于第2行第3列棋格中。

现在，第1行和第2行都有皇后了，重新计算棋盘状态，以寻找第3行的皇后位置。

经过计算，第3行的所有棋格已经全部处于第1个和第2个皇后的联合攻击范围内了，虽然第4行还有空位，但已经无关紧要，当前尝试可以宣告 Game Over 了。

换句话说，刚才的第2个皇后位置不对。调整一下，将第2个皇后从第3列挪到第4列再试试。

调整之后，继续更新棋盘状态。

此时，第3行有一个可用的空位，于是将第3个皇后放在这个棋格中。

然后再次更新棋盘状态。

Oops，又遇到了类似的情况，第4行已经没有棋格可以用了，所以，刚才的第3个皇后位置不对。

但第3行只有一个空位可以用，而这唯一的一个空位又是错误的，这说明，问题还是出在第2个皇后的位置上。

再进一步回溯分析，可以发现，第2行可用的棋格已经都尝试过了，然而都不对。

所以，问题其实出在第1个皇后的位置上。也就是说，第一步将皇后放置于第1行第1列的摆法就错了。

知错就改，善莫大焉。将第1个皇后挪到第1行第2列，重头再来。

继续，更新棋盘状态。

根据上图，将第2个皇后置于第2行第4列。

继续，更新棋盘状态。

看上去不错，接着，将第3个皇后置于第3行第1列。

继续，更新棋盘状态。

咦，似乎成了。

BINGO！4皇后的第一个解，找到了。

以上就是回溯法的思想，下面八皇后问题的92种方案代码如下：

public class Queen {      public static int num=0;  //累计方案      public static final int MaxQueen=8;   //最多多少个皇后      public static int[] clos=new int[MaxQueen];    //8列皇后的位置      public void getCount(int n){               //n为填第几列皇后，之后递归填完          boolean[]  old=new boolean[MaxQueen];//记录当前格子是否可以放，已经放了就为true          for(int m=0;m<n;m++){            //之前的横排不能放              old[clos[m]]=true;                        // clos[0]=1;clow[1]=2;代表第0列的第一个和第1列的第二个已经放了              int d=n-m;          //斜对角              //正斜方向              if(clos[m]-d>=0){                  old[clos[m]-d]=true;               }            //反斜方向              if(clos[m]+d<=(MaxQueen-1)){                  old[clos[m]+d]=true;              }          }        //到此知道了哪些位置不能放皇后          for(int i=0;i<MaxQueen;i++){              if(old[i]){                //代表之前行放过。不能放                  continue;              }              clos[n]=i;            //下面仍可能有合法位置              if(n<MaxQueen-1){                  getCount(n+1);              }              else              {                //找完整了                  num++;                  printQueen();              }          }      }      private void printQueen() {          System.out.println("第"+num+"方案");          for(int i=0;i<MaxQueen;i++){              for(int j=0;j<MaxQueen;j++){                  if(i==clos[j]){                      System.out.print("0 ");                  }else{                      System.out.print("+");                  }              }              System.out.println();          }      }      public static void main(String[] args) {          Queen qu=new Queen();          qu.getCount(0);      }  }

面试题-括号生成

回溯法经常出现在面试中，例如本题也是用到了回溯法，当然还有其他解法，本文主讲回溯法。

题目：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

["((()))","(()())","(())()","()(())","()()()"]

思路和算法：只有在我们知道序列仍然保持有效时才添加 '(' or ')'，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果我们还剩一个位置，我们可以开始放一个左括号。如果它不超过左括号的数量，我们可以放一个右括号。代码如下：

class Solution {      public List<String> generateParenthesis(int n) {          List<String> ans = new ArrayList();          backtrack(ans, "", 0, 0, n);          return ans;      }      public void backtrack(List<String> ans, String cur, int open, int close, int max){          if (cur.length() == max * 2) {              ans.add(cur);              return;          }          if (open < max)              backtrack(ans, cur+"(", open+1, close, max);          if (close < open)              backtrack(ans, cur+")", open, close+1, max);          }      }

参考文档

https://www.cnblogs.com/libra-yong/p/6390303.html

https://www.cnblogs.com/houkai/p/3480940.html

http://www.sohu.com/a/224239296684445

https://www.cnblogs.com/sherrywasp/archive/2018/10/10/9765921.html

https://www.cnblogs.com/jiaxin359/p/9588827.html#label0

https://dwz.cn/RBMLaiP5