C語言回溯算法課件

第五講回溯算法

從問題的某一種可能出發(fā),搜索從這種情況出發(fā)所能達到的所有可能,當這一條路走到“盡頭”而沒達到目的地的時候,再倒回上一個出發(fā)點,從另一個可能出發(fā),繼續(xù)搜索.這種不斷“

倒回一步"尋找解的方法,稱作"回溯法".

回溯即是較簡單、較常用的搜索策略,實質(zhì)就是一種搜索策略.AB12345678910從A到B的路線:A---4---6---B如:找一條從A到B的路線[問題描述]

學校放暑假時，信息學輔導教師有n本書要分給參加培訓的n個學生。如：A，B，C，D，E共5本書要分給參加培訓的張、劉、王、李、孫5位學生，每人只能選1本。教師事先讓每個人將自己喜愛的書填寫在如下的表中，然后根據(jù)他們填寫的表來分配書本，希望設計一個程序幫助教師求出可能的分配方案，使每個學生都滿意。ABCDE張YY王YY劉YY孫Y李YY引例、借書問題分析:a:array[1..maxn,1..maxn]of0..1;{a[i，j]=1：第i個人喜歡第j本書，0表示不喜歡}b:array[1..maxn]ofinteger;{記錄分配方案:b[i]是第i個人借第b[i]本書}book:array[1..maxn]ofboolean;{book[[i]:能否可以借第i本書,是否他人已借此書初始:true,一旦有人借了:就改為:false}算法設計:proceduretry(i:integer);{要搜索第i個人可以借的書b[i]，說明前i-1個人已經(jīng)借了書}

varj:integer;beginifi=n+1then輸出結(jié)果；

forj:=1tondo{搜索人i能夠可以結(jié)的書}if第i個人可以借第j本書thenbegin

記錄下b[i]=j;

標記第j本數(shù)已被借：book[j]=false;try(i+1);

刪除書的被借標志;book[j]=true；別人可以借

end;end;constmaxn=10;vara:array[1..maxn,1..maxn]of0..1;b:array[1..maxn]ofinteger;book:array[1..maxn]ofboolean;n:integer;

procedureinit;{讀入數(shù)據(jù)}vari,j:integer;beginfillchar(b,sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(a[i,j]);end;procedureprint;vari:integer;beginfori:=1ton-1dowrite(b[i],'');writeln(B[N]);end;回溯算法：假設問題的解的形式為（x1,x2,x3,……..xn）,x1∈S1,x2∈S2,xn∈Sn

基本思路：若已有滿足約束條件的部分解，不妨設為（x1,x2,x3,……xi），I<n,

則添加屬于s(i+1)一個x(i+1)，檢查(x1,x2,……,xi,x(i+1))是否滿足條件，滿足了就繼續(xù)添加一個x(i+2)∈s(i+2)，若所有的x(i+1)∈s(i+1)都不能得到部分解，即找不到一個x(i+1)∈s(i+1)滿足條件,就去掉當前xi，回溯到(xi,x2,……x(i-1))，添加那些未考察過的xi∈Si，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。[問題描述]

在n×n的國際象棋盤上，放置n個皇后，使任何一個皇后都不能吃掉另一個,要使任何一個皇后都不能吃掉另一個，需滿足的條件是：同一行、同一列、同一對角線上只能有一個皇后。求放置方法.

如:n=4時,有以下2種放置方法.********一N皇后問題輸出：241331422、放置第k(1<=k<=n)個皇后的遞歸算法：

proceduretry(k);{搜索第k個皇后所在的列x[k]=？,前k-1個已放好,即已求得x[1]…x[k-1]}vari:integer;beginifk=n+1thenprint（輸出放置方案：數(shù)組x）;fori:=1tondo{搜索第k個皇后所在的列j}if第k個皇后能夠放置在第i列

thenbegin

放置第k個皇后在第j列（x[k]=i）；

try（k+1）；

end;end;3、怎樣判斷：第k個皇后能否放置在第i列：functionplace(k,i:integer):boolean;{第k個皇后能否放在第i列}varj:integer;beginforj:=1TOK-1doif(x[j]=i)or(abs(x[j]-i)=abs(j-k))thenbeginplace:=false;exitend;place:=true;end;4、輸出解：

procedureprint;varj:integer;begincount:=count+1;write('answer',count,':');forj:=1ton-1dowrite(x[j],'');writeln(x[n]);end;主程序：try（1）方法二：方法一的缺點：每次調(diào)用函數(shù)place（I,j）判斷第i個皇后能否放在j列時：有一個for循環(huán)判斷，顯然浪費時間。functionplace(k,i:integer):boolean;{第k個皇后能否放在第i列}varj:integer;beginforj:=1TOK-1doif(x[j]=i)or(abs(x[j]-i)=abs(j-k))thenbeginplace:=false;exitend;place:=true;end;遞歸算法：proceduretry(i:integer);varj:integer;beginifi=n+1thenprintelseforj:=1tondoifa[j]andb[i+j]andc[i-j]thenbeginx[i]:=j;a[j]:=false;{列控制標志}b[i+j]:=false;{左上右下方斜線控制標志}c[i-j]:=false;{左下右上方斜線控制標志}try(i+1);{如果不能遞歸進行，既a[j]andb[i+j]andc[i-j]=false：無法放置i+1個皇后，說明當前皇后i放置不正確，要回溯，消除標志}a[j]:=true;b[i+j]:=true;c[i-j]:=trueend;end;2、無重復元素的全排列輸入n（<=10）個不同的小些字母，輸出n個字符的全部排列。樣例：輸入：abc輸出：1:abc2:acb3:bac4:bca5:cab6:cbaproceduretry(i:integer);{開始搜第i個字符a[i]}varj:integer;beginifi=n+1thenprint;{得到一種排列輸出數(shù)組a}forj:=1tondo{找第i個字符}ifcan[j]=0then{沒進序列}begina[i]:=s[j];{加入到排序序列}can[j]:=1;{標記已用了}try(i+1);{找第i+1個字符}can[j]:=0;{恢復標記，以便繼續(xù)使用}end;end;Begin{主程序}readln(s);n:=length(s);fillchar(can,sizeof(can),0);count:=0;try(1);{開始生成第一個字符}end.{有重復元素的排列方法一}vars:string;a:array[1..10]ofchar;{記錄生成排列}num:array[‘a(chǎn)’..‘z’]ofinteger;{相應字符出現(xiàn)的次數(shù)}n,i,count:integer;procedureprint;{讀入字符}vari:integer;begininc(count);write(count,':');fori:=1tondowrite(a[i]);writeln;end;分析：對于某個字符，不能僅僅使用標志，即使用過了，只要還有就可以繼續(xù)使用，所以出現(xiàn)的字符按類存儲，同時記錄個數(shù)。proceduretry(i:integer);{搜索生成第i個字符}varj:char;beginifi=n+1thenprint;forj:='a'to'z'doifnum[j]>0then{只要還有沒拿的}begina[i]:=j;{記下當前字符}dec(num[j]);{當前字符數(shù)量減少一個}try(i+1);{找下一個}inc(num[j]);{恢復原來數(shù)量}end;end;Begin{主程序}readln(s);n:=length(s);fori:=1tondoinc(num[s[i]]);{統(tǒng)計出現(xiàn)的字符個數(shù)}count:=0;try(1);{找第一個}end.varn,k,i,count:integer;a:array[1..100]ofinteger;{記錄分解項}Procedureprint(x);{輸出分解方案}

vari:integer;begininc(count);write(count,':',n,'=');fori:=1tokdowrite(a[i],‘+’);writeln(x);{輸出分解方案}End;proceduretry(x:integer);{要分解x，前面已有k項}vari,j:integer;beginprint(x)；

forj:=a[k]toxdiv2do{分解x=j+（x-j）：保證非遞減}if(j>=a[k])and(x-j>=j)thenbegininc(k);a[k]:=j;try(x-j);dec(k);end;end;beginreadln(n);count:=0;fori:=1tondiv2do{先分解成i+（n-i）兩項和}begink:=1;{分解項}a[1]:=i;try(n-i);end;end.分解（二）輸入自然數(shù)n和m（n，m<100），輸出所有分解，分解后的每一項都不超大于m的。不能重復。如：4=1+1+2；4=1+2+1;4=2+1+1屬于一種分解形式。如：輸入：74輸出：1:7=1+1+1+42:7=1+1+1+1+33:7=1+1+1+1+1+24:7=1+1+1+1+1+1+15:7=1+1+1+2+26:7=1+1+2+37:7=1+2+48:7=1+2+2+29:7=1+3+310:7=2+2+311:7=3+4beginreadln(n);readln(m);count:=0;fori:=1tondiv2dobegink:=1;a[1]:=i;try(n-i);end;end.varn,m,k,i,count:integer;a:array[1..100]ofinteger;procedureprint(i,x:integer);varj:integer;begininc(count);write(count,':',n,'=');fori:=1tokdowrite(a[i],'+');writeln(x);end;proceduretry(x:integer);{x是第k+1項}vari,j:integer;beginifx<=mthenprint(k,x);forj:=a[k]toxdiv2doif(j>=a[k])and(x-j>=j)thenbegininc(k);a[k]:=j;try(x-j);dec(k);end;end;分解（三）輸入自然數(shù)n和m（n，m<100），輸出所有分解項數(shù)不超過m的所有形式。不能重復。如：4=1+1+2；4=1+2+1;4=2+1+1屬于一種分解形式。如：輸入：74輸出：1:7=1+62:7=1+1+53:7=1+1+1+44:7=1+1+2+35:7=1+2+46:7=1+2+2+27:7=1+3+38:7=2+59:7=2+2+310:7=3+4varn,m,k,i,count:integer;a:array[1..100]ofinteger;procedureprint(i,x:integer);varj:integer;begininc(count);write(count,':',n,'=');fori:=1tokdowrite(a[i],'+');writeln(x);end;proceduretry(x:integer);{x是第k+1項}vari,j:integer;beginifk<=m-1thenprint(k,x);forj:=a[k]toxdiv2doif(j>=a[k])and(x-j>=j)thenbegininc(k);a[k]:=j;try(x-j);dec(k);end;end;beginreadln(n);readln(m);count:=0;fori:=1tondiv2dobegink:=1;a[1]:=i;try(n-i);end;end.算法的缺點？改進優(yōu)化？ifk>=mthenexit;{剪枝優(yōu)化}5、騎士的游歷設有下圖所示的一個棋盤，在棋盤上的A(0,0)點有一個中國象棋馬，并約定馬走的規(guī)則：

1、馬只向右走；

2、馬走“日“字。找出所有從A到B的路徑。輸入：B的坐標n，m（<=15）。輸出：所有走法。如：輸入：84輸出：（0,0)(21)(40)(52)(60)(72)(84)1112345671231分析：1、馬跳的方向：

x:array[1..4,1..2]ofinteger=((1,-2),(2,-1),(2,1),(1,2));4個方向橫向和縱向的增量。2、記錄馬經(jīng)過的位置坐標

a:array[1..16,1..2]ofinteger;

第i步所在的位置，1：橫坐標

2：縱坐標3、馬的當前位置：（a[I,1],a[I,2]）下一個位置可能是：(a[I,1]+x[j,1],a[I,2]+x[j,2])1<=j<=44、目標：a[I,1]=n;a[I,2]=m;constmaxx=15;maxy=15;x:array[1..4,1..2]ofinteger=((1,-2),(2,-1),(2,1),(1,2));{4個方向}varn,m,t:integer;a:array[1..maxx+1,1..2]ofinteger;{記錄走的路徑坐標}procedureprint(i:integer);varj:integer;begininc(t);write(t,':');forj:=1toidowrite('(',a[j,1],'',a[j,2],')');writeln;end;proceduretry(i:integer);{搜索到當前第i個點}varj:integer;beginif(a[i,1]=n)and(a[i,2]=m)thenprint(i);forj:=1to4doif(a[i,1]+x[j,1]>=0)and(a[i,1]+x[j,1]<=n)and(a[i,2]+x[j,2]>=0)and(a[i,2]+x[j,2]<=m){判界}thenbegina[i+1,1]:=a[i,1]+x[j,1];a[i+1,2]:=a[i,2]+x[j,2];try(i+1);end;end;beginassign(output,'house1.out');rewrite(output);readln(n,m);t:=0;a[1,1]:=0;{起始位置作為第1個點}a[1,2]:=0;try(1);close(output);end.求最少步到達B點。Best:最短路線，a：臨時得到的一個路線。Min：最少步。proceduretry(i:integer);{搜索到當前第i個點}varj:integer;beginif((a[i,1]=n)and(a[i,2]=m))and(i<min)thenbeginmin:=i;best:=a;exit;end;{記下當前最短路徑和最少步數(shù)}if((a[i,1]<>n)or(a[i,2]<>m))and(i>=min)thenexit;{剪枝優(yōu)化}forj:=1to4doif(a[i,1]+x[j,1]>=0)and(a[i,1]+x[j,1]<=n)and(a[i,2]+x[j,2]>=0)and(a[i,2]+x[j,2]<=m)thenbegina[i+1,1]:=a[i,1]+x[j,1];a[i+1,2]:=a[i,2]+x[j,2];try(i+1);end;end;19196、迷宮問題

設有一個N*N方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中分別放有0和1，0表示可通，1表示不能，迷宮走的規(guī)則如下圖所示：即從某點開始，有八個方向可走，前進方格中數(shù)字為0時表示可通過，為1時表示不可通過，要另找路徑。輸入例子：（從文件中讀取數(shù)據(jù)）80001101010110110010010010011010101000110011111010011101111000000入口：（1，1）；出口：（1，8）輸出要求：找出一條從入口（左上角）到出口（又上角）的路徑(不能重復)。

(1,1)->(2,2)->(3,3)->(3,4)->(4,5)->(3,6)->(3,7)->(2,8)->(1,8)分析:a:array[0..maxn+1,0..maxn+1]of0..1;{記錄迷宮坐標}b:array[0..maxn*maxn,1..2]ofinteger;{記錄路徑}dx,dy:array[1..8]ofinteger;{方向位移}8個方向的位移:

dx[1]:=0;

dy[1]:=-1;dx[2]:=1;

dy[2]:=-1;dx[3]:=1;

dy[3]:=0;dx[4]:=1;

dy[4]:=1;dx[5]:=0;

dy[5]:=1;dx[6]:=-1;

dy[6]:=1;dx[7]:=-1;

dy[7]:=0;dx[8]:=-1;

dy[8]:=-1;constmaxn=20;{遞歸算法}dx:array[1..8]ofinteger=(0,1,1,1,0,-1,-1,-1);dy:array[1..8]ofinteger=(-1,-1,0,1,1,1,0,-1);vara:array[0..maxn+1,0..maxn+1]of0..1;b:array[0..maxn*maxn,1..2]ofinteger;n,m,k,i,j,x,y:integer;sum:longint;procedureinit;beginfori:=0tomaxn+1doforj:=0tomaxn+1doa[i,j]:=1;readln(n);fori:=1tondoforj:=1tondoread(a[i,j]);End；procedureprint(i:integer);varj:integer;begininc(sum);write(sum,':');forj:=1toidowrite('(',b[j,1],'',b[j,2],')');writeln;end;proceduretry(i:integer);vark:integer;beginif(b[i,1]=1)and(b[i,2]=n)thenprint(i);fork:=1to8dobeginifa[b[i,1]+dx[k],b[i,2]+dy[k]]=0thenbeginb[i+1,1]:=b[i,1]+dx[k];b[i+1,2]:=b[i,2]+dy[k];a[b[i+1,1],b[i+1,2]]:=1;try(i+1);a[b[i+1,1],b[i+1,2]]:=0;end;end;end;Begin{main}init;sum:=0;b[1,1]:=1;b[1,2]:=1;a[1,1]:=1;try(1);ifsum=0thenwriteln('noanswer');end.7、細胞

一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。輸入：整數(shù)m,n(m行，n列)

矩陣輸出：細胞的個數(shù)。樣例:輸入:410

0234500067

1034560500

2045600671

0000000089輸出:40234500067

1034560500

2045600671

89

programxibao;{細胞個數(shù)}constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,1,0,-1);vars:string;pic:array[1..50,1..80]of0..1;m,n,i,j,num:integer;h:array[1..4000,1..2]ofbyte;{隊列：存細胞的坐標}procedureinit;beginfillchar(pic,sizeof(pic),0);num:=0;fillchar(h,sizeof(h),0);assign(input,'b5.in');reset(input);readln(m,n);fori:=1tomdobeginreadln(s);forj:=1tondoifs[j]='0'thenpic[i,j]:=0elsepic[i,j]:=1;end;close(input);end;proceduretry(i,j:integer);vark,t,w,x,y:integer;beginpic[i,j]:=0;fork:=1to4do{沿細胞的上下左右四個方向搜索細胞}beginx:=i+dx[k];y:=j+dy[k];if(x>=1)and(x<=m)and(y>=1)and(y<=n)and(pic[x,y]=1)thenbeginpic[x,y]:=0;try(x,y);end;{為細胞的入隊}end;end;Begin{主程序}init;fori:=1tomdoforj:=1tondoifpic[i,j]=1thenbegintry(i,j);{在矩陣中尋找細胞}inc(num);end;writeln(num);end.8、組合（一）無重復元素的組合輸入一串小些字母（無重復字母），從中取出k個字母，輸出組合情況。樣例：輸入：abcd3輸出：abcabdacdbcdvars:string;n,m:integer;a:array[1..10]ofchar;procedureprint;varj:integer;beginforj:=1tomdowrite(a[j]);writeln;end;proceduretry(i,k:integer);{搜索組合的第p個元素，x搜索位置}varj:integer;beginifi=m+1thenprint;forj:=ktondobegina[i]:=s[j];try(i+1,j+1);end;end;beginreadln(s);readln(m);n:=length(s);try(1,1);end.（二）、有重復元素的組合輸入一串小些字母（有重復字母），從中取出k個字母，輸出組合情況。樣例：輸入：aabbcc4輸出：1:aabb2:aabc3:aacc4:abbc5:abcc6:bbcc9、數(shù)字排列(li3.txt)在一個N*N的棋盤上（1<=n<=10),填入1,2,...,n*n共n*n個數(shù)，使得任意兩個相臨的數(shù)之合為素數(shù)

例如：

n=2時，有:

12

43

n=4

121112

161585

134914

67103分析：

逐行搜索1到n*n之間的數(shù)放在（i，j）處，依次判斷他與上方（i-1,j）的數(shù)和左邊(I,j-1)的數(shù)的和是否為素數(shù)，是就放(I,j)處，再放（I,j+1);如果不是素數(shù)，則繼續(xù)在1到n*n之間搜索合適的數(shù)能放在(I,j)處。constmaxn=100;vari,j,k,m,n,x,y,nn:integer;p:array[1..2*maxn*maxn]ofboolean;{素數(shù)表：p[i]=true:i是素數(shù)，p[i]=false:i不是素數(shù)}b:array[1..maxn,1..maxn]ofinteger;{坐標}used:array[1..maxn*maxn]ofboolean;{檢查是否該數(shù)是否用過}{篩選法創(chuàng)建素數(shù)表}procedureprime;vari,j,s:integer;beginfillchar(p,sizeof(p),true);p[1]:=false;fori:=2to3*ndiv2

do{依次搜索素數(shù)i并篩掉是i倍數(shù)的數(shù)}ifp[i]thenbeginj:=2*i;whilej<=2*n*ndobeginp[j]:=false;j:=j+i;end;end;end;判斷（x,y）位置能否放數(shù)值k的函數(shù)functionok(x,y,k:integer):boolean;beginok:=true;ifx>1thenifnot(p[b[x-1,y]+k])thenok:=false;ify>1thenifnot(p[b[x,y-1]+k])thenok:=false;end;proceduretry(x,y,dep:integer);{遞歸搜索（x,y）處放第dep

個數(shù)}vari:integer;beginifdep=n*n+1thenprint;{如果已放了n*n個數(shù)，得出一種方法}fori:=1ton*ndoifnot(used[i])andok(x,y,i)thenbeginb[x,y]:=i;used[i]:=true;ify=nthentry(x+1,1,dep+1){如果當前是最右邊一列，則轉(zhuǎn)到下一行首列}elsetry(x,y+1,dep+1);{繼續(xù)放當前行的下一列}used[i]:=false;{釋放標志}end;end;procedureprint;vari,j:integer;beginfori:=1tondobeginforj:=1tondowrite(b[i,j]:4);writeln;end;halt;end;主程序：beginreadln(n);prime;b[1,1]:=1;fori:=2ton*ndoused[i]:=false;used[1]:=true;try(1,2,2);writeln('NO');end.constmaxn=100;vara:array[1..maxn]ofinteger;n,m:integer;proceduretry(i:integer);varj:integer;beginifi>nthenbeginwrite('{');forj:=1tom-1dowrite(a[j],',');ifm>0thenwrite(a[m]);writeln('}');exit;end;try(i+1);inc(m);a[m]:=i;try(i+1);dec(m);end;beginread(n);m:=0;try(1);end.10、因式分解輸入自然數(shù)n（<109）,將n分解成一系列自然數(shù)乘積的形式：N=a1*a2*......*am，1<a1<=a2<=......<=am<n.輸出所有的分解方案及方案數(shù)目。樣例:輸入:12輸出:2*62*2*33*43varn,k,i,count:integer;a:array[1..100]ofinteger;procedureprint(x:integer);vari:integer;begininc(count);write(count,':',n,'=');fori:=1tokdowrite(a[i],'*');writeln(x);end;proceduretry(x:integer);varj:integer;beginprint(x);forj:=a[k]totrunc(sqrt(x))doif(xmodj=0)and(xdivj>=j)thenbegininc(k);a[k]:=j;try(xdivj);dec(k);end;end;beginreadln(n);count:=0;fori:=2totrunc(sqrt(n))doifnmodi=0thenbegink:=1;a[1]:=i;try(ndivi);end;end.1)構(gòu)造因子表proceduremakebiao;vari,p:longint;begink:=0;fori:=2totrunc(sqrt(n))doifnmodi=0thenbegininc(k);a[k]:=i;end;p:=2*k;ifa[k]*a[k]=nthendec(p);fori:=K+1topdoa[i]:=ndiva[p-i+1];{fori:=1topdowrite(a[i],'');writeln(p);}end;注意:注意n為完全平方數(shù)時:dec(p)N=12:時2346N=100時:245102025502)遞歸求解:proceduretry(j,n1,h:longint);{j:待搜索的因子表起點序號,即從a[j]到a[k]中開始搜索因數(shù)表中的因數(shù)