B5-搜索與回溯算法

1、搜索與回溯算法搜索與回溯算法應(yīng)用范圍：遇到無法根據(jù)某種確定的計算法則來求解的問題，往往采用搜索所有可能情況的方法來進(jìn)行求解?；厮菔菍崿F(xiàn)搜索的一種策略。回溯的基本思想：類似走迷宮，為了求得問題的解，先選擇一種可能情況向前探索，一旦發(fā)現(xiàn)選擇錯誤（無路可走了），則退回一步重新選擇，然后繼續(xù)向前探索。簡單來說就是“走不通就掉頭”。遞歸回溯算法框架int Search(int k)if (到目的地) 輸出解;elsefor (i=1;i=算符種數(shù);i+)if (滿足條件) 保存當(dāng)前結(jié)果;Search(k+1);恢復(fù)：撤銷當(dāng)前結(jié)果回溯一步搜索與回溯算法例1素數(shù)環(huán)從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩

2、個數(shù)的和是一個素數(shù)?！舅惴ǚ治觥窟@是一道回溯的題目。從1開始，每個空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個素數(shù)。第20個數(shù)還要判斷和第1個數(shù)的和是否素數(shù)?！舅惴鞒獭?、數(shù)據(jù)初始化；2、遞歸填數(shù)：判斷第i個數(shù)填入是否合法；A、合法：填數(shù)；判斷是否到達(dá)目標(biāo)（20個已填完）：是，打印結(jié)果；不是，填下一個數(shù)；B、不合法：選擇下一種可能；有合法的數(shù)jai:=j沒有合法的數(shù)a1a2ai-1a20aiai+1ai-1尋找下一個合法的數(shù)ai+1從1開始尋找合法的數(shù)搜索與回溯算法例1#include#include#include#includeusing namesp

3、ace std;#define N 10bool bN+1=0;/表示數(shù)字是否可用int total=0,aN+1=0;bool pd(int x,int y)/判斷素數(shù)int k=2,i=x+y;while(ksqrt(i)return 1;else return 0;void print()/輸出方案total+;couttotal;for(int j=1;j=N;j+)coutaj ;coutendl;int search(int t)/回溯過程int i;for(i=1;i=N;i+)/有N個數(shù)可選if(!bi)&(t=1|pd(at-1,i)/判斷該數(shù)是否可用及與前一個數(shù)是否構(gòu)成素數(shù)

4、at=i;bi=1;if(t=N)if(pd(aN,a1) print();else search(t+1);bi=0;int main()search(1);couttotalendl;/輸出總方案數(shù)搜索與回溯算法例2設(shè)有n個整數(shù)的集合1,2,n，從中取出任意r個數(shù)進(jìn)行排列（rn），試列出所有的排列。#include#include#includeusing namespace std;int num=0,a10001=0,n,r;bool b10001=0;int print()/輸出方案num+;for (int i=1;i=r;i+)coutsetw(3)ai;coutendl; in

5、t search(int k)/回溯過程int i;for (i=1;i=n;i+)if(!bi)/判斷i是否可用ak=i;/保存結(jié)果bi=1; /標(biāo)記i不可用if (k=r) print();else search(k+1);bi=0; /標(biāo)記i可用int main()coutnr;search(1);coutnumber=numendl;搜索與回溯算法例3自然數(shù)的拆分任何一個大于1的自然數(shù)n，總可以拆分成若干個小于n的自然數(shù)之和。根據(jù)n的值，輸出拆分的方法總數(shù)。當(dāng)n=7時，共有14種拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+

6、27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14搜索與回溯算法例3#include#include#includeusing namespace std;int a10001=1,n,total;int search(int,int);int print(int);/輸出一種拆分方案int print(int t)coutn=;for (int i=1;i=t-1;i+)coutai+;coutatendl;total+;/方案數(shù)累加1/回溯過程，s為待拆分的數(shù)，t表示第幾個拆分?jǐn)?shù)in

7、t search(int s,int t)int i;/i是當(dāng)前拆分出來的數(shù)for (i=at-1;i=s;i+) /i要大于等于前1位數(shù)if (in;search(n,1);/將待拆分的數(shù)n傳遞給scouttotal=totalendl;搜索與回溯算法例4八皇后問題要在國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一對角線的任意棋子。）1234567812345678搜索與回溯算法例4【算法分析】顯然，每行有且僅有一個皇后。我們規(guī)定第i個皇后放置在第i行，用ai=j表示第i行皇后處于j列，然后逐行來放置皇后，即對每個i搜索合適的j值。/放置第i個(行

8、)皇后int search(i)；int j;for (第i個皇后的列位置j=1;j=8;j+ )if (i行j列允許放置皇后)放置第i個皇后，對放置皇后的位置進(jìn)行標(biāo)記；if (i=8) 輸出/已經(jīng)放完8個皇后elsesearch(i+1)；/放置第i+1個皇后取消放置，釋放位置標(biāo)記，嘗試下一個位置是否可行；搜索與回溯算法例4第i個皇后能放置在j列的條件：j列沒有其它皇后，j不重復(fù)，用數(shù)組b1.8判斷對角線1沒有其它皇后，i+j不重復(fù)：用數(shù)組c1.16判斷對角線2沒有其它皇后，i-j不重復(fù)：用數(shù)組d-7.7判斷，但C數(shù)組下標(biāo)從0開始，修正為i-j+7不重復(fù)，用數(shù)組d0.14判斷12345678

9、12345678對角線2對角線1搜索與回溯算法例4#include#include#includeusing namespace std;bool d100=0,b100=0,c100=0;int sum=0,a100;int print()int i;sum+;/方案數(shù)累加1coutsum=sumendl;for (i=1;i=8;i+)/輸出一種方案coutsetw(4)ai;coutendl;int search(int i)/放置第i個(行)皇后int j;for (j=1;j2,1-3,3-1,4-3,5-2,7-4,80123456784321搜索與回溯算法例5【算法分析】馬最多有

10、四個方向，若原來的橫坐標(biāo)為j、縱坐標(biāo)為i,則四個方向的移動可表示為：1:(i,j)(i+2,j+1)； (i3,j8)2:(i,j)(i+1,j+2)； (i4,j0,j1,j8)搜索策略：S1:A1:=(0,0);S2:從A1出發(fā)，按移動規(guī)則依次選定某個方向，如果達(dá)到的是(4,8)則轉(zhuǎn)向S3,否則繼續(xù)搜索下一個到達(dá)的頂點；S3:打印路徑。(i,j)(i+2,j+1)(i+1,j+2)(i-1,j+2)(i-2,j+1)搜索與回溯算法例5#include#includeusing namespace std;int a100100,t=0;/a路徑，t路徑總數(shù)int x4=2,1,-1,-2,

11、y4=1,2,2,1; /四種移動規(guī)則坐標(biāo)偏移量int print(int ii)t+;coutt: ;for (int i=1;i=ii-1;i+)coutai1,ai2;cout4,8endl;int search(int i)/搜索第i步for (int j=0;j=0/判斷馬不越界&ai-11+xj=0&ai-12+yj5：判斷效益是否大于max，若大于max，則更新g及max逐級回溯step5,step4,step1，直至所有可能的選擇都被嘗試過J1J2J3J4J5A13111047B13101085C59774D151210115E1011884搜索與回溯算法例6#include#

12、includeusing namespace std;int data66=0,0,0,0,0,0,0,13,11,10,4,7,0,13,10,10,8,5,0,5,9,7,7,4,0,15,12,10,11,5,0,10,11,8,8,4;int max1=0,g10,f10;bool p6=0;int go(int,int); int main()go(1,0); /從第1個人，總效益為0開始for (int i=1;i=5;i+)coutchar(64+i):Jgisetw(3);/輸出安排情況coutendl;coutsupply:max1endl;/安排第step個人的工作，t是之

13、前已得的效益int go(int step,int t)for (int i=1;i=5;i+)if (!pi)/判斷第i項工作沒人選擇fstep=i;/第step個人，選第i項工作pi=1; /標(biāo)記第i項工作被人安排了t+=datastepi;/計算效益值if(stepmax1)/如果當(dāng)前效益最佳max1=t;/保存最佳效益值for (int j=1;j=5;j+)gj=fj; /保存方案/回溯，第setp人不安排i項工作t-=datastepi;/清除i項工作效益pi=0;/第i項工作未安排搜索與回溯算法例7選書學(xué)校放寒假時，信息學(xué)競賽輔導(dǎo)老師有A，B，C，D，E五本書，要分給參加培訓(xùn)的張

14、、王、劉、孫、李五位同學(xué)，每人只能選一本書。老師事先讓每個人將自己喜歡的書填寫在如下的表格中。然后根據(jù)他們填寫的表來分配書本，希望設(shè)計一個程序幫助老師求出所有可能的分配方案，使每個學(xué)生都滿意。ABCDE張YY王YYY劉YY孫Y李YY搜索與回溯算法例7【算法分析】可用窮舉法，先不考慮“每人都滿意”這一條件，這樣只?！懊咳诉x一本且只能選一本”這一條件。在這個條件下，可行解就是五本書的所有全排列，一共有5!=120種。然后在120種可行解中一一刪去不符合“每人都滿意”的解，留下的就是本題的解答。為了編程方便，設(shè)1，2，3，4，5分別表示這五本書。這五個數(shù)的一種全排列就是五本書的一種分發(fā)。例如5432

15、1就表示第5本書（即E）分給張，第4本書（即D）分給王，第1本書（即A）分給李。“喜愛書表”可以用二維數(shù)組來表示，1表示喜愛，0表示不喜愛。算法設(shè)計：S1：產(chǎn)生5個數(shù)字的一個全排列；S2：檢查是否符合“喜愛書表”的條件，如果符合就打印出來；S3：檢查是否所有的排列都產(chǎn)生了，如果沒有產(chǎn)生完，則返回S1；S4：結(jié)束。ABCDE張YY王YYY劉YY孫Y李YY搜索與回溯算法例7【算法分析】上述算法有可以改進(jìn)的地方。比如產(chǎn)生了一個全排列12345，從表中可以看出，第一本書不可能是1的，因為張只喜歡第3、4本書。這就是說，1一類的分法都不符合條件。由此想到，如果選定第一本書后，就立即檢查一下是否符合條件，

16、發(fā)現(xiàn)1是不符合的，后面的四個數(shù)字就不必選了，這樣就減少了運算量。換句話說，第一個數(shù)字只在3、4中選擇，這樣就可以減少3/5的運算量。同理，每選擇了一個數(shù)字后，就立即檢查是否符合條件。例如，第一個數(shù)選3，第二個數(shù)選4后，立即檢查，發(fā)現(xiàn)不符合條件，就應(yīng)另選第二個數(shù)。這樣就把34一類的分法在產(chǎn)生前就刪去了。又減少了一部分運算量。 ABCDE張YY王YYY劉YY孫Y李YY搜索與回溯算法例7#include#include#includeusing namespace std;int book6,c;bool flag6,like66=0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,

17、1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0,1;int print()c+;/方案數(shù)累加1cout answer c :n;for(int i=1;i=5;i+)cout i : /輸出方案char(64+booki)endl;int search(int i)/分配第i人的書 for(int j=1;j=5; j+)/共有5本書if (flagj&likeij)/j可選flagj=0;/標(biāo)記第j本書已選booki=j;/第i個人選中第j本if (i=5)/所有的人都分到書print();/輸出方案 else/還有人沒分配到書search(i+1);/分配下一個人f

18、lagj=1;/回溯，放回第j本書int main()for(int i=1;i=5;i+) flagi=1;search(1);/從第1個開始選書，遞歸。搜索與回溯算法例8跳馬問題。在5*5格的棋盤上，有一只中國象棋的馬，從(1,1)點出發(fā)，按日字跳馬，它可以朝8個方向跳，但不允許出界或跳到已跳過的格子上，要求跳遍整個棋盤。輸出前5個方案及總方案數(shù)。11621102520112415221721969127413143181385搜索與回溯算法例8#include#includeusing namespace std;int u8=1,2,2,1,-1,-2,-2,-1,/8個方向v8=-2

19、,-1,1,2,2,1,-1,-2;/x,y增量int a100100=0,/每一格的在第幾步走到num=0;/總方案數(shù)int print()/打印方案num+;/統(tǒng)計總方案if(num=5)/打印出前5種方案 for (int k=1;k=5;k+)/打印方案 for(int kk=1;kk=5;kk+)coutsetw(5)akkk; cout25)/已做完所有格子print();return 0;/打印方案for (k=0;k=7;k+)/嘗試往8個方向走x=i+uk;y=j+vk;/往k方向走的新坐標(biāo)if(x=1&y=1&(!axy)/如果新坐標(biāo)可以走axy=n;/第n步走到(x,y)

20、search(x,y,n+1);/從(x,y)搜n+1步走法axy=0;/回溯，第n步不走(x,y)int main() a11=1;/第1步在(1,1)search(1,1,2);/從(1,1)開始搜第2步走法coutnumendl;/輸出總方案(共304)搜索與回溯算法例9數(shù)的劃分(Noip2001)將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。1,1,51,5,15,1,1問有多少種不同的分法?！据斎敫袷健縩，k (6n=200，2=k=6)【輸出格式】一個整數(shù)，即不同的分法?！据斎霕永?3【輸出樣例】4四種分法為：

21、1,1,5；1,2,4;；1,3,3；2,2,3搜索與回溯算法例9【算法分析1回溯】考慮采用回溯法對k個數(shù)的值逐一進(jìn)行枚舉，當(dāng)k個數(shù)的和等于n，找到了一個解。以n=7，k=3為例，初步判斷每個數(shù)的范圍為15，先考慮怎么枚舉出由15組成的3個數(shù)組合：1 1 12 1 13 1 14 1 15 1 11 1 22 1 23 1 24 1 25 1 21 1 32 1 33 1 34 1 35 1 31 1 4 2 1 43 1 44 1 45 1 41 1 52 1 53 1 54 1 55 1 51 2 12 2 13 2 14 2 15 2 11 2 22 2 23 2 24 2 25 2 2

22、1 5 32 5 33 5 34 5 35 5 31 5 42 5 43 5 44 5 45 5 41 5 52 5 53 5 54 5 55 5 5觀察上面的列表，結(jié)合我們的思維習(xí)慣，我們一般的枚舉方法是：從每個數(shù)都是最小數(shù)的組合1 1 1開始最后一個數(shù)逐漸加1，依次枚舉出1 1 2，1 1 3，直到加到6(超出最大限制)，轉(zhuǎn)倒數(shù)第二個數(shù)加1，最后一個數(shù)置為最?。? 2 1，轉(zhuǎn)，若倒數(shù)第二個數(shù)加到6(超出最大限制)，轉(zhuǎn)倒數(shù)第三個數(shù)加1，其后的數(shù)全置為最?。? 1 1，轉(zhuǎn)，若倒數(shù)第三個數(shù)加到6(超出最大限制)，結(jié)束搜索與回溯算法例9編程實現(xiàn)，枚舉k個數(shù)的組合，假設(shè)每個數(shù)的范圍為1Ms1.k存儲

23、第1.k個數(shù)，i表示正在對第幾個數(shù)進(jìn)行操作s1=0;/初始化i=1;while(i)/若i=0，說明第一位已超過極限，結(jié)束si+;/第i個數(shù)加1if (si=m) /當(dāng)前數(shù)未超過極限值if (i=k) /如果加1的是最后一個數(shù)，此時已產(chǎn)生一個新的組合根據(jù)需要，對新的組合進(jìn)行相應(yīng)操作;else/如果加1的不是最后一個數(shù)，則還需將其后的數(shù)置為最小數(shù)i+;/i指向下一個數(shù)，下一個循環(huán)將對si加1si=0;/在下一個循環(huán)加1后即成為最小數(shù)else i-; /如果當(dāng)前數(shù)超過極限，在下一個循環(huán)中將對前一個數(shù)加1搜索與回溯算法例9本題指出，數(shù)字相同但順序不同的組合視為同一個組合，而用前面的方法枚舉出的組合是

24、有重復(fù)的，不能滿足本題的要求。那么，怎樣才不會產(chǎn)生重復(fù)的組合呢？只要保證每次產(chǎn)生的新組合都是不下降序列（后面的數(shù)不小于前面的數(shù)）即可避免重復(fù)，即在枚舉組合中的每一數(shù)時，其最小值必須與前一個數(shù)相等，而不一定是1了。s1=0;/初始化i=1;while(i)/若i=0，說明第一位已超過極限，結(jié)束si+;/第i個數(shù)加1if (si=m) /當(dāng)前數(shù)未超過極限值if (i=k) /如果加1的是最后一個數(shù)，此時已產(chǎn)生一個新的組合根據(jù)需要，對新的組合進(jìn)行相應(yīng)操作;else/如果加1的不是最后一個數(shù)，則還需將其后的數(shù)置為最小數(shù)i+;/i指向下一個數(shù)，下一個循環(huán)將對si加1si=si-1-1;/在下一個循環(huán)加1

25、后即等于前一個數(shù)，保證了數(shù)值的不下降else i-; /如果當(dāng)前數(shù)超過極限，在下一個循環(huán)中將對前一個數(shù)加1搜索與回溯算法例9#includeusing namespace std;int n,i,j,k,sum,total;int s201;int main()cinnk;total=0;s1=0; i=1;while(i)si+;if(si=n-k+1)if (i=k)sum=0;for(j=1;j=k;j+) sum+=sj;if(n=sum) total+;else i+; si=si-1-1; else i-;couttotal;return 0;共有k個數(shù)，每個數(shù)大概有n種可能選擇，

26、所以算法的時間復(fù)雜度為O(nk)題目的數(shù)據(jù)規(guī)模為(6n=200，2=k=6)，在最壞的情況下將會超時搜索與回溯算法例9搜索與回溯算法例9#includeusing namespace std;int n,k;int f(int a,int b,int c)int g=0,i;if (b=1)/遞歸邊界，只劃分1份g=1;elsefor (i=c;i n k;coutf(n,k,1);return 0;時間復(fù)雜度：由于在搜索每一位數(shù)字的數(shù)值時做到了保證有解沒有重復(fù)，整個搜索過程沒有無用或重復(fù)的搜索分支，因此時間復(fù)雜度跟本題的答案是同一個數(shù)量級別。答案的數(shù)量級別估算如下：1、不排除重復(fù)，把n分為k

27、份，有C(n-1,k-1)種分法2、n和k的數(shù)字越大，其中重復(fù)的比例越接近于A(k,k)所以估計本題的時間復(fù)雜度為O(C(n-1,k-1)/k!)當(dāng)n=200，k=6時，時間復(fù)雜度為106搜索與回溯算法例9【算法分析3動態(tài)循環(huán)枚舉】回到第一種思路，枚舉出所有組合，然后逐一判斷組合是否滿足條件。在數(shù)據(jù)規(guī)模較大時，將因為組合數(shù)量很大而超時。事實上，絕大部分的組合是不滿足條件的，如果能減少或不枚舉不滿足條件的組合，那么將極大地節(jié)省運行時間，這在搜索中稱為剪枝。以n=7，k=3為例：第1個數(shù)的枚舉范圍為12第2個數(shù)的枚舉范圍根據(jù)第1個數(shù)動態(tài)調(diào)整1 ：剩余6，第2個數(shù)的枚舉范圍為132 ：剩余5，第2個

28、數(shù)的枚舉范圍為22第3個數(shù)即最后1個數(shù)必須等于剩余的數(shù)，不需枚舉假設(shè)在枚舉第dep個數(shù)時，還剩余rest，第det-1個數(shù)為last，若depk，則第i個數(shù)的枚舉范圍是lastrest/(k-dep+1)若dep=k，則第i個數(shù)等于rest，得到一個滿足條件的組合搜索與回溯算法例9#includeusing namespace std;int n,k,total;void select(int dep,int rest,int last)int i;if (dep=k)/最后1個數(shù)只能等于rest，不需枚舉，得到一個解total+;else for (i=last;ink;total=0;select(1,n,1);/從第一個數(shù)開始枚舉couttotal;return 0; 時間復(fù)雜度參照上一個解法上機(jī)練習(xí)1、全排列問題：輸出自然數(shù)1到n所有不重復(fù)的排列，即n的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。2、組合的輸出：排列與組合是常用的數(shù)學(xué)方法，其中組合就是從n個元素中抽出r個元素(不分順序且rn)，我們可以簡單地將n個元素理解為自然數(shù)1，2，n，從中任取r個數(shù)?，F(xiàn)要求你用遞歸的方法輸出所有組合。3、N皇后問題：在N*N的棋盤上放置N個皇后（n=10）而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解所有的