N皇后問題 回溯法

回溯

Backtracking回溯N皇后問題跳馬問題迷宮問題圖的著色問題0-1背包問題裝載問題批處理作業(yè)調度填數(shù)問題組合輸出問題算24點問題ACM應用學習要點掌握回溯的概念掌握經典問題的回溯解決方法掌握回溯與其它方法的異同有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ɑ厮菟惴ㄊ撬兴阉魉惴ㄖ凶顬榛镜囊环N算法,是一種能避免不必要搜索的窮舉式的搜索算法，其基本思想就是窮舉搜索。算法思想：采用了一種“走不通就掉頭”的思想。搜索時往往有多分支，按某一分支為新的出發(fā)點，繼續(xù)向下探索，當所有可能情況都探索過且都無法到達目標的時候，再回退到上一個出發(fā)點，繼續(xù)探索另一個可能情況，這種不斷回頭尋找目標的方法稱為“回溯法”?；厮莘ɑ厮菟惴ㄊ撬兴阉魉惴ㄖ凶顬榛镜囊环N算法,是一種能避免不必要搜索的窮舉式的搜索算法，其基本思想就是窮舉搜索。回溯法搜索的方式主要采用深度優(yōu)先搜索的方式回溯三要素：

1)解空間：該空包含問題的解

2)約束條件

3)狀態(tài)樹問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。n=3時的0-1背包問題用完全二叉樹表示的解空間生成問題狀態(tài)的基本方法擴展結點:一個正在產生兒子的結點稱為擴展結點活結點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結點死結點:一個所有兒子已經產生的結點稱做死結點深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產生了它的一個兒子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結點變成死結點之前，它一直是擴展結點回溯法：為了避免生成那些不可能產生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法回溯法的基本思想(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間。遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。voidbacktrack(intt){

if(t>n)output(x);

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。voiditerativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){

if(solution(t))output(x);

elset++;}}

elset--;}}在一個n*n的國際象棋棋盤上放置n個皇后，使得它們中任意2個之間都不互相“攻擊”，即任意2個皇后不可在同行、同列、同斜線上。輸出N，⑴求N皇后問題的一種放法；

⑵求N皇后問題的所有放法分析：

N=4時，右圖是一組解要素一：解空間一般想法：利用二維數(shù)組，用[i,j]確定一個皇后位置！

優(yōu)化：利用約束條件，只需一維數(shù)組即可！

x:array[1..n]ofinteger;x[i]：i表示第i行皇后

x[i]表示第i行上皇后放第幾列

x[3,1,4,2]N皇后問題要素二：約束條件不同行：數(shù)組x的下標保證不重復不同列：x[i]<>x[j](i<=I,j<=n；i<>j)不同對角線：abs(x[i]-x[j])<>abs(i-j)要素三：狀態(tài)樹將搜索過程中的每個狀態(tài)用樹的形式表示出來！畫出狀態(tài)樹對書寫程序有很大幫助！填到第K行時，就與前1~(K-1)行都進行比較FunctionPlace(k:integer):boolean;place:=true;forj←1tok-1doif|k-j|=|x[j]-x[k]|orx[j]=x[k]thenplace:=falseN皇后問題K=0K=1**************回溯**********回溯***********K=3K=2K=4****出解后可以繼續(xù)剛才的做法過程：進入新一行，該行上按順序逐個格子嘗試，直到能放為止（不沖突、不越界）算法描述：產生一種新放法沖突，繼續(xù)找，直到找到不沖突----不超范圍if不沖突thenk<nk+1 k=n一組解if沖突then回溯N皇后問題回溯部份：

即狀態(tài)恢復，使其恢復到進入該分支前的狀態(tài)，繼續(xù)新的分支

x[k]:=0;Dec(k);

程序結束條件：一組解：設標志，找到一解后更改標志，以標志做為結束循環(huán)的條件所有解：k=0程序實現(xiàn)：回溯算法可用非遞歸和遞歸兩種方法實現(xiàn)！判斷約束函數(shù)FunctionPlace(k:integer):boolean;place:=true;forj←1tok-1doif|k-j|=|x[j]-x[k]|orx[j]=x[k]thenplace:=falseN皇后問題Nqueens()

beginx[1]←0k←1

whilek>0dobegin

x[k]←x[k]+1

whilex[k]<=nand(notplace(k))dox[k]←x[k]+1

ifx[k]<=nthenifk=nthensum←sum+1

else

begink←k+1x[k]←0

end

elsek←k-1

end

end

非遞歸寫法：

ifk=nthenprint;flag←false算法描述：產生一種新放法沖突，繼續(xù)找，直到找到不沖突----不超范圍if不沖突thenk<nk+1 k=n一組解if沖突then回溯Flag←trueWhileflagdoN皇后問題proceduretry(k:byte);

vari:byte;

begin

fori:=1tondo {每層均有n種放法}

ifplace(k)then {尋找放置皇后的位置}

begin

x[k]:=i; {放置皇后)

ifk=nthenprint {８個皇后都放置好,輸出} {若只想找一組解，halt}

elsetry(k+1); {繼續(xù)遞歸放置下一個皇后}

end;

end;遞歸寫法：分析：狀態(tài)恢復（回溯）在什么地方實現(xiàn)？N皇后問題在n×m棋盤上有一中國象棋中的馬：馬走日字；馬只能往右走。請你找出一條可行路徑，使得馬可以從棋盤的左下角（1，1）走到右上角（n，m）。輸入：95輸出：(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)跳馬問題分析：按題意，馬每一步可以有4種走法！搜索過程：當馬一開始位于左下角的時候，根據(jù)規(guī)則，它只有兩條線路可以選擇（另外兩條超出棋盤的范圍），我們無法預知該走哪條，故任意選擇一條，到達A1。AA1A2當?shù)竭_A1點后，又有三條線路可以選擇，于是再任意選擇一條，到達B1。從B1再出發(fā)，又有兩條線路可以選擇，先選一條，到達C1。AA1A2B1B2B3C1C2跳馬問題AA1A2B1B2B3C1C2D1D2D3E14.從C1出發(fā)，可以有三條路徑，選擇D1。但到了D1以后，我們無路可走且D1也不是最終目標點，因此，選擇D1是錯誤的，我們退回C1重新選擇D2。同樣D2也是錯誤的。再回到C1選擇D3。D3只可以到E1，但E1也是錯誤的。返回D3后，沒有其他選擇，說明D3也是錯誤的，再回到C1。此時C1不再有其他選擇，故C1也是錯誤的，退回B1，選擇C2進行嘗試。AA1A2B1B2B3C2E2BD4E1F15.從C2出發(fā)，有四條路徑可以選擇，選擇D4，從D4出發(fā)又有兩條路徑，選擇E1錯誤，返回D4選擇E2，從E2出發(fā)有兩條路徑，先選擇F1錯誤，返回E2選擇B，而B恰好是我們要到達的目標點，至此，一條路徑查找成功。跳馬問題①②③④從上面的分析我們可以得知：在無法確定走哪條線路的時候，任選一條線路進行嘗試；為方便路徑表示，對馬可以走到的四個點（方向）都編上號；當從某點出發(fā)，所有可能到達的點都不能到達終點時，說明此點是一個死節(jié)點，必須回溯到上一個點，并重新選擇一條新的線路進行嘗試。解空間:

為了描述路徑，我們最直接的方法就是記錄路徑上所有點的坐標。優(yōu)化：每一個方向上兩個坐標和原位置對應關系若馬所處的位置為(x,y)，則其下一步可以到達的四個位置分別是(x+1,y-2)，(x+2,y-1)，(x+2,y+1)，(x+1,y+2)。增量數(shù)組：

dx=(1,2,2,1)

dy=(-2,-1,1,2)方向t，下一步的位置就是(x+dx[t],y+dy[t])。xypath:array[1..m]ofinteger;其中，path[i]：表示第i個節(jié)點所走的方向跳馬問題約束條件：不越界：(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)

狀態(tài)樹：0①②③④⑤⑤⑤⑥④Path[1]:=3Path[2]:=2Path[3]:=3Path[4]:=234Path[5]:=14①②③④④⑤⑤⑤⑤⑥⑥⑦⑦①②③④算法描述：產生一種新走法越界，繼續(xù)用新走法，直到找到一種走法不越界----不超過4種走法if不越界thenk<nk+1 k=n一組解if越界then回溯跳馬問題Horse()

beginpath[1]←0，k←1，x←1，y←1

while(x<>m)and(y<>n)dobegin

path[k]←path[k]+1

while(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)

and (path[k]<=4)dopath[k]←path[k]+1

ifpath[k]<=4then {在4種走法中找到不越界的走法}beginx←x+dx[i]，y←y+dy[i]if(x<>m)and(y<>n)thenprint

else

begink←k+1path[k]←0

end

end

elsepath[k]←0，k←k-1

end

end

跳馬問題（非遞歸）跳馬問題跳馬問題（遞歸）跳馬問題proceduresearch(k:integer);//遞歸查找beginfori:=1to4do//依次嘗試四個方向

if(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)then//在棋盤上

beginpath[k]:=i;//記錄下當前方向

x:=x+dx[i];y:=y+dy[i];//修改擴展節(jié)點坐標

if(x=n)and(y=m)then//是否是目標點

beginoutput(k);halt;//是目標點，輸出結果并終止程序

endelsesearch(k+1);//不是目標點，繼續(xù)嘗試下一步

//擴展出的點是死點，回溯

x:=x-dx[i];y:=y-dy[i];//恢復擴展節(jié)點坐標，狀態(tài)恢復

end;end;Beginread(n,m);x:=1;y:=1;search(1);End.思考:1.在本例中，我們只要求輸出一條可行路徑，如果我們需要輸出所有的可行路徑，怎樣改動此程序呢？<遞歸><非遞歸>2.如果我們把問題改成“在n×m的棋盤上有一騎士，開始時，騎士在點(x,y)，現(xiàn)在請你找出一條可行的路徑，使得騎士可以不重復的走遍棋盤上的每一個點?！钡脑?，又要如何編寫此程序呢？跳馬問題

設有一個N*N方格的迷宮，入口和出口分別在左上角和右上角，迷宮格子中分別放有0和1，0表示可走，1表示不能走，迷宮走的規(guī)則如圖。當迷宮給出之后，找出一條從入口到出口的通路。輸入：NN*N的迷宮輸出：具體路徑輸入樣例：

8輸出樣例：(1,1)-(2,1)-(3,1)-(2,2)-(1,3)-(2,4)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)迷宮問題xy①②③④⑤⑥⑦⑧分析：增量和方向表示

dx=(1,1,-1,-1,1,-1,0,0)dy=(-1,0,1,0,1,-1,1,-1)path:array[1..maxn*maxn]ofinteger;其中，path[i]：表示第i個節(jié)點所走的方向解空間約束條件不越界且該點可走(x>=1)and(x<=N)and(y>=1)and(y<=N)andA[x,y]=1迷宮信息用二維數(shù)組表示

A:array[1..maxn,1..maxn]of0..1;入口（1,1）；出口（n,1）狀態(tài)樹迷宮問題給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。圖的著色問題

有形如下列圖形的地圖，圖中每一塊區(qū)域代表一個省份，現(xiàn)請你用紅（1）、蘭（2）、黃（3）、綠（4）四種顏色給這些省份填上顏色，要求每一省份用一種顏色，且任意兩個相鄰省份的顏色不能相同，請給出一種符合條件的填色方案。1234567圖的存儲R:array[1..n,1..n]of0..1;其中，R[I,j]=0------省i和省j不相鄰

=1------省i和省j相鄰①②③④⑤⑥⑦將實際地圖用無向圖的形式給出，每個省份代表圖上的一個頂點，邊代表兩個省份是相鄰的。四色問題圖的著色問題解向量：(x1,x2,…,xn)表示頂點i所著顏色x[i]

可行性約束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復。voidColor::Backtrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk){//檢查顏色可用性

for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}圖的著色問題1234567算法思想：從編號1的省開始，按4種顏色的排列順序，首先選擇第一種顏色，然后檢查是否矛盾，即相鄰的區(qū)域中是否已有該顏色，若不矛盾，則涂色，若矛盾，則選擇下一個顏色，再判斷，當4種顏色都不可能時，則需回溯。當?shù)谝粋€省的顏色確定之后，依次對第二個省、第三個省……進行處理，當所有省都涂上顏色之后，得到一種解法。color:array[1..maxn]ofinteger;其中，color[k]：表示第k個省所填的顏色解空間Color(1,2,1,3,1,3,4)迷宮問題Functionpd(k:integer):boolean;Varm:integer;Beginm:=1;{從第一個省份開始檢查是否沖突}pd:=true;{不沖突}

while(m<k)and(color[k]*g[m,k]<>color[m])doinc(m);ifk>=mthenpd:=false;{沖突}End;約束條件該點k涂的顏色(color[k)與和k相鄰的點m(1<=m<=k-1)的顏色(color[m])相同

color[k]*g[m,k]=color[m]狀態(tài)樹迷宮問題proceduresearch(k:integer);{遞歸搜索第m個省份}beginifk>nthen {是否所有省份都已經填色}beginwrite(color[1]);{已全部填色，輸出結果，終止程序}forj:=2tondowrite('',color[j]);writeln;haltendelse {還未全部填色}forj:=1to4dobegin{依次用四種顏色對當前省份填色}if(k<=n)andpd(k)then {沒有沖突}begincolor[k]:=j; {記錄當前省份顏色}search(k+1); {遞歸檢查下一個省份}end;end;end;四色問題（遞歸）迷宮問題輸入：第一行一個整數(shù)，為背包的容量M；第二行一個整數(shù)，為物品的種數(shù)Ｎ；第三行Ｎ個整數(shù)為各物品的重量；第四行Ｎ個整數(shù)分別為Ｎ個物品的價值輸出：第一行為最大總價值；第二行為裝入的各物品的重量（未裝的物品用０）；第三行為裝入的各物品的價值（未裝的物品用０）

已知一個容量大小為M重量的背包和N種物品，每種物品的重量為Wi。若將物品放入背包將得到Pi的效益，求怎樣選取物品將得到效益最大輸入樣例：

50

3

102030

60100120

輸出樣例：

220

02030

0100120測試數(shù)據(jù)：

輸入：

10

5

22654

63546

輸出：

?0-1背包問題bag:array[1..maxn]of0..1;其中，bag[k]=1表示第k個物品要取

0表示第k個物品不取解空間約束條件第k個物品確定放置方法后，背包所剩重量足夠放第K個物品wei-bag[k]*w[k]>=0 {wei：背包還能裝的重量}Best:=0;表示最大價值當一組解產生后，得到當前總價值count，

ifcount>bestthenbest:=count利用這種方法記錄最優(yōu)解！如果還要記錄最優(yōu)時的物品取法應：ifcount>bestthenbegin best:=count; fori:=1tondoy[i]:=bag[i];狀態(tài)樹求最優(yōu)值0-1背包問題本題可以用遞歸求解：本題可用方法很多！非遞歸寫法與前幾題相似，請自己寫出！算法分析：

設當前有N個物品，容量為M；這些物品要么選，要么不選，我們假設選的第一個物品編號為i（1~i-1號物品不選），問題又可以轉化為有N-I個物品（即第I+1~N號物品），容量為M-Wi的子問題……如此反復下去，然后在所有可行解中選一個效益最大的便可?；厮荩顟B(tài)恢復）后，需恢復的狀態(tài)有：Bag[k]背包可裝的物品重量：wei:=wei+w[k]*i已裝物品的價值總和：count:=count:-c[k]*i0-1背包問題procedurework(k,wei:integer);vari,j:integer;beginfori:=1downto0doif(wei-w[k]*i>=0)thenbeginbag[k]:=i;count:=count+c[k]*i;if(k=n)and(count>best)thenbeginbest:=count;forj:=1tondoy[j]:=bag[j];end;ifk<nthenwork(k+1,wei-w[k]*i);count:=count-c[k]*i;{狀態(tài)恢復}end;end;(k)(k,wei,count)work(k+1)wei:=wei+w[k]*iwork(k+1,wei-w[k])*i,count)0-1背包（遞歸）wei:=wei-w[k]*i0-1背包問題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價于以下特殊的0-1背包問題。用回溯法設計解裝載問題的O(2n)計算時間算法。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。裝載問題解空間：子集樹可行性約束函數(shù)(選擇當前元素)：上界函數(shù)(不選擇當前元素)：當前載重量cw+剩余集裝箱的重量r當前最優(yōu)載重量bestwvoidbacktrack(inti){//搜索第i層結點

if(i>n)//到達葉結點更新最優(yōu)解bestx,bestw;return;r-=w[i];

if(cw+w[i]<=c){//搜索左子樹

x[i]=1;cw+=w[i];

backtrack(i+1);cw-=w[i];}

if(cw+r>bestw){x[i]=0;//搜索右子樹

backtrack(i+1);}r+=w[i];}裝載問題給定n個作業(yè)的集合{J1,J2,…,Jn}。每個作業(yè)必須先由機器1處理，然后由機器2處理。作業(yè)Ji需要機器j的處理時間為tji。對于一個確定的作業(yè)調度，設Fji是作業(yè)i在機器j上完成處理的時間。所有作業(yè)在機器2上完成處理的時間和稱為該作業(yè)調度的完成時間和。批處理作業(yè)調度問題要求對于給定的n個作業(yè)，制定最佳作業(yè)調度方案，使其完成時間和達到最小。這3個作業(yè)的6種可能的調度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應的完成時間和分別是19，18，20，21，19，19。易見，最佳調度方案是1,3,2，其完成時間和為18。批處理作業(yè)問題解空間：排列樹voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}classFlowshop{friendFlow(int**,int,int[]);private:voidBacktrack(inti);int**M,//各作業(yè)所需的處理時間*x,//當前作業(yè)調度*bestx,//當前最優(yōu)作業(yè)調度*f2,//機器2完成處理時間

f1,//機器1完成處理時間

f,//完成時間和

bestf,//當前最優(yōu)值

n;//作業(yè)數(shù)};批處理作業(yè)問題【問題描述】

從整數(shù)1到10中任取9個不同的數(shù)，填入下面的9個格子中，使所有相鄰（左、右、上、下）兩個格子中的數(shù)的和是素數(shù)?！据敵觥?/p>

一行3個數(shù)，共3行?！緲永?/p>

125 438 7109【說明】

輸出所有本質不同的解。（通過某個解的旋轉、上下翻轉、左右翻轉得到的是本質相同的）填數(shù)問題【問題描述】

排列與組合是常用的數(shù)學方法，其中組合