實驗6子集和問題的回溯算法設(shè)計與實現(xiàn)報告

1、實驗6 子集和問題的回溯算法設(shè)計與實現(xiàn)一、實驗目的1、掌握回溯法解題的基本思想；2、掌握回溯算法的設(shè)計方法；3、針對子集和數(shù)問題，熟練掌握回溯遞歸算法、迭代算法的設(shè)計與實現(xiàn)。二、實驗內(nèi)容1、認真閱讀教材或參考書, 掌握回溯法解題的基本思想, 算法的抽象控制策略；2、了解子集和數(shù)問題及解向量的定長和變長狀態(tài)空間表示；3、針對解向量的定長表示, 設(shè)計狀態(tài)空間樹節(jié)點擴展的規(guī)范(限界)函數(shù)及實現(xiàn)方法；4、分析深度優(yōu)先擴展狀態(tài)空間樹節(jié)點或回溯的條件；5、分析和設(shè)計生成解向量各分量可選值的實現(xiàn)方法；6、設(shè)計和編制回溯算法的遞歸和迭代程序。【實驗題】：組合數(shù)問題：找出從自然數(shù)1，2，n中任取r個數(shù)的所有組合

2、。3、 算法的原理方法回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探?？梢圆捎没厮莘ㄕ覇栴}的解，將找到的組合以從小到大順序存于a0，a1，ar-1中，組合的元素滿足以下性質(zhì)：（1）  ai

3、+1>ai，后一個數(shù)字比前一個大；（2）  ai-i<=n-r+1。按回溯法的思想，找解過程可以敘述如下：首先放棄組合數(shù)個數(shù)為r的條件，候選組合從只有一個數(shù)字1開始。因該候選解滿足除問題規(guī)模之外的全部條件，擴大其規(guī)模，并使其滿足上述條件（1），候選組合改為1，2。繼續(xù)這一過程，得到候選組合1，2，3。該候選解滿足包括問題規(guī)模在內(nèi)的全部條件，因而是一個解。在該解的基礎(chǔ)上，選下一個候選解，因a2上的3調(diào)整為4，以及以后調(diào)整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由于對5不能再作調(diào)整，就要從a2回溯到a1，這時，a1=2，可以調(diào)整為3，并向前試探，得到

4、解1，3，4。重復上述向前試探和向后回溯，直至要從a0再回溯時，說明已經(jīng)找完問題的全部解。4、 實驗程序的功能模塊void comb(int n,int r); /計算排列函數(shù)，傳入?yún)?shù)數(shù)組規(guī)模大小n，排列的規(guī)模大小r，輸出排列結(jié)果。5、 詳細代碼#include <stdio.h>#include <iostream>#define N 100using namespace std;int aN; /暫存結(jié)果數(shù)組，排列void comb(int n,int r)int i,j; i=0;ai=1;do if(ai-i<=n-r+1)/*還可以向前試探*/ if

5、(i=r-1)/*已找到一個組合*/ for (j=0;j<r;j+) cout<<aj;cout<<endl;ai+; continue;i+;ai = ai-1 + 1; /*向前試探*/ else if (i=0) return;/*已找到所有解*/ a-i+; /*回溯*/while (1);int main()int n,r;cin>>n>>r;comb(n,r);return 0;6、 測試數(shù)據(jù)和相應的實驗結(jié)果Input:3 21 2 3 Output:1 21 32 3 7、 思考題1、 在3×3個方格的方陣中要填入

6、數(shù)字1到N（N10）內(nèi)的某9個數(shù)字，每個方格填一個整數(shù)，似的所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。試求出所有滿足這個要求的各種數(shù)字填法。答：# include <stdio.h># define N 12void write(int a ) int i,j; for (i=0;i<3;i+) for (j=0;j<3;j+) printf("%3d",a3*i+j); printf("n"); scanf("%*c"); int bN+1;int a10;int isprime(int m) int i;in

7、t primes=2,3,5,7,11,17,19,23,29,-1; if (m=1|m%2=0) return 0; for (i=0;primesi>0;i+) if (m=primesi) return 1; for (i=3;i*i<=m;) if (m%i=0) return 0; i+=2; return 1; int checmatrix 3= -1,0,-1,1,-1,0,-1,1,3,-1, 2,4,-1,3,-1,4,6,-1,5,7,-1;int selectnum(int start) int j; for (j=start;j<=N;j+) if

8、(bj) return j; return 0; int check(int pos) int i,j; if (pos<0) return 0; for (i=0;(j=checmatrixposi)>=0;i+) if (!isprime(apos+aj) return 0; return 1; int extend(int pos) a+pos=selectnum(1); bapos=0; return pos; int change(int pos) int j; while (pos>=0&&(j=selectnum(apos+1)=0) bapos

9、-=1; if(pos<0) return -1; bapos=1; apos=j; bj=0; return pos;void find() int ok=0,pos=0; apos=1; bapos=0; doif (ok) if (pos=8) write(a);pos=change(pos); else pos=extend(pos); else pos=change(pos); ok=check(pos); while (pos>=0); void main() int i; for (i=1;i<=N;i+) bi=1; find();（1）4,9,81,2,36

10、,11,16（2） 1,2,54,3,87,10,9(3)2,1,45,6,78,11,122、試針對0/1背包問題設(shè)計回溯算法，比較與子集和數(shù)問題的算法差異。答：0/1背包問題是子集樹，是滿二叉樹，而子集和數(shù)問題是排列樹。就以本實驗的題目來說，兩者解空間構(gòu)成的樹如下：0/1背包問題 解空間樹：ai表示第i件物品，邊0表示不放入背包，邊1表示放入背包子集和數(shù)問題 解空間樹：ai表示第i個數(shù)，從根節(jié)點到葉節(jié)點表示一個排列3、求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。思考題可選做一個。答：一個合適的解應是在每列、每行上只有一個皇后，且一條斜線上也只有一個

11、皇后。求解過程從空配置開始。在第1列至第m列為合理配置的基礎(chǔ)上，再配置第m+1列，直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置，希望獲得下一個解。另外，在任一列上，可能有n種配置。開始時配置在第1行，以后改變時，順次選擇第2行、第3行、直到第n行。當?shù)趎行配置也找不到一個合理的配置時，就要回溯，去改變前一列的配置。為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個工作數(shù)組：（1） 數(shù)組a ，ak表示第k行上還沒有皇后；（2） 數(shù)組b ，bk表示第k列右高左低斜線上沒有皇后；（3） 數(shù)組 c ，ck表示第k列左高右低斜線上沒有皇后；棋盤中同一右高左低斜線上的方格，他們的行號

12、與列號之和相同；同一左高右低斜線上的方格，他們的行號與列號之差均相同。 初始時，所有行和斜線上均沒有皇后，從第1列的第1行配置第一個皇后開始，在第m列colm行放置了一個合理的皇后后，準備考察第m+1列時，在數(shù)組a 、b 和c 中為第m列，colm行的位置設(shè)定有皇后標志；當從第m列回溯到第m-1列，并準備調(diào)整第m-1列的皇后配置時，清除在數(shù)組a 、b 和c 中設(shè)置的關(guān)于第m-1列，colm-1行有皇后的標志。一個皇后在m列，colm行方格內(nèi)配置是合理的，由數(shù)組a 、b 和c 對應位置的值都為1來確定。得到求解皇后問題的算法如下：# include <stdio.h># includ

13、e <stdlib.h># define MAXN 20int n,m,good;int colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1; void main() int j; char awn; printf("Enter n: "); scanf("%d",&n); for (j=0;j<=n;j+) aj=1; for (j=0;j<=2*n;j+) bj=cj=1; m=1; col1=1; good=1; col0=0; do if (good) if (m=n) printf("列t行"); for (j=1;j<=n;j+) printf("%3dt%dn",j,colj); printf("Enter a character (Q/q for exit)!n"); scanf("%c",&awn); if (awn='Q'|awn='q') exit(0)