標(biāo)準(zhǔn)迭代范式
[回溯算法] 五大常用算法之回溯法
本文轉(zhuǎn)自2018年02月12日
算法入門6：回溯法
一. 回溯法 – 深度優(yōu)先搜素
1. 簡(jiǎn)單概述
回溯法思路的簡(jiǎn)單描述是：把問題的解空間轉(zhuǎn)化成了圖或者樹的結(jié)構(gòu)表示，然后使用深度優(yōu)先搜索策略進(jìn)行遍歷醉旦，遍歷的過程中記錄和尋找所有可行解或者最優(yōu)解宦言。
基本思想類同于：
圖的深度優(yōu)先搜索
-
二叉樹的后序遍歷
分支限界法：廣度優(yōu)先搜索 思想類同于：圖的廣度優(yōu)先遍歷 二叉樹的層序遍歷
2. 詳細(xì)描述
詳細(xì)的描述則為：
回溯法按深度優(yōu)先策略搜索問題的解空間樹庆揩。首先從根節(jié)點(diǎn)出發(fā)搜索解空間樹揪利，當(dāng)算法搜索至解空間樹的某一節(jié)點(diǎn)時(shí)壮池，先利用剪枝函數(shù)判斷該節(jié)點(diǎn)是否可行（即能得到問題的解）粥庄。如果不可行爹凹，則跳過對(duì)該節(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先節(jié)點(diǎn)回溯身诺；否則蜜托，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索霉赡。
回溯法的基本行為是搜索橄务，搜索過程使用剪枝函數(shù)來為了避免無效的搜索。剪枝函數(shù)包括兩類：1\. 使用約束函數(shù)穴亏，剪去不滿足約束條件的路徑蜂挪；2.使用限界函數(shù)重挑，剪去不能得到最優(yōu)解的路徑。
問題的關(guān)鍵在于如何定義問題的解空間棠涮，轉(zhuǎn)化成樹（即解空間樹）谬哀。解空間樹分為兩種：子集樹和排列樹。兩種在算法結(jié)構(gòu)和思路上大體相同严肪。
3. 回溯法應(yīng)用
當(dāng)問題是要求滿足某種性質(zhì)（約束條件）的所有解或最優(yōu)解時(shí)史煎，往往使用回溯法。
它有“通用解題法”之美譽(yù)驳糯。
二. 回溯法實(shí)現(xiàn) - 遞歸和遞推（迭代）
回溯法的實(shí)現(xiàn)方法有兩種：遞歸和遞推（也稱迭代）篇梭。一般來說，一個(gè)問題兩種方法都可以實(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ù)雜协怒，但效率高。
- //針對(duì)N叉樹的迭代回溯方法
- void iterativeBacktrack ()
- {
- int t=1;
- while (t>0) {
- if(ExistSubNode(t)) //當(dāng)前節(jié)點(diǎn)的存在子節(jié)點(diǎn)
- {
- for i = 1 to k //遍歷當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)
- {
- x[t]=value(i);//每個(gè)子節(jié)點(diǎn)的值賦值給x
- if (constraint(t)&&bound(t))//滿足約束條件和限界條件
- {
- //solution表示在節(jié)點(diǎn)t處得到了一個(gè)解
- if (solution(t)) output(x);//得到問題的一個(gè)可行解卑笨，輸出
- else t++;//沒有得到解孕暇，繼續(xù)向下搜索
- }
- }
- }
- else //不存在子節(jié)點(diǎn)，返回上一層
- {
- t--;
- }
- }
- }
三. 子集樹和排列樹
1. 子集樹
所給的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)赤兴，相應(yīng)的解空間成為子集樹妖滔。
如0-1背包問題，從所給重量桶良、價(jià)值不同的物品中挑選幾個(gè)物品放入背包座舍，使得在滿足背包不超重的情況下，背包內(nèi)物品價(jià)值最大陨帆。它的解空間就是一個(gè)典型的子集樹曲秉。
回溯法搜索子集樹的算法范式如下：
[cpp] view plain copy
- void backtrack (int t)
- {
- if (t>n) output(x);
- else
- for (int i=0;i<=1;i++) {
- x[t]=i;
- if (constraint(t)&&bound(t)) backtrack(t+1);
- }
- }
2. 排列樹
所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間就是排列樹疲牵。
如旅行售貨員問題承二，一個(gè)售貨員把幾個(gè)城市旅行一遍，要求走的路程最小纲爸。它的解就是幾個(gè)城市的排列亥鸠，解空間就是排列樹。
回溯法搜索排列樹的算法范式如下：
[cpp] view plain copy
- void backtrack (int t)
- {
- if (t>n) output(x);
- else
- for (int i=t;i<=n;i++) {
- swap(x[t], x[i]);
- if (constraint(t)&&bound(t)) backtrack(t+1);
- swap(x[t], x[i]);
- }
- }
四. 經(jīng)典問題
（1）裝載問題
（2）0-1背包問題
（3）旅行售貨員問題
（4）八皇后問題
（5）迷宮問題
（6）圖的m著色問題
1. 0-1背包問題
問題：給定n種物品和一背包。物品i的重量是wi负蚊，其價(jià)值為pi神妹，背包的容量為C。問應(yīng)如何選擇裝入背包的物品家妆，使得裝入背包中物品的總價(jià)值最大?
分析：?jiǎn)栴}是n個(gè)物品中選擇部分物品鸵荠，可知，問題的解空間是子集樹伤极。比如物品數(shù)目n=3時(shí)蛹找，其解空間樹如下圖，邊為1代表選擇該物品塑荒，邊為0代表不選擇該物品熄赡。使用x[i]表示物品i是否放入背包姜挺，x[i]=0表示不放齿税，x[i]=1表示放入〈逗溃回溯搜索過程凌箕，如果來到了葉子節(jié)點(diǎn)，表示一條搜索路徑結(jié)束词渤，如果該路徑上存在更優(yōu)的解牵舱，則保存下來。如果不是葉子節(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
-
include <stdio.h>
-
define N 3 //物品的數(shù)量
-
define C 16 //背包的容量
int w[N]={10,8,5}; //每個(gè)物品的重量
int v[N]={5,4,1}; //每個(gè)物品的價(jià)值
int x[N]={0,0,0}; //x[i]=1代表物品i放入背包，0代表不放入
int CurWeight = 0; //當(dāng)前放入背包的物品總重量
int CurValue = 0; //當(dāng)前放入背包的物品總價(jià)值
int BestValue = 0; //最優(yōu)值剪芍；當(dāng)前的最大價(jià)值塞淹，初始化為0
int BestX[N]; //最優(yōu)解；BestX[i]=1代表物品i放入背包罪裹，0代表不放入
//t = 0 to N-1
void backtrack(int t)
{
//葉子節(jié)點(diǎn)饱普，輸出結(jié)果
if(t>N-1)
{
//如果找到了一個(gè)更優(yōu)的解
if(CurValue>BestValue)
{
//保存更優(yōu)的值和解
BestValue = CurValue;
for(int i=0;i<N;++i) BestX[i] = x[i];
}
}
else
{
//遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)：0 不放入背包，1放入背包
for(int i=0;i<=1;++i)
{
x[t]=i;
if(i==0) //不放入背包
{
backtrack(t+1);
}
else //放入背包
{
//約束條件：放的下
if((CurWeight+w[t])<=C)
{
CurWeight += w[t];
CurValue += v[t];
backtrack(t+1);
CurWeight -= w[t];
CurValue -= v[t];
}
}
}
//PS:上述代碼為了更符合遞歸回溯的范式状共，并不夠簡(jiǎn)潔
}
}
int main(int argc, char* argv[])
{
backtrack(0);
printf("最優(yōu)值：%d\n",BestValue);
for(int i=0;i<N;i++)
{
printf("最優(yōu)解：%-3d",BestX[i]);
}
return 0;
}
2. 旅行售貨員問題
[回溯法----旅行售貨員問題](http://blog.csdn.net/jarvischu/article/details/6058931)
3. 詳細(xì)描述N皇后問題
問題：在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后套耕。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子峡继。
N皇后問題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后箍铲，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。
分析：從n×n個(gè)格子中選擇n個(gè)格子擺放皇后鬓椭〉吆铮可見解空間樹為子集樹关划。
使用Board[N][N]來表示棋盤，Board[i][j]=0 表示(I,j)位置為空翘瓮，Board[i][j]=1 表示(I,j)位置擺放有一個(gè)皇后贮折。
全局變量way表示總共的擺放方法數(shù)目。
使用Queen(t)來擺放第t個(gè)皇后资盅。Queen(t) 函數(shù)符合子集樹時(shí)的遞歸回溯范式调榄。當(dāng)t>N時(shí)，說明所有皇后都已經(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馋劈，無則繼續(xù)判斷行、列晾嘶、斜方向是否沖突妓雾。斜方向分為左上角、左下角变擒、右上角君珠、右下角四個(gè)方向，每次從（row,col）向四個(gè)方向延伸一個(gè)格子娇斑，判斷是否沖突策添。如果所有方向都沒有沖突，則返回1毫缆，表示此位置可以擺放一個(gè)皇后唯竹。
[圖片上傳失敗...(image-d4906e-1552436966752)]
代碼：
1. /************************************************************************
2. * 名 稱：NQueen.cpp
3. * 功 能：回溯算法實(shí)例：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ú)提出來為了提高效率
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)橄嗤顺玻瑒t每個(gè)皇后可任意調(diào)換位置）
145. printf("考慮每個(gè)皇后都不同，擺放方法：%d\n",way/factorial(N));//N=8時(shí), way=3709440/8! = 92種
147. return 0;
148. }
PS：該問題還有更優(yōu)的解法兼耀。充分利用問題隱藏的約束條件：每個(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. 迷宮問題
問題：給定一個(gè)迷宮梧躺，找到從入口到出口的所有可行路徑似谁，并給出其中最短的路徑
分析：用二維數(shù)組來表示迷宮，則走迷宮問題用回溯法解決的的思想類似于圖的深度遍歷掠哥。從入口開始巩踏，選擇下一個(gè)可以走的位置，如果位置可走续搀，則繼續(xù)往前塞琼，如果位置不可走，則返回上一個(gè)位置禁舷，重新選擇另一個(gè)位置作為下一步位置彪杉。
N表示迷宮的大小，使用Maze[N][N]表示迷宮牵咙，值為0表示通道（可走）派近，值為1表示不可走（墻或者已走過）；
Point結(jié)構(gòu)體用來記錄路徑中每一步的坐標(biāo)(x,y)
(ENTER_X,ENTER_Y) 是迷宮入口的坐標(biāo)
(EXIT_X, EXIT _Y) 是迷宮出口的坐標(biāo)
Path容器用來存放一條從入口到出口的通路路徑
BestPath用來存放所有路徑中最短的那條路徑
Maze()函數(shù)用來遞歸走迷宮洁桌，具體步驟為：
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è)顯示搜索過程中得到的每一個(gè)可行通路。
由于構(gòu)造一個(gè)迷宮比較復(fù)雜刃麸，所以暫時(shí)“迷宮設(shè)置”功能沒有做實(shí)現(xiàn)醒叁，至于手動(dòng)一步步查看搜素過程的動(dòng)畫也沒有做實(shí)現(xiàn)。
