B5-搜索與回溯算法

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

2、個(gè)數(shù)的和是一個(gè)素?cái)?shù)。【算法分析】這是一道回溯的題目。從1開(kāi)始，每個(gè)空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個(gè)素?cái)?shù)。第20個(gè)數(shù)還要判斷和第1個(gè)數(shù)的和是否素?cái)?shù)?！舅惴鞒獭?、數(shù)據(jù)初始化；2、遞歸填數(shù)：判斷第i個(gè)數(shù)填入是否合法；A、合法：填數(shù)；判斷是否到達(dá)目標(biāo)（20個(gè)已填完）：是，打印結(jié)果；不是，填下一個(gè)數(shù)；B、不合法：選擇下一種可能；有合法的數(shù)jai:=j沒(méi)有合法的數(shù)a1a2ai-1a20aiai+1ai-1尋找下一個(gè)合法的數(shù)ai+1從1開(kāi)始尋找合法的數(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)/判斷素?cái)?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)/回溯過(guò)程int i;for(i=1;i=N;i+)/有N個(gè)數(shù)可選if(!bi)&(t=1|pd(at-1,i)/判斷該數(shù)是否可用及與前一個(gè)數(shù)是否構(gòu)成素?cái)?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個(gè)整數(shù)的集合1,2,n，從中取出任意r個(gè)數(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)/回溯過(guò)程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ù)的拆分任何一個(gè)大于1的自然數(shù)n，總可以拆分成若干個(gè)小于n的自然數(shù)之和。根據(jù)n的值，輸出拆分的方法總數(shù)。當(dāng)n=7時(shí)，共有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/回溯過(guò)程，s為待拆分的數(shù)，t表示第幾個(gè)拆分?jǐn)?shù)in

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

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

9、12345678對(duì)角線(xiàn)2對(duì)角線(xiàn)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個(gè)(行)皇后int j;for (j=1;j2,1-3,3-1,4-3,5-2,7-4,80123456784321搜索與回溯算法例5【算法分析】馬最多有

10、四個(gè)方向，若原來(lái)的橫坐標(biāo)為j、縱坐標(biāo)為i,則四個(gè)方向的移動(dòng)可表示為：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ā)，按移動(dòng)規(guī)則依次選定某個(gè)方向，如果達(dá)到的是(4,8)則轉(zhuǎn)向S3,否則繼續(xù)搜索下一個(gè)到達(dá)的頂點(diǎn)；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; /四種移動(dòng)規(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逐級(jí)回溯step5,step4,step1，直至所有可能的選擇都被嘗試過(guò)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個(gè)人，總效益為0開(kāi)始for (int i=1;i=5;i+)coutchar(64+i):Jgisetw(3);/輸出安排情況coutendl;coutsupply:max1endl;/安排第step個(gè)人的工作，t是之

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

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

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

16、發(fā)現(xiàn)1是不符合的，后面的四個(gè)數(shù)字就不必選了，這樣就減少了運(yùn)算量。換句話(huà)說(shuō)，第一個(gè)數(shù)字只在3、4中選擇，這樣就可以減少3/5的運(yùn)算量。同理，每選擇了一個(gè)數(shù)字后，就立即檢查是否符合條件。例如，第一個(gè)數(shù)選3，第二個(gè)數(shù)選4后，立即檢查，發(fā)現(xiàn)不符合條件，就應(yīng)另選第二個(gè)數(shù)。這樣就把34一類(lèi)的分法在產(chǎn)生前就刪去了。又減少了一部分運(yù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人的書(shū) for(int j=1;j=5; j+)/共有5本書(shū)if (flagj&likeij)/j可選flagj=0;/標(biāo)記第j本書(shū)已選booki=j;/第i個(gè)人選中第j本if (i=5)/所有的人都分到書(shū)print();/輸出方案 else/還有人沒(méi)分配到書(shū)search(i+1);/分配下一個(gè)人f

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

19、,-1,1,2,2,1,-1,-2;/x,y增量int a100100=0,/每一格的在第幾步走到num=0;/總方案數(shù)int print()/打印方案num+;/統(tǒng)計(jì)總方案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個(gè)方向走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)開(kāi)始搜第2步走法coutnumendl;/輸出總方案(共304)搜索與回溯算法例9數(shù)的劃分(Noip2001)將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。1,1,51,5,15,1,1問(wèn)有多少種不同的分法。【輸入格式】n，k (6n=200，2=k=6)【輸出格式】一個(gè)整數(shù)，即不同的分法?！据斎霕永?3【輸出樣例】4四種分法為：

21、1,1,5；1,2,4;；1,3,3；2,2,3搜索與回溯算法例9【算法分析1回溯】考慮采用回溯法對(duì)k個(gè)數(shù)的值逐一進(jìn)行枚舉，當(dāng)k個(gè)數(shù)的和等于n，找到了一個(gè)解。以n=7，k=3為例，初步判斷每個(gè)數(shù)的范圍為15，先考慮怎么枚舉出由15組成的3個(gè)數(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í)慣，我們一般的枚舉方法是：從每個(gè)數(shù)都是最小數(shù)的組合1 1 1開(kāi)始最后一個(gè)數(shù)逐漸加1，依次枚舉出1 1 2，1 1 3，直到加到6(超出最大限制)，轉(zhuǎn)倒數(shù)第二個(gè)數(shù)加1，最后一個(gè)數(shù)置為最?。? 2 1，轉(zhuǎn)，若倒數(shù)第二個(gè)數(shù)加到6(超出最大限制)，轉(zhuǎn)倒數(shù)第三個(gè)數(shù)加1，其后的數(shù)全置為最?。? 1 1，轉(zhuǎn)，若倒數(shù)第三個(gè)數(shù)加到6(超出最大限制)，結(jié)束搜索與回溯算法例9編程實(shí)現(xiàn)，枚舉k個(gè)數(shù)的組合，假設(shè)每個(gè)數(shù)的范圍為1Ms1.k存儲(chǔ)

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

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

25、后即等于前一個(gè)數(shù)，保證了數(shù)值的不下降else i-; /如果當(dāng)前數(shù)超過(guò)極限，在下一個(gè)循環(huán)中將對(duì)前一個(gè)數(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個(gè)數(shù)，每個(gè)數(shù)大概有n種可能選擇，

26、所以算法的時(shí)間復(fù)雜度為O(nk)題目的數(shù)據(jù)規(guī)模為(6n=200，2=k=6)，在最壞的情況下將會(huì)超時(shí)搜索與回溯算法例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;時(shí)間復(fù)雜度：由于在搜索每一位數(shù)字的數(shù)值時(shí)做到了保證有解沒(méi)有重復(fù)，整個(gè)搜索過(guò)程沒(méi)有無(wú)用或重復(fù)的搜索分支，因此時(shí)間復(fù)雜度跟本題的答案是同一個(gè)數(shù)量級(jí)別。答案的數(shù)量級(jí)別估算如下：1、不排除重復(fù)，把n分為k

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

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