五、回溯法回溯法也稱為試探法，該方法首先暫時放棄關于問題規模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，并繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。1、回溯法的一般描述可用回溯法求解的問題P,通常要能表達為：對于已知的由n元組(xl,x2,,xn)組成的一個狀態空間E={(x1,x2,,xn)|xi^Si,i=1,2,,n},給定關于n元組中的一個分量的一個約束集D,要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且|Si有限，i=1,2,,n。我們稱￡中滿足D的全部約束條件的任一n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。我們發現，對于許多問題，所給定的約束集D具有完備性，即i元組(xl,x2,,xi)滿足D中僅涉及到x1,x2,,xi的所有約束意味著j(j<)元組(x1,x2,,xj)一定也滿足D中僅涉及到x1,x2,,xj的所有約束，i=1,2,,n。換句話說，只要存在0<j<n-1,使得(x1,x2,,乂小違反。中僅涉及到x1,x2,,xj的約束之一，則以(x1,x2,,xj)為前綴的任何n元組(x1,x2,,xjxj+1,,xn)一定也違反。中僅涉及到x1,x2,,xi的一個約束，n>i〉j因此，對于約束集D具有完備性的問題P,一旦檢測斷定某個j元組(x1,x2,,xj)違反。中僅涉及x1,x2,,xj的一個約束，就可以肯定，以(x1,x2,,xj)為前綴的任何n元組(x1,x2,,xjxj+1,,xn)都不會是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的算法。回溯法首先將問題P的n元組的狀態空間E表示成一棵高為n的帶權有序樹T,把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構造：設Si中的元素可排成xi(1),xi(2),,xi(mi-1),|Si=mi,i=1,2,,n。從根開始，讓T的第I層的每一個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1),xi+1(2),,xi+1(mi),i=0,1,2,,n-1。照這種構造方式，E中的一個n元組(x1,x2,,xn)對應于T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的n條邊的權分別為x1,x2,,xn,反之亦然。另外，對于任意的0<i<n-1,E中n元組(x1,x2,,xn)的一個前綴I元組(x1,x2,,xi)對應于T中的一個非葉子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為x1,x2,,乂［反之亦然。特別，E中的任意一個n元組的空前綴()，對應于T的根。因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結點，要求從T的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1,x2,,xn滿足約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從根出發，按深度優先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（xli）、前綴2元組（xl,x2）、…，前綴I元組（xl,x2,…，xi）,…，直到i=n為止。在回溯法中，上述引入的樹被稱為問題P的狀態空間樹；樹T上任意一個結點被稱為問題P的狀態結點；樹T上的任意一個葉子結點被稱為問題P的一個解狀態結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題P的一個回答狀態結點，它對應于問題P的一個解。【問題】組合問題問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5,r=3的所有組合為：(1)1、2、3(2)1、2、4(3)1、2、5(4)1、3、4(5)1、3、5(6)1、4、5(7)2、3、4(8)2、3、5(9)2、4、5(10)3、4、5則該問題的狀態空間為：E={（xl，x2，x3）|xieS，i=1，2，3}其中：S={1，2，3，4，5}約束集為：x1<x2<x3顯然該約束集具有完備性。問題的狀態空間樹T：RE：c語言經典算法2、回溯法的方法對于具有完備約束集D的一般問題P及其相應的狀態空間樹T，利用T的層次結構和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：從T的根出發，按深度優先的策略，系統地搜索以其為根的子樹中可能包含著回答結點的所有狀態結點，而跳過對肯定不含回答結點的所有子樹的搜索，以提高搜索效率。具體地說，當搜索按深度優先策略到達一個滿足D中所有有關約束的狀態結點時，即“激活”該狀態結點，以便繼續往深層搜索；否則跳過對以該狀態結點為根的子樹的搜索，而一邊逐層地向該狀態結點的祖先結點回溯，一邊“殺死”其兒子結點已被搜索遍的祖先結點，直到遇到其兒子結點未被搜索遍的祖先結點，即轉向其未被搜索的一個兒子結點繼續搜索。在搜索過程中，只要所激活的狀態結點又滿足終結條件，那么它就是回答結點，應該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點后，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結點均已被搜索過為止。例如在組合問題中，從T的根出發深度優先遍歷該樹。當遍歷到結點（1，2）時，雖然它滿足約束條件，但還不是回答結點，則應繼續深度遍歷；當遍歷到葉子結點（1,2,5）時，由于它已是一個回答結點，則保存（或輸出）該結點，并回溯到其雙親結點，繼續深度遍歷；當遍歷到結點（1,5）時，由于它已是葉子結點，但不滿足約束條件，故也需回溯。3、回溯法的一般流程和技術在用回溯法求解有關問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：在用回溯法求解問題，也即在遍歷狀態空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數據結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯過程。例如在組合問題中，我們用一個一維數組Stack[]表示棧。開始棧空，則表示了樹的根結點。如果元素1進棧，則表示建立并遍歷（1）結點；這時如果元素2進棧，則表示建立并遍歷（1，2）結點；元素3再進棧，則表示建立并遍歷（1，2,3）結點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或保存）。這時只要棧頂元素（3）出棧，即表示從結點（1，2,3）回溯到結點（1，2）。【問題】組合問題問題描述：找出從自然數1,2,…，n中任取r個數的所有組合。采用回溯法找問題的解，將找到的組合以從小到大順序存于a[0],a[1]，…，a[r-1]中，組合的元素滿足以下性質：（1）a[i+1]>a[i]，后一個數字比前一個大；（2）a[i]-i<=n-r+1。按回溯法的思想，找解過程可以敘述如下：首先放棄組合數個數為r的條件，候選組合從只有一個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，并使其滿足上述條件（1）,候選組合改為1,2。繼續這一過程，得到候選組合1,2,3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4,以及以后調整為5都滿足問題的全部要求，得到解1,2,4和1，2,5。由于對5不能再作調整，就要從a[2]回溯到a[1],這時，a[1]=2,可以調整為3,并向前試探，得到解1,3,4。重復上述向前試探和向后回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程序如下：【程序】**從n個不同元素中取出m個元素構成的所有組合。*按照字典序從小到大輸出所有組合。#include<stdio.h>#defineMAXN100inta[MAXN];voidcomb(intm,intr)(inti,j;i=0;a[i]=1；do{if(a[i]-i<=m-r+1)(if(i==r-1)(for(j=0;j<r;j++)printf("%d%c",a[j],(j==r-l)?'\n‘:'');a[i]++;continue;}i++；a[i]=a[i-l]+l;}else{if(i==0)return;a[--i]++;}}while(1);}intmain(){intn,m;scanf("%d%d",&n,&m);comb(n,m);return0;}【問題】填字游戲問題描述：在3X3個方格的方陣中要填入數字1到N(N310)內的某9個數字，每個方格填一個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試求出所有滿足這個要求的各種數字填法。可用試探發找到問題的解，即從第一個方格開始，為當前方格尋找一個合理的整數填入，并在當前位置正確填入后，為下一方格尋找可填入的合理整數。如不能為當前方格找到一個合理的可填證書，就要回退到前一方格，調整前一方格的填入數。當第九個方格也填入合理的整數后，就找到了一個解，將該解輸出，并調整第九個的填入的整數，尋找下一個解。為找到一個滿足要求的9個數的填法，從還未填一個數開始，按某種順序(如從小到大的順序)每次在當前位置填入一個整數，然后檢查當前填入的整數是否能滿足要求。在滿足要求的情況下，繼續用同樣的方法為下一方格填入整數。如果最近填入的整數不能滿足要求，就改變填入的整數。如對當前方格試盡所有可能的整數，都不能滿足要求，就得回退到前一方格，并調整前一方格填入的整數。如此重復執行擴展、檢查或調整、檢查，直到找到一個滿足問題要求的解，將解輸出。回溯法找一個解的算法：(intm=0,ok=1;intn=8;do{if(ok)擴展；else調整；ok=檢查前m個整數填放的合理性；}while((!okllm!=n)&&(m!=0))if(m!=0)輸出解；else輸出無解報告；}如果程序要找全部解，則在將找到的解輸出后，應繼續調整最后位置上填放的整數，試圖去找下一個解。相應的算法如下:回溯法找全部解的算法：{intm=0,ok=1;intn=8;do{if(ok){if(m==n){輸出解；調整；}else擴展；}else調整；ok=檢查前m個整數填放的合理性；}while(m!=0);}為了確保程序能夠終止，調整時必須保證曾被放棄過的填數序列不會再次實驗，即要求按某種有許模型生成填數序列。給解的候選者設定一個被檢驗的順序，按這個順序逐一形成候選者并檢驗。從小到大或從大到小，都是可以采用的方法。如擴展時，先在新位置填入整麴，調整時，找當前候選解中下一個還未被使用過的整數。將上述擴展、調整、檢驗都編寫成程序，細節見以下找全部解的程序。【程序】include<stdio.h>defineN12voidwrite(inta[]){inti,j;for(i=0;i<3;i++){for(j=0;j<3;j++)printf("％3d”，a[3*i+j]);printf("\n”);}scanf("％*c”);}intb[N+1];inta[10];intisprime(intm){inti;intprimes[]={2,3,5,7,11,17,19,23,29,-1};if(m==1||m%2=0)return0;for(i=0;primes[i]>0;i++)if(m==primes[i])return1;for(i=3;i*i<=m;){if(m%i==0)return0;i+=2;return1;intcheckmatrix[][3]={{-1},{0,-1},{1,-1},{0,-1},{1,3,-1},{2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};intselectnum(intstart)(intj；for(j=start;j<=N;j++)if(b[j])returnjreturn0;}intcheck(intpos)(intij;if(pos<0)return0;for(i=0;(j=checkmatrix[pos][i])>=0;i++)if(!isprime(a[pos]+a[j])return0;return1;}intextend(intpos){a[++pos]=selectnum(1);b[a][pos]]=0;returnpos;intchange(intpos)(intj；while(pos>=0&&(j=selectnum(a[pos]+1))—0)b[a[pos-]]=l;if(pos<0)return-1b[a[pos]]=l;a[pos]=j;b[j]=O;returnpos;}voidfind(){intok=0,pos=0;a[pos]=l;b[a[pos]]=0;do{if(ok)if(pos==8){write(a);pos=change(pos);}elsepos=extend(pos);elsepos=change(pos);ok=check(pos);}while(pos>=0)}voidmain()(inti;for(i=1;i<=N;i++)b[i]=1；find();}【問題】n皇后問題問題描述：求出在一個nXn的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。這是來源于國際象棋的一個問題。皇后可以沿著縱橫和兩條斜線4個方向相互捕捉。如圖所示，一個皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“X”的位置上的皇后就能與這個皇后相互捕捉。12345678XXXXXXXXXXQXXXXXXXXXXXXXXX從圖中可以得到以下啟示：一個合適的解應是在每列、每行上只有一個皇后，且一條斜線上也只有一個皇后。求解過程從空配置開始。在第1列至第m列為合理配置的基礎上，再配置第m+1歹L直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置，希望獲得下一個解。另外，在任一列上，可能有n種配置。開始時配置在第1行，以后改變時，順次選擇第2行、第3行、…、直到第n行。當第n行配置也找不到一個合理的配置時，就要回溯，去改變前一列的配置。得到求解皇后問題的算法如下：{輸入棋盤大小值n；m=0;good=1;do{if(good)if(m==n){輸出解；改變之，形成下一個候選解；}else擴展當前候選接至下一列；else改變之，形成下一個候選解；good=檢查當前候選解的合理性；}while(m!=0);}在編寫程序之前，先確定邊式棋盤的數據結構。比較直觀的方法是采用一個二維數組，但仔細觀察就會發現，這種表示方法給調整候選解及檢查其合理性帶來困難。更好的方法乃是盡可能直接表示那些常用的信息。對于本題來說，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已經在某行和某條斜線合理地安置好了”。因在某一列上恰好放一個皇后，引入一個一維數組(col[])，值col[i]表示在棋盤第i歹叭col[i]行有一個皇后。例如：col[3]=4,就表示在棋盤的第3列、第4行上有一個皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設定col[0]的初值為0當回溯到第0列時，說明程序已求得全部解，結束程序運行。為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個工作數組：數組a[]，a[k]表示第k行上還沒有皇后；數組b[]，b[k]表示第k列右高左低斜線上沒有皇后；數組c[]，c[k]表示第k列左高右低斜線上沒有皇后；棋盤中同一右高左低斜線上的方格，他們的行號與列號之和相同；同一左高右低斜線上的方格，他們的行號與列號之差均相同。初始時，所有行和斜線上均沒有皇后，從第1列的第1行配置第一個皇后開始，在第m列col[m]行放置了一個合理的皇后后，準備考察第m+1列時，在數組a[]、b[]和c[]中為第m列，col[m]行的位置設定有皇后標志；當從第m列回溯到第m-1歹U，并準備調整第m-1列的皇后配置時，清除在數組a[]、b[]和c[]中設置的關于第m-1歹U,col[m-1]行有皇后的標志。一個皇后在m歹U，col[m]行方格內配置是合理的，由數組心"[]和c[]對應位置的值都為1來確定。細節見以下程序：【程序】include<stdio.h>include<stdlib.h>defineMAXN20intn,m,good;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];voidmain(){intj；charawn;printf(“Entern:“)；scanf("％d”，&n);for(j=0;j<=n;j++)a[j]=1;for(j=0;j<=2*n;j++)cb[j]=c[j]=1;m=1;col[1]=1;good=1;col[0]=0;do{if(good)if(m==n){printf(“列\t行”);for(j=1;j<=n;j++)printf("％3d\t%d\n”，j,col[j]);printf(“Enteracharacter(Q/qforexit)!\n”);scanf("%c”，&awn);if(awn==’Q’||awn==’q’)exit(0);while(col[m]==n){m--;a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;}col[m]++;}else{a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;col[++m]=1;}else{while(col[m]==n){m--;a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;}col[m]++;}good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];}while(m!=0);}試探法找解算法也常常被編寫成遞歸函數，下面兩程序中的函數queen_all()和函數queen_one()能分別用來解皇后問題的全部解和一個解。【程序】include<stdio.h>include<stdlib.h>defineMAXN20intn;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];voidmain(){intj:printF(Entern:“);scanf^d",&n);for(j=0;j<=n;j++)a[j]=l:for(j=0;j<=2*n;j++)cb[j]=c[j]=l:queen_all(1,n);}voidqueen_all(intk,intn){inti,j:charawn;for(i=l;i<=n;i++)if(a[i]&&b[k+i]&&c[n+k-i]){col[k]=i:a[i]=b[k+i]=c[n+k-i]=0;if(k==n){print妾例、行”);for(j=l:j<=n;j++)printF(%3d\t%d\nw,j,col[j]);printF(Enteracharacter(Q/qfor枝x)U)!\nscanf0%c”,&awn);if(awn=-Qf\\awn=-q，)exit(0):queen_all(k+1,n);a[i]=b[k+i]=c[n+k-i];}}采用遞歸方法找一個解與找全部解稍有不同，在找一個解的算法中，遞歸算法要對當前候選解最終是否能成為解要有回答。當它成為最終解時，遞歸函數就不再遞歸試探，立即返回；若不能成為解，就得繼續試探。設函數queen_one()返回1表示找到解，返回0表示當前候選解不能成為解。細節見以下函數。【程序】#defineMAXN20intn;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];intqueen_one(intk,intn)(inti,found;i=found=0;While(!found&&i<n){i++;if(a[i]&&b[k+i]&&c[n+k-i]){col[k]=i;a[i]=b[k+i]=c[n+k-i]=0;if(k==n)return1;elsefound=queen_one(k+1,n);a[i]=b[k+i]=c[n+k-i]=1;}}returnfound;}六、貪婪法貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。例如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。【問題】裝箱問題問題描述：裝箱問題可簡述如下：設有編號為0、1、…、n-1的n種物品，體積分別為v0、v1、?、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過V，即對于0WiVn，有0VviWV。不同的裝箱方案所需要的箱子數目可能不同。裝箱問題要求使裝盡這n種物品的箱子數要少。若考察將n種物品的集合分劃成n個或小于n個物品的所有子集，最優解就可以找到。但所有可能劃分的總數太大。對適當大的如，找出所有可能的劃分要花費的時間是無法承受的。為此，對裝箱問題采用非常簡單的近似算法，即貪婪法。該算法依次將物品放到它第一個能放進去的箱子中，該算法雖不能保證找到最優解，但還是能找到非常好的解。不失一般性，設n件物品的體積是按從大到小排好序的，即有v03v1m?mvn-1。如不滿足上述要求，只要先對這n件物品按它們的體積從大到小排序，然后按排序結果對物品重新編號即可。裝箱算法簡單描述如下：（輸入箱子的容積；輸入物品種數n；按體積從大到小順序，輸入各物品的體積；預置已用箱子鏈為空；預置已用箱子計數器box_count為0；for（i=0;i<n;i++）（從已用的第一只箱子開始順序尋找能放入物品i的箱子j；if（已用箱子都不能再放物品i）（另用一個箱子，并將物品i放入該箱子；box_count++;}else將物品訪攵入箱子j；}}上述算法能求出需要的箱子數box_count并能求出各箱子所裝物品。下面的例子說明該算法不一定能找到最優解，設有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個單位體積。按上述算法計算，需三只箱子，各箱子所裝物品分別為：第一只箱子裝物品1、3;第二只箱子裝物品2、4、5;第三只箱子裝物品6。而最優解為兩只箱子，分別裝物品1、4、5和2、3、6。若每只箱子所裝物品用鏈表來表示，鏈表首結點指針存于一個結構中，結構記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構成鏈表。以下是按以上算法編寫的程序。【程序】include<stdio.h>include<stdlib.h>typedefstructele{intvno;structele*link;}ELE;typedefstructhnode{intremainder;ELE*head;Structhnode*next;}HNODE;voidmain(){intn,i,box_count,box_volume,*a;HNODE*box_h,*box_t,*j;ELE*p,*q;Printf(“輸入箱子容積\n”)；Scanf("％d”，&box_volume);Printf(“輸入物品種數\n”);Scanf("％d”，&n);A=(int*)malloc(sizeof(int)*n);Printf(“請按體積從大到小順序輸入各物品的體積:”For(i=0;i<n;i++)scanf("％d”,a+i);Box_h=box_t=NULL;Box_count=0;For(i=0;ivn;i++){p=(ELE*)malloc(sizeof(ELE));p->vno=i;for(j=box_h;j!=NULL;j=j->next)if(j->remainder>=a[i])break;if(j=NULL){j=(HNODE*)malloc(sizeof(HNODE));j->remainder=box_volume-a[i];j->head=NULL;if(box_h=NULL)box_h=box_t=j;elsebox_t=boix_t->next=j;j->next=NULL;box_count++;}elsej->remainder-=a[i];for（q=j->next;q!=NULL&&q->link!=NULL;q=q->link）;if（q==NULL）（p->link=j->head;j->head=p;}else{p->link=NULL;q->link=p;}}printf（“共使用了%d只箱子”，box_count）;printf（“各箱子裝物品情況如下:”）;for（j=box_h,i=1;j!=NULL;j=j->next,i++）{printf（“第%2d只箱子，還剩余容積%4d，所裝物品有；\n”，I,j->remainder）;for（p=j->head;p!=NULL;p=p->link）printf（"％4d”,p->vno+1）;printf（"\n”）;}}【問題】馬的遍歷問題描述：在8X8方格的棋盤上，從任意指定的方格出發，為馬尋找一條走遍棋盤每一格并且只經過一次的一條路徑。馬在某個方格，可以在一步內到達的不同位置最多有8個，如圖所示。如用二維數組board[][]表示棋盤，其元素記錄馬經過該位置時的步驟號。另對馬的8種可能走法（稱為著法）設定一個順序，如當前位置在棋盤的（i，j）方格，下一個可能的位置依次為（i+2,j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2,j-1）、（i-1，j-2）、（i+1，j-2）、（i+2,j-1），實際可以走的位置盡限于還未走過的和不越出邊界的那些位置。為便于程序的同意處理，可以引入兩個數組，分別存儲各種可能走法對當前位置的縱橫增量。TOC\o"1-5"\h\z2馬10對于本題，一般可以采用回溯法，這里采用Warnsdoff策略求解，這也是一種貪婪法，其選擇下一出口的貪婪標準是在那些允許走的位置中，選擇出口最少的那個位置。如馬的當前位置(i,j)只有三個出口，他們是位置(i+2,j+1)、(i-2,j+1)和(i-1，j-2)，如分別走到這些位置，這三個位置又分別會有不同的出口，假定這三個位置的出口個數分別為4、2、3,則程序就選擇讓馬走向(i-2,j+1)位置。由于程序采用的是一種貪婪法，整個找解過程是一直向前，沒有回溯，所以能非常快地找到解。但是，對于某些開始位置，實際上有解，而該算法不能找到解。對于找不到解的情況，程序只要改變8種可能出口的選擇順序，就能找到解。改變出口選擇順序，就是改變有相同出口時的選擇標準。以下程序考慮到這種情況，引入變量start，用于控制8種可能著法的選擇順序。開始時為0，當不能找到解時，就讓start增1，重新找解。細節以下程序。【程序】#include<stdio.h>intdelta_i[]={2,1,-1,-2,-2,-1,1,2};intdelta項]={1,2,2,1,-1,-2,-2,-1};intboard[8][8];intexitn(inti,intj,ints,inta[]){inti1,j1,k,count;for(count=k=0;k<8;k++){i1=i+delta_i[(s+k)%8];j1=i+delta_j[(s+k)%8];if(i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)a[count++]=(s+k)%8;}returncount;intnext(inti,intj,ints){intm,k,mm,min,a[8],b[8],temp;m=exitn(i,j,s,a);if(m=0)return-1;for(min=9,k=0;kvm;k++){temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);if(temp<min){min=temp;kk=a[k];}}returnkk;}voidmain(){intsx,sy,i,j,step,no,start;for(sx=0;sxv8;sx++)for(sy=0;syv8;sy++){start=0;do{for(i=0;i<8;i++)for(j=O;j<8;j++)board[i][j]=0;board[sx][sy]=1;I=sx;j=sy;For(step=2;step<64;step++)(if((no=next(i,j,start))==-1)break;I+=delta_i[no];j+=delta項no];board[i][j]=step;}if(step>64)break;start++;}while(step<=64)for(i=0;i<8;i++){for(j=0;j<8;j++)printf("％4d”,board[i][j]);printf("\n\n”);}scanf("％*c”);}}今天復習了回溯算法。N皇后問題是一個典型的需要用回溯算法來解決的問題。回溯算法可以用遞歸方法來實現，也可以用非遞歸方法來實現。用遞歸的方法來解決回溯的問題思路很清晰，但是耗費的內存資源較多，速度也較慢；非遞歸方法具有速度快和耗費較少內存資源的優點，但是程序的邏輯結構卻很復雜——不過搞懂之后覺得也很簡單。在寫非遞歸算法之前，參考了網上的一些文章，但是覺得那些程序都很晦澀難懂，而且存在一些問題，我索性自己寫了一個，花了我不少時間。遞歸實現：#include"stdio.h"#include"stdlib.h"#include"time.h"/**//*記錄當前的放置方案*/int*x;/**//*皇后的個數N和方案數目*/intn,sum=0;/**//*檢查參數所指示的這一行皇后放置方案是否滿足要求*/intPlace(int);/**//*遞歸方法求取皇后放置方案*/voidQueen1(void);/**//*用戶遞歸求取皇后放置方案的遞歸方法*/voidTraceBack(int);/**//*打印當前成功的放置方案*/voidPrintMethod(void);voidmain(void){longstart,stop;printf("inputn:");scanf("%d",&n);x=(int*)malloc(sizeof(int)*n);time(&start);/**〃*記錄開始時間*/Queen1();time(&stop);/**〃*記錄結束時間*/printf("\nmethodtotal%d\n",sum);printf("\nuse%dseconds\n",(int)(stop-start));}intPlace(intr)(inti;for(i=0;i<r;i++){if(x[r]==x[i]IIabs(r-i)==abs(x[r]-x