实验6---子集和问题的回溯算法设计与实现(报告)

实验6 子集和问题的回溯算法设计与实现一、实验目的1、掌握回溯法解题的基本思想；2、掌握回溯算法的设计方法；3、针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。二、实验内容1、认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；2、了解子集和数问题及解向量的定长和变长状态空间表示；3、针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；4、分析深度优先扩展状态空间树节点或回溯的条件；5、分析和设计生成解向量各分量可选值的实现方法；6、设计和编制回溯算法的递归和迭代程序。【实验题】：组合数问题：找出从自然数1，2，n中任取r个数的所有组合。3、 算法的原理方法回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。可以采用回溯法找问题的解，将找到的组合以从小到大顺序存于a0，a1，ar-1中，组合的元素满足以下性质：（1）ai+1ai，后一个数字比前一个大；（2）ai-i=n-r+1。按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a2上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a2回溯到a1，这时，a1=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a0再回溯时，说明已经找完问题的全部解。4、 实验程序的功能模块void comb(int n,int r); /计算排列函数，传入参数数组规模大小n，排列的规模大小r，输出排列结果。5、 详细代码#include #include #define N 100using namespace std;int aN; /暂存结果数组，排列void comb(int n,int r)int i,j; i=0;ai=1;do if(ai-i=n-r+1)/*还可以向前试探*/ if (i=r-1)/*已找到一个组合*/ for (j=0;jr;j+) coutaj;coutnr;comb(n,r);return 0;6、 测试数据和相应的实验结果Input:3 21 2 3 Output:1 21 32 3 7、 思考题1、 在33个方格的方阵中要填入数字1到N（N10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。答：# include # define N 12void write(int a ) int i,j; for (i=0;i3;i+) for (j=0;j0;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 (bj) return j; return 0; int check(int pos) int i,j; if (pos=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-=1; if(pos=0); void main() int i; for (i=1;i=N;i+) bi=1; find();（1）4,9,81,2,36,11,16（2） 1,2,54,3,87,10,9(3)2,1,45,6,78,11,122、试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。答：0/1背包问题是子集树，是满二叉树，而子集和数问题是排列树。就以本实验的题目来说，两者解空间构成的树如下：0/1背包问题 解空间树：ai表示第i件物品，边0表示不放入背包，边1表示放入背包子集和数问题 解空间树：ai表示第i个数，从根节点到叶节点表示一个排列3、求出在一个nn的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。思考题可选做一个。答：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：（1） 数组a ，ak表示第k行上还没有皇后；（2） 数组b ，bk表示第k列右高左低斜线上没有皇后；（3） 数组 c ，ck表示第k列左高右低斜线上没有皇后；棋盘中同一右高左低斜线上的方格，他们的行号与列号之和相同；同一左高右低斜线上的方格，他们的行号与列号之差均相同。 初始时，所有行和斜线上均没有皇后，从第1列的第1行配置第一个皇后开始，在第m列colm行放置了一个合理的皇后后，准备考察第m+1列时，在数组a 、b 和c 中为第m列，colm行的位置设定有皇后标志；当从第m列回溯到第m-1列，并准备调整第m-1列的皇后配置时，清除在数组a 、b 和c 中设置的关于第m-1列，colm-1行有皇后的标志。一个皇后在m列，colm行方格内配置是合理的，由数组a 、b 和c 对应位置的值都为1来确定。得到求解皇后问题的算法如下：# include # include # 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); while (colm=n) m-; acolm=b