經典算法之回溯法

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