算法分析与设计实验报告--回溯法.doc

《算法分析与设计实验报告--回溯法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验报告完成日期：20011.12.8一﹑实验题目回溯算法实验二、实验目的(1)掌握回溯算法思想(2)掌握回溯递归原理(3)了解回溯法典型问题三、实验内容(1)编写一个简单的程序，解决8皇后问题(2)批处理作业调度[问题描述]给定n个作业的集合J=(J1,J2,…,Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器i的处理时间为tji，i=1,2,…,n;j=1,2。对于个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。则所有作业在机器2上完成

2、处理的时间和成为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。要求输入：1、作业数2、每个作业完成时间表：作业完成时间机器1机器2作业121作业231作业323要求输出：1、最佳完成时间2、最佳调度方案提示提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。（3）数字全排列问题：任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。注意：数字不能重复，N

3、由键盘输入（N<=9）。四、算法思想分析1.8皇后问题回溯法分析：(1)从空棋盘起，逐行放置棋子。(2)每在一个布局中放下一个棋子，即推演到一个新的布局。(3)如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。其中存储结构：(1)二维数组A[N][N]存储皇后位置若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。(2)一维数组M[k]、L[k]、R[k]分别表示竖列、左斜线、右斜线是否放有棋子有则值为1,否则值为0。2.批处理作业调度思想分析：批处理作业调度问题要从n个作业的所有排列中找出有最小完成时间和的作

4、业调度，所以批处理作业调度的解空间是一棵排列树。五﹑算法源代码及用户屏幕1.8皇后问题#include;usingnamespacestd;#defineN8/*N为皇后个数*/intcount=0;intM[N]={0},L[2*N]={0},R[2*N]={0};intA[N][N]={0};/*皇后位置*/voidprint(intA[N][N]);intmytry(inti,intM[N],intL[2*N],intR[2*N],intA[N][N]);voidmain(){intn=mytry(0,M,L,R,A);

5、//代表从0行开始试探cout<<"count="<

6、,R,A);//试探下一行A[i][j]=0;/*去皇后*/M[j]=L[i-j+N]=R[i+j]=0;}returncount;}voidprint(intA[N][N])/*输出*/{inti,j;for(i=0;iusingnamespacestd;#defineN3//作业数目#defineMAX1000intx[N+1]={0,1,2,3};intm[3][N+1

7、]={0,0,0,0,0,2,3,2,0,1,1,3};intbestx[N+1];//用于保存结果调度顺序intf2[N+1];//第i阶段机器2完成处理的时间intf1=0;//机器1完成处理时间intf=0;//当前完成时间和intbestf=MAX;voidswap(int&a,int&b){inttemp=a;a=b;b=temp;}voidBacktrace(intt){if(t>N){bestf=f;for(inti=1;i<=N;i++){bestx[i]=x[i];}}else{for(inti=t;i<=N;i++){f1+=

8、m[1][x[i]];f2[t]=(f2[t-1]>f1?f2[t-1]:f1)+m[2][x[i]];f+=f2[t];swap(x[