算法分析实验报告-回溯法

《算法设计与分析》实验报告回溯法姓名：XXX专业班级：XXX学号：XXX指导教师：XXX完成日期：XXX一、试验名称：回溯法写出源程序，并编译运行详细记录程序调试及运行结果二、实验目的掌握回溯算法思想掌握回溯递归原理了解回溯法典型问题三、实验内容编写一个简单的程序，解决8皇后问题批处理作业调度数字全排列问题四、算法思想分析编写一个简单的程序，解决8皇后问题批处理作业调度[问题描述]给定n个作业的集合J=(J1,J2,…,Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器i的处理时间为tji，i=1,2,…,n;j=1,2。对于一个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。则所有作业在机器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由键盘输入（N<=9）。五、算法源代码及用户程序编写一个简单的程序，解决8皇后问题N皇后问题代码1：#include<stdio.h>#defineNUM8//定义数组大小inta[NUM+1];intmain(){ inta[100];intnumber;inti;intk;intflag;intnotfinish=1;intcount=0;i=1;//正在处理的元素下标，表示前i－1个元素已符合要求，正在处理第i个元素a[1]=1;//为数组的第一个元素赋初值printf("Result:\n");while(notfinish)//处理尚未结束{while(notfinish&&i<=NUM)//处理尚未结束且还没处理到第NUM个元素{for(flag=1,k=1;flag&&k<i;k++)//判断是否有多个皇后在同一行{if(a[k]==a[i])flag=0;}for(k=1;flag&&k<i;k++)//判断是否有多个皇后在同一对角线{if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))flag=0;}if(!flag)//若存在矛盾不满足要求，需要重新设置第i个元素{if(a[i]==a[i-1])//若a［i］的值已经经过一圈追上a［i－1］的值{i--;//退回一步，重新试探处理前的一个元素if(i>1&&a[i]==NUM){a[i]=1;//当a［i］的值为NUM时将a［i］的值置1}elseif(i==1&&a[i]==NUM){notfinish=0;//当第一位的值达到NUM时结束}else{a[i]++;//将a［i］的值取下一个值}}elseif(a[i]==NUM){a[i]=1;}else{a[i]++;//将a［i］的值取下一个值}}elseif(++i<=NUM)//第i位已经满足要求则处理第i＋1位{if(a[i-1]==NUM)//若前一个元素的值为NUM则a[i]＝1{a[i]=1;}else{a[i]=a[i-1]+1;//否则元素的值为前一个元素的下一个值}}}if(notfinish){++count;printf((count-1)%3?"[%2d]:":"\n[%2d]:",count);for(k=1;k<=NUM;k++)//输出结果{printf("%d",a[k]);}if(a[NUM-1]<NUM)//修改倒数第二位的值{a[NUM-1]++;}else{a[NUM-1]=1;}i=NUM-1;//开始寻找下一个满足条件的解}}//whileprintf("\n");return0;}批处理作业调度importjava.util.*;publicclassFlowShop{staticintn;//作业数staticintf1;//机器1完成处理时间staticintf;//完成时间和staticintbestf;//当前最优值staticint[][]m;//各作业所需要的处理时间staticint[]x;//当前作业调度staticint[]bestx;//当前最优作业调度staticint[]f2;//机器2完成处理时间publicstaticvoidtrackback(inti){if(i==n){for(intj=0;j<n;j++){bestx[j]=x[j];}bestf=f;}else{for(intj=i;j<n;j++){f1+=m[x[j]][0];if(i>0){f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][1];}else{f2[i]=f1+m[x[j]][1];}f+=f2[i];if(f<bestf){swap(x,i,j);trackback(i+1);swap(x,i,j);}f1-=m[x[j]][0];f-=f2[i];}}}privatestaticvoidswap(int[]x,inti,intj){inttemp=x[i];x[i]=x[j];x[j]=temp;}privatestaticvoidtest(){n=3;int[][]testm={{2,1},{3,1},{2,3}};m=testm;int[]testx={0,1,2};x=testx;bestx=newint[n];f2=newint[n];f1=0;f=0;bestf=Integer.MAX_VALUE;trackback(0);System.out.println(Arrays.toString(bestx));System.out.println(bestf);}publicstaticvoidmain(String[]args){test();System.out.println("HelloWorld!");}}数字全排列问题#include"stdio.h"#include"conio.h"intnum,cont=0;main(){inti,n,a[30];printf("enterN:");scanf("%d",&num);for(i=1;i<=num;i++)a[i]=i;perm(a,1);printf("\n%d",cont);getch();}intperm(intb[],inti){intk,j,temp;

if(i==num){for(k=1;k<=num;k++)printf("%d",b[k]);printf("\t");cont++;}

elsefor(j=i