算法分析实验报告回溯法.docx
《算法分析实验报告回溯法.docx》由会员分享，可在线阅读，更多相关《算法分析实验报告回溯法.docx（11页珍藏版）》请在冰点文库上搜索。
算法分析实验报告回溯法
《算法设计与分析》实验报告
回溯法
姓名：
XXX
专业班级：
XXX
学号：
XXX
指导教师：
XXX
完成日期：
XXX
一、试验名称：
回溯法
（1）写出源程序，并编译运行
（2）详细记录程序调试及运行结果
二、实验目的
（1）掌握回溯算法思想
（2）掌握回溯递归原理
（3）了解回溯法典型问题
三、实验内容
（1）编写一个简单的程序，解决8皇后问题
（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上完成处理的时间和成为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。
要求输入：
1、作业数
2、每个作业完成时间表：
作业完成时间
机器1
机器2
作业1
2
1
作业2
3
1
作业3
2
3
要求输出：
1、最佳完成时间
2、最佳调度方案
提示
提示：
算法复杂度为O（n!
）,建议在测试的时候n值不要太大，可以考虑不要超过12。
（3）数字全排列问题：
任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。
如N=3时，共有以下6种排列方式：
123，132，213，231，312，321。
注意：
数字不能重复，N由键盘输入（N<=9）。
五、算法源代码及用户程序
（1）编写一个简单的程序，解决8皇后问题
N皇后问题
代码1：
#include
#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{
if（a[k]==a[i]）
flag=0;
}
for（k=1;flag&&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]{
a[NUM-1]++;
}
else
{
a[NUM-1]=1;
}i=NUM-1;//开始寻找下一个满足条件的解
}}//while
printf（"\n"）;
return0;
}
（2）批处理作业调度
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;jbestx[j]=x[j];
}
bestf=f;
}else{
for（intj=i;jf1+=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（fswap（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!
"）;
}
}
（3）数字全排列问题
#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++;
}
else
for（j=i;j<=num;j++）
{temp=b[i];b[i]=b[j],b[j]=temp;
perm（b,i+1）;
temp=b[i];b[i]=b[j],b[j]=temp;
}
return（0）;
}
六、实验结果与思想
这次的实验是回溯法，我也对回溯法有了一个基本印象，所谓回溯法，就是把所有的可行解都遍历一遍，遇到不可行的就回溯到上一步，然后通过添加约束条件和限界条件就可以得到最优解。
升级会员 