回溯算法的遞歸和迭代

標(biāo)準(zhǔn)迭代范式

[回溯算法] 五大常用算法之回溯法

本文轉(zhuǎn)自2018年02月12日

算法入門6：回溯法

一. 回溯法 – 深度優(yōu)先搜素

1. 簡(jiǎn)單概述

   回溯法思路的簡(jiǎn)單描述是：把問(wèn)題的解空間轉(zhuǎn)化成了圖或者樹的結(jié)構(gòu)表示，然后使用深度優(yōu)先搜索策略進(jìn)行遍歷，遍歷的過(guò)程中記錄和尋找所有可行解或者最優(yōu)解。

基本思想類同于：

  • 圖的深度優(yōu)先搜索

  • 二叉樹的后序遍歷

     分支限界法：廣度優(yōu)先搜索

 思想類同于：圖的廣度優(yōu)先遍歷

                        二叉樹的層序遍歷

2. 詳細(xì)描述

    詳細(xì)的描述則為：

    回溯法按深度優(yōu)先策略搜索問(wèn)題的解空間樹。首先從根節(jié)點(diǎn)出發(fā)搜索解空間樹，當(dāng)算法搜索至解空間樹的某一節(jié)點(diǎn)時(shí)，先利用剪枝函數(shù)判斷該節(jié)點(diǎn)是否可行（即能得到問(wèn)題的解）。如果不可行，則跳過(guò)對(duì)該節(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先節(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。

    回溯法的基本行為是搜索，搜索過(guò)程使用剪枝函數(shù)來(lái)為了避免無(wú)效的搜索。剪枝函數(shù)包括兩類：1\. 使用約束函數(shù)，剪去不滿足約束條件的路徑；2.使用限界函數(shù)，剪去不能得到最優(yōu)解的路徑。

    問(wèn)題的關(guān)鍵在于如何定義問(wèn)題的解空間，轉(zhuǎn)化成樹（即解空間樹）。解空間樹分為兩種：子集樹和排列樹。兩種在算法結(jié)構(gòu)和思路上大體相同。

3. 回溯法應(yīng)用

   當(dāng)問(wèn)題是要求滿足某種性質(zhì)（約束條件）的所有解或最優(yōu)解時(shí)，往往使用回溯法。

   它有“通用解題法”之美譽(yù)。

二. 回溯法實(shí)現(xiàn) - 遞歸和遞推（迭代）

    回溯法的實(shí)現(xiàn)方法有兩種：遞歸和遞推（也稱迭代）。一般來(lái)說(shuō)，一個(gè)問(wèn)題兩種方法都可以實(shí)現(xiàn)，只是在算法效率和設(shè)計(jì)復(fù)雜度上有區(qū)別。

  【類比于圖深度遍歷的遞歸實(shí)現(xiàn)和非遞歸（遞推）實(shí)現(xiàn)】

1. 遞歸

思路簡(jiǎn)單，設(shè)計(jì)容易，但效率低，其設(shè)計(jì)范式如下：

1.  //針對(duì)N叉樹的遞歸回溯方法  
2.  void backtrack (int t)  
3.  {  
4.  if (t>n) output(x); //葉子節(jié)點(diǎn)，輸出結(jié)果，x是可行解  
5.  else  
6.  for i = 1 to k//當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)  
7.  {  
8.  x[t]=value(i); //每個(gè)子節(jié)點(diǎn)的值賦值給x  
9.  //滿足約束條件和限界條件  
10.  if (constraint(t)&&bound(t))   
11.  backtrack(t+1);  //遞歸下一層  
12.  }  
13.  }

2. 遞推

算法設(shè)計(jì)相對(duì)復(fù)雜，但效率高。

  1. //針對(duì)N叉樹的迭代回溯方法
  2. void iterativeBacktrack ()
  3. {
  4. int t=1;
  5. while (t>0) {
  6. if(ExistSubNode(t)) //當(dāng)前節(jié)點(diǎn)的存在子節(jié)點(diǎn)
  7. {
  8. for i = 1 to k //遍歷當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)
  9. {
  10. x[t]=value(i);//每個(gè)子節(jié)點(diǎn)的值賦值給x
  11. if (constraint(t)&&bound(t))//滿足約束條件和限界條件
  12. {
  13. //solution表示在節(jié)點(diǎn)t處得到了一個(gè)解
  14. if (solution(t)) output(x);//得到問(wèn)題的一個(gè)可行解，輸出
  15. else t++;//沒有得到解，繼續(xù)向下搜索
  16. }
  17. }
  18. }
  19. else //不存在子節(jié)點(diǎn)，返回上一層
  20. {
  21. t--;
  22. }
  23. }
  24. }

三. 子集樹和排列樹

1. 子集樹

   所給的問(wèn)題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間成為子集樹。

如0-1背包問(wèn)題，從所給重量、價(jià)值不同的物品中挑選幾個(gè)物品放入背包，使得在滿足背包不超重的情況下，背包內(nèi)物品價(jià)值最大。它的解空間就是一個(gè)典型的子集樹。

   回溯法搜索子集樹的算法范式如下：

[cpp] view plain copy

  1. void backtrack (int t)
  2. {
  3. if (t>n) output(x);
  4. else
  5. for (int i=0;i<=1;i++) {
  6. x[t]=i;
  7. if (constraint(t)&&bound(t)) backtrack(t+1);
  8. }
  9. }

2. 排列樹

  所給的問(wèn)題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間就是排列樹。

如旅行售貨員問(wèn)題，一個(gè)售貨員把幾個(gè)城市旅行一遍，要求走的路程最小。它的解就是幾個(gè)城市的排列，解空間就是排列樹。

  回溯法搜索排列樹的算法范式如下：

[cpp] view plain copy

  1. void backtrack (int t)
  2. {
  3. if (t>n) output(x);
  4. else
  5. for (int i=t;i<=n;i++) {
  6. swap(x[t], x[i]);
  7. if (constraint(t)&&bound(t)) backtrack(t+1);
  8. swap(x[t], x[i]);
  9. }
  10. }

四. 經(jīng)典問(wèn)題

（1）裝載問(wèn)題

（2）0-1背包問(wèn)題

（3）旅行售貨員問(wèn)題

（4）八皇后問(wèn)題

（5）迷宮問(wèn)題

（6）圖的m著色問(wèn)題

1. 0-1背包問(wèn)題

    問(wèn)題：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為pi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

    分析：?jiǎn)栴}是n個(gè)物品中選擇部分物品，可知，問(wèn)題的解空間是子集樹。比如物品數(shù)目n=3時(shí)，其解空間樹如下圖，邊為1代表選擇該物品，邊為0代表不選擇該物品。使用x[i]表示物品i是否放入背包，x[i]=0表示不放，x[i]=1表示放入?；厮菟阉鬟^(guò)程，如果來(lái)到了葉子節(jié)點(diǎn)，表示一條搜索路徑結(jié)束，如果該路徑上存在更優(yōu)的解，則保存下來(lái)。如果不是葉子節(jié)點(diǎn)，是中點(diǎn)的節(jié)點(diǎn)（如B），就遍歷其子節(jié)點(diǎn)（D和E），如果子節(jié)點(diǎn)滿足剪枝條件，就繼續(xù)回溯搜索子節(jié)點(diǎn)。

[圖片上傳失敗...(image-a1757f-1552436966753)]

代碼：

[cpp] view plain copy

  1. include <stdio.h>

  2. define N 3 //物品的數(shù)量

  3. define C 16 //背包的容量

  4. int w[N]={10,8,5}; //每個(gè)物品的重量

  5. int v[N]={5,4,1}; //每個(gè)物品的價(jià)值

  6. int x[N]={0,0,0}; //x[i]=1代表物品i放入背包，0代表不放入

  7. int CurWeight = 0; //當(dāng)前放入背包的物品總重量

  8. int CurValue = 0; //當(dāng)前放入背包的物品總價(jià)值

  9. int BestValue = 0; //最優(yōu)值；當(dāng)前的最大價(jià)值，初始化為0

  10. int BestX[N]; //最優(yōu)解；BestX[i]=1代表物品i放入背包，0代表不放入

  11. //t = 0 to N-1

  12. void backtrack(int t)

  13. {

  14. //葉子節(jié)點(diǎn)，輸出結(jié)果

  15. if(t>N-1)

  16. {

  17. //如果找到了一個(gè)更優(yōu)的解

  18. if(CurValue>BestValue)

  19. {

  20. //保存更優(yōu)的值和解

  21. BestValue = CurValue;

  22. for(int i=0;i<N;++i) BestX[i] = x[i];

  23. }

  24. }

  25. else

  26. {

  27. //遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)：0 不放入背包，1放入背包

  28. for(int i=0;i<=1;++i)

  29. {

  30. x[t]=i;

  31. if(i==0) //不放入背包

  32. {

  33. backtrack(t+1);

  34. }

  35. else //放入背包

  36. {

  37. //約束條件：放的下

  38. if((CurWeight+w[t])<=C)

  39. {

  40. CurWeight += w[t];

  41. CurValue += v[t];

  42. backtrack(t+1);

  43. CurWeight -= w[t];

  44. CurValue -= v[t];

  45. }

  46. }

  47. }

  48. //PS:上述代碼為了更符合遞歸回溯的范式，并不夠簡(jiǎn)潔

  49. }

  50. }

  51. int main(int argc, char* argv[])

  52. {

  53. backtrack(0);

  54. printf("最優(yōu)值：%d\n",BestValue);

  55. for(int i=0;i<N;i++)

  56. {

  57. printf("最優(yōu)解：%-3d",BestX[i]);

  58. }

  59. return 0;

  60. }

2. 旅行售貨員問(wèn)題

  [回溯法----旅行售貨員問(wèn)題](http://blog.csdn.net/jarvischu/article/details/6058931)

3. 詳細(xì)描述N皇后問(wèn)題

   問(wèn)題：在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

   N皇后問(wèn)題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。

  分析：從n×n個(gè)格子中選擇n個(gè)格子擺放皇后?？梢娊饪臻g樹為子集樹。

  使用Board[N][N]來(lái)表示棋盤，Board[i][j]=0 表示(I,j)位置為空，Board[i][j]=1 表示(I,j)位置擺放有一個(gè)皇后。

  全局變量way表示總共的擺放方法數(shù)目。

  使用Queen(t)來(lái)擺放第t個(gè)皇后。Queen(t) 函數(shù)符合子集樹時(shí)的遞歸回溯范式。當(dāng)t>N時(shí)，說(shuō)明所有皇后都已經(jīng)擺   放完成，這是一個(gè)可行的擺放方法，輸出結(jié)果；否則，遍歷棋盤，找皇后t所有可行的擺放位置，F(xiàn)easible(i,j) 判斷皇后t能否擺放在位置(i,j)處，如果可以擺放則繼續(xù)遞歸擺放皇后t+1，如果不能擺放，則判斷下一個(gè)位置。

   Feasible(row,col)函數(shù)首先判斷位置(row,col)是否合法，繼而判斷(row,col)處是否已有皇后，有則沖突，返回0，無(wú)則繼續(xù)判斷行、列、斜方向是否沖突。斜方向分為左上角、左下角、右上角、右下角四個(gè)方向，每次從（row,col）向四個(gè)方向延伸一個(gè)格子，判斷是否沖突。如果所有方向都沒有沖突，則返回1，表示此位置可以擺放一個(gè)皇后。

[圖片上傳失敗...(image-d4906e-1552436966752)]

    代碼：


1.  /************************************************************************  
2.  * 名  稱：NQueen.cpp 
3.  * 功  能：回溯算法實(shí)例：N皇后問(wèn)題  
4.  * 作  者：JarvisChu  
5.  * 時(shí)  間：2013-11-13  
6.  ************************************************************************/   

8.  #include <stdio.h>  

10.  #define N 8  

12.  int Board[N][N];//棋盤 0表示空白 1表示有皇后  
13.  int way;//擺放的方法數(shù)  

16.  //判斷能否在(x,y)的位置擺放一個(gè)皇后；0不可以，1可以  
17.  int Feasible(int row,int col)  
18.  {  
19.  //位置不合法  
20.  if(row>N || row<0 || col >N || col<0)  
21.  return 0;  

23.  //該位置已經(jīng)有皇后了，不能  
24.  if(Board[row][col] != 0)  
25.  {   //在行列沖突判斷中也包含了該判斷，單獨(dú)提出來(lái)為了提高效率  
26.  return 0;  
27.  }  

29.  //////////////////////////////////////////////////  
30.  //下面判斷是否和已有的沖突  

32.  //行和列是否沖突  
33.  for(int i=0;i<N;++i)  
34.  {  
35.  if(Board[row][i] != 0 || Board[i][col]!=0)  
36.  return 0;  
37.  }  

39.  //斜線方向沖突  

41.  for(int i=1;i<N;++i)  
42.  {  
43.  /* i表示從當(dāng)前點(diǎn)(row,col)向四個(gè)斜方向擴(kuò)展的長(zhǎng)度 

45.  左上角 \  / 右上角   i=2 
46.  \/           i=1 
47.  /\           i=1 
48.  左下角 /  \ 右下角   i=2 
49.  */  
50.  //左上角  
51.  if((row-i)>=0 && (col-i)>=0)    //位置合法  
52.  {  
53.  if(Board[row-i][col-i] != 0)//此處已有皇后，沖突  
54.  return 0;  
55.  }  

57.  //左下角  
58.  if((row+i)<N && (col-i)>=0)  
59.  {  
60.  if(Board[row+i][col-i] != 0)  
61.  return 0;  
62.  }  

64.  //右上角  
65.  if((row-i)>=0 && (col+i)<N)  
66.  {  
67.  if(Board[row-i][col+i] != 0)  
68.  return 0;  
69.  }  

71.  //右下角  
72.  if((row+i)<N && (col+i)<N)  
73.  {  
74.  if(Board[row+i][col+i] != 0)  
75.  return 0;  
76.  }  
77.  }  

79.  return 1; //不會(huì)發(fā)生沖突，返回1  
80.  }  

83.  //擺放第t個(gè)皇后 ；從1開始  
84.  void Queen(int t)  
85.  {  
86.  //擺放完成，輸出結(jié)果  
87.  if(t>N)  
88.  {  
89.  way++;  
90.  /*如果N較大，輸出結(jié)果會(huì)很慢；N較小時(shí)，可以用下面代碼輸出結(jié)果 
91.  for(int i=0;i<N;++i){ 
92.  for(int j=0;j<N;++j) 
93.  printf("%-3d",Board[i][j]); 
94.  printf("\n"); 
95.  } 
96.  printf("\n------------------------\n\n"); 
97.  */  
98.  }  
99.  else  
100.  {  
101.  for(int i=0;i<N;++i)  
102.  {  
103.  for(int j=0;j<N;++j)  
104.  {  
105.  //（i,j）位置可以擺放皇后，不沖突  
106.  if(Feasible(i,j))  
107.  {  
108.  Board[i][j] = 1;  //擺放皇后t  
109.  Queen(t+1);       //遞歸擺放皇后t+1  
110.  Board[i][j] = 0;  //恢復(fù)  
111.  }  
112.  }  
113.  }  
114.  }  
115.  }  

117.  //返回num的階乘,num!  
118.  int factorial(int num)  
119.  {  
120.  if(num==0 || num==1)  
121.  return 1;  
122.  return num*factorial(num-1);  
123.  }  

126.  int main(int argc, char* argv[])  
127.  {  
128.  //初始化  
129.  for(int i=0;i<N;++i)  
130.  {  
131.  for(int j=0;j<N;++j)  
132.  {  
133.  Board[i][j]=0;  
134.  }  
135.  }  

137.  way = 0;  

139.  Queen(1);  //從第1個(gè)皇后開始擺放  

141.  //如果每個(gè)皇后都不同  
142.  printf("考慮每個(gè)皇后都不同，擺放方法：%d\n",way);//N=8時(shí), way=3709440 種  

144.  //如果每個(gè)皇后都一樣，那么需要除以 N！出去重復(fù)的答案（因?yàn)橄嗤?，則每個(gè)皇后可任意調(diào)換位置）  
145.  printf("考慮每個(gè)皇后都不同，擺放方法：%d\n",way/factorial(N));//N=8時(shí), way=3709440/8! = 92種  

147.  return 0;  
148.  }

PS：該問(wèn)題還有更優(yōu)的解法。充分利用問(wèn)題隱藏的約束條件：每個(gè)皇后必然在不同的行(列)，每個(gè)行(列)必然也只有一個(gè)皇后。這樣我們就可以把N個(gè)皇后放到N個(gè)行中，使用Pos[i]表示皇后i在i行中的位置（也就是列號(hào)）（i = 0 to N-1）。這樣代碼會(huì)大大的簡(jiǎn)潔，因?yàn)楣?jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目會(huì)減少，判斷沖突也更簡(jiǎn)單。

4. 迷宮問(wèn)題

    問(wèn)題：給定一個(gè)迷宮，找到從入口到出口的所有可行路徑，并給出其中最短的路徑

    分析：用二維數(shù)組來(lái)表示迷宮，則走迷宮問(wèn)題用回溯法解決的的思想類似于圖的深度遍歷。從入口開始，選擇下一個(gè)可以走的位置，如果位置可走，則繼續(xù)往前，如果位置不可走，則返回上一個(gè)位置，重新選擇另一個(gè)位置作為下一步位置。

    N表示迷宮的大小，使用Maze[N][N]表示迷宮，值為0表示通道（可走），值為1表示不可走（墻或者已走過(guò)）；

    Point結(jié)構(gòu)體用來(lái)記錄路徑中每一步的坐標(biāo)(x,y)

   (ENTER_X,ENTER_Y) 是迷宮入口的坐標(biāo)

   (EXIT_X, EXIT _Y)    是迷宮出口的坐標(biāo)

   Path容器用來(lái)存放一條從入口到出口的通路路徑

   BestPath用來(lái)存放所有路徑中最短的那條路徑

   Maze()函數(shù)用來(lái)遞歸走迷宮，具體步驟為：

   1\. 首先將當(dāng)前點(diǎn)加入路徑，并設(shè)置為已走

   2\. 判斷當(dāng)前點(diǎn)是否為出口，是則輸出路徑，保存結(jié)果；跳轉(zhuǎn)到4

   3\. 依次判斷當(dāng)前點(diǎn)的上、下、左、右四個(gè)點(diǎn)是否可走，如果可走則遞歸走該點(diǎn)

   4\. 當(dāng)前點(diǎn)推出路徑，設(shè)置[為可]

PS：用WPF實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的圖形化迷宮程序。白色表示通道，紅色表示墻，最短的路徑用黃色顯示。目前實(shí)現(xiàn)了一個(gè)10*10的迷宮自動(dòng)搜素最短通路，右側(cè)顯示搜索過(guò)程中得到的每一個(gè)可行通路。

由于構(gòu)造一個(gè)迷宮比較復(fù)雜，所以暫時(shí)“迷宮設(shè)置”功能沒有做實(shí)現(xiàn)，至于手動(dòng)一步步查看搜素過(guò)程的動(dòng)畫也沒有做實(shí)現(xiàn)。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容