回溯算法實例一培訓(xùn)講學(xué)

回溯算法實例一精品文檔【問題】 填字游戲問題描述：在3×3個方格的方陣中要填入數(shù)字1到N（N≥10）內(nèi)的某9個數(shù)字，每個方格填一個整數(shù)，使得所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。試求出所有滿足這個要求的各種數(shù)字填法?？捎迷囂桨l(fā)找到問題的解，即從第一個方格開始，為當(dāng)前方格尋找一個合理的整數(shù)填入，并在當(dāng)前位置正確填入后，為下一方格尋找可填入的合理整數(shù)。如不能為當(dāng)前方格找到一個合理的可填證書，就要回退到前一方格，調(diào)整前一方格的填入數(shù)。當(dāng)?shù)诰艂€方格也填入合理的整數(shù)后，就找到了一個解，將該解輸出，并調(diào)整第九個的填入的整數(shù)，尋找下一個解。為找到一個滿足要求的 9個數(shù)的填法，從還未填一個數(shù)開始，按某種順序（如從小到大的順序）每次在當(dāng)前位置填入一個整數(shù)，然后檢查當(dāng)前填入的整數(shù)是否能滿足要求。在滿足要求的情況下，繼續(xù)用同樣的方法為下一方格填入整數(shù)。如果最近填入的整數(shù)不能滿足要求，就改變填入的整數(shù)。如對當(dāng)前方格試盡所有可能的整數(shù)，都不能滿足要求，就得回退到前一方格，并調(diào)整前一方格填入的整數(shù)。如此重復(fù)執(zhí)行擴(kuò)展、檢查或調(diào)整、檢查，直到找到一個滿足問題要求的解，將解輸出?；厮莘ㄕ乙粋€解的算法：{intm=0,ok=1;intn=8;do{if(ok) 擴(kuò)展;else 調(diào)整;ok=檢查前m個整數(shù)填放的合理性;}while((!ok||m!=n)&&(m!=0))if(m!=0) 輸出解;else 輸出無解報告；}如果程序要找全部解，則在將找到的解輸出后，應(yīng)繼續(xù)調(diào)整最后位置上填放的整數(shù)，試圖去找下一個解。相應(yīng)的算法如下：回溯法找全部解的算法：{intm=0,ok=1;intn=8;do{if(ok){if(m==n){輸出解；調(diào)整；}else 擴(kuò)展;}else 調(diào)整;ok=檢查前m個整數(shù)填放的合理性;}while(m!=0);收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔}為了確保程序能夠終止，調(diào)整時必須保證曾被放棄過的填數(shù)序列不會再次實驗，即要求按某種有許模型生成填數(shù)序列。給解的候選者設(shè)定一個被檢驗的順序，按這個順序逐一形成候選者并檢驗。從小到大或從大到小，都是可以采用的方法。如擴(kuò)展時，先在新位置填入整數(shù)1，調(diào)整時，找當(dāng)前候選解中下一個還未被使用過的整數(shù)。將上述擴(kuò)展、調(diào)整、檢驗都編寫成程序，細(xì)節(jié)見以下找全部解的程序?！境绦颉?include<stdio.h>;#define N 12voidwrite(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>;0;i++)if(m==primes) 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;}收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔intcheck(intpos){inti,j;if(pos<0) return0;for(i=0;(j=checkmatrix[pos])>;=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--]]=1;if(pos<0) return –1b[a[pos]]=1;a[pos]=j;b[j]=0;returnpos;}voidfind(){intok=0,pos=0;a[pos]=1;b[a[pos]]=0;do{if(ok)if(pos==8){write(a);pos=change(pos);}else pos=extend(pos);else pos=change(pos);ok=check(pos);}while(pos>;=0)}voidmain(){inti;for(i=1;i<=N;i++)收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔b=1;find();}/jh/23/437639.html五、回溯法回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時，就選擇下一個候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當(dāng)前候選解，尋找下一個候選解的過程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。1、回溯法的一般描述可用回溯法求解的問題 P，通常要能表達(dá)為：對于已知的由 n元組（x1，x2，，xn）組成的一個狀態(tài)空間 E={（x1，x2，，xn）∣xi∈Si，i=1，2，，n}，給定關(guān)于n元組中的一個分量的一個約束集 D，要求E中滿足D的全部約束條件的所有 n元組。其中Si是分量xi的定義域，且|Si|有限，i=1，2，，n。我們稱E中滿足D的全部約束條件的任一 n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對 E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題 P的一個解。但顯然，其計算量是相收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔當(dāng)大的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集 D具有完備性，即i元組（x1，x2，，xi）滿足D中僅涉及到x1，x2，，xi的所有約束意味著 j（j<i）元組（x1，x2，，xj）一定也滿足D中僅涉及到x1，x2，，xj的所有約束，i=1，2，，n。換句話說，只要存在 0≤j≤n-1，使得（x1，x2，，xj）違反D中僅涉及到x1，x2，，xj的約束之一，則以（x1，x2，，xj）為前綴的任何n元組（x1，x2，，xj，xj+1，，xn）一定也違反D中僅涉及到x1，x2，，xi的一個約束，n≥i>j。因此，對于約束集 D具有完備性的問題 P，一旦檢測斷定某個 j元組（x1，x2，，xj）違反D中僅涉及x1，x2，，xj的一個約束，就可以肯定，以（ x1，x2，，xj）為前綴的任何 n元組（x1，x2，，xj，xj+1，，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法?；厮莘ㄊ紫葘栴} P的n元組的狀態(tài)空間E表示成一棵高為 n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在 T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造：設(shè)Si中的元素可排成xi(1)，xi(2)，，xi(mi-1)，|Si|=mi，i=1，2，，n。從根開始，讓T的第I層的每一個結(jié)點都有 mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán) xi+1(1)，xi+1(2)，，xi+1(mi)，i=0，1，2，，n-1。照這種構(gòu)造方式，E中的一個n元組（x1，x2，，xn）對應(yīng)于T中的一個葉子結(jié)點，T的根到這個葉子結(jié)點的路徑上依次的 n條邊的權(quán)分別為x1，x2，，xn，反之亦然。另外，對于任意的 0≤i≤n-1，E中n元組收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔（x1，x2，，xn）的一個前綴I元組（x1，x2，，xi）對應(yīng)于T中的一個非葉子結(jié)點，T的根到這個非葉子結(jié)點的路徑上依次的 I條邊的權(quán)分別為 x1，x2，，xi，反之亦然。特別，E中的任意一個 n元組的空前綴（），對應(yīng)于 T的根。因而，在E中尋找問題P的一個解等價于在 T中搜索一個葉子結(jié)點，要求從T的根到該葉子結(jié)點的路徑上依次的 n條邊相應(yīng)帶的n個權(quán)x1，x2，，xn滿足約束集D的全部約束。在 T中搜索所要求的葉子結(jié)點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴 1元組（x1i）、前綴2元組（x1，x2）、，前綴I元組（x1，x2，，），，直到i=n為止。在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié)點被稱為問題P的狀態(tài)結(jié)點；樹T上的任意一個葉子結(jié)點被稱為問題 P的一個解狀態(tài)結(jié)點；樹 T上滿足約束集D的全部約束的任意一個葉子結(jié)點被稱為問題P的一個回答狀態(tài)結(jié)點，它對應(yīng)于問題 P的一個解?！締栴}】 組合問題問題描述：找出從自然數(shù) 1、2、、n中任取r個數(shù)的所有組合。例如n=5，r=3的所有組合為：1）1、2、3（2）1、2、4（3）1、2、54）1、3、4（5）1、3、5（6）1、4、57）2、3、4（8）2、3、5（9）2、4、510）3、4、5則該問題的狀態(tài)空間為：收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔E={（x1，x2，x3）∣xi∈S，i=1，2，3} 其中：S={1，2，3，4，5}約束集為： x1<x2<x3顯然該約束集具有完備性。問題的狀態(tài)空間樹 T：2、回溯法的方法對于具有完備約束集 D的一般問題P及其相應(yīng)的狀態(tài)空間樹 T，利用T的層次結(jié)構(gòu)和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結(jié)點的所有狀態(tài)結(jié)點，而跳過對肯定不含回答結(jié)點的所有子樹的搜索，以提高搜索效率。具體地說，當(dāng)搜索按深度優(yōu)先策略到達(dá)一個滿足 D中所有有關(guān)約束的狀態(tài)結(jié)點時，即 “激活”該狀態(tài)結(jié)點，以便繼續(xù)往深層搜索；否則跳過對以該狀態(tài)結(jié)點為根的子樹的搜索，而一邊逐層地向該狀態(tài)結(jié)點的祖先結(jié)點回溯，一邊“殺死”其兒子結(jié)點已被搜索遍的祖先結(jié)點，直到遇到其兒子結(jié)點未被搜索遍的祖先結(jié)點，即轉(zhuǎn)向其未被搜索的一個兒子結(jié)點繼續(xù)搜索。在搜索過程中，只要所激活的狀態(tài)結(jié)點又滿足終結(jié)條件，那么它就是回答結(jié)點，應(yīng)該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結(jié)點后，同時也要進(jìn)行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結(jié)點均已被搜索過為止。例如在組合問題中，從 T的根出發(fā)深度優(yōu)先遍歷該樹。當(dāng)遍歷到結(jié)點（ 1，收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔2）時，雖然它滿足約束條件，但還不是回答結(jié)點，則應(yīng)繼續(xù)深度遍歷；當(dāng)遍歷到葉子結(jié)點（1，2，5）時，由于它已是一個回答結(jié)點，則保存（或輸出）該結(jié)點，并回溯到其雙親結(jié)點，繼續(xù)深度遍歷；當(dāng)遍歷到結(jié)點（ 1，5）時，由于它已是葉子結(jié)點，但不滿足約束條件，故也需回溯。3、回溯法的一般流程和技術(shù)在用回溯法求解有關(guān)問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時，不僅可以用棧來表示正在遍歷的樹的結(jié)點，而且可以很方便地表示建立孩子結(jié)點和回溯過程。例如在組合問題中，我們用一個一維數(shù)組 Stack[]表示棧。開始?？?，則表示了樹的根結(jié)點。如果元素 1進(jìn)棧，則表示建立并遍歷（ 1）結(jié)點；這時如果元素 2進(jìn)棧，則表示建立并遍歷（ 1，2）結(jié)點；元素3再進(jìn)棧，則表示建立并遍歷1，2，3）結(jié)點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或保存）。這時只要棧頂元素（3）出棧，即表示從結(jié)點（1，2，3）回溯到結(jié)點（1，2）?！締栴}】組合問題問題描述：找出從自然數(shù)1，2，，n中任取r個數(shù)的所有組合。采用回溯法找問題的解，將找到的組合以從小到大順序存于a[0]，a[1]，，a[r-1]中，組合的元素滿足以下性質(zhì)：（1） a[i+1]>a[i]，后一個數(shù)字比前一個大；收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔2）a[i]-i<=n-r+1。按回溯法的思想，找解過程可以敘述如下：首先放棄組合數(shù)個數(shù)為r的條件，候選組合