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

回溯法

姓 名： 专 业 班 级： 学 号： 指导教师： 完成日期：

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 3 机器2 1 1 作业3 要求输出： 1、最佳完成时间 2、最佳调度方案 提示

2 3 提示：算法复杂度为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

#define NUM 8 //定义数组大小int a[NUM + 1]; int main () {

int a[100]; int number; int i; int k; int flag; int notfinish = 1;

int count = 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 }

else if (i == 1 && a[i] == NUM) {

notfinish = 0; //当第一位的值达到NUM时结束 } else {

a[i]++; //将a［i］的值取下一个值 }

}

else if (a[i] == NUM) { a[i] = 1; } else {

a[i]++; //将a［i］的值取下一个值 } }

else if (++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]:\

for (k = 1; k <= NUM; k++) //输出结果 { printf (\" %d\

} if (a[NUM - 1] < NUM) //修改倒数第二位的值 {

a[NUM - 1]++; } else {

a[NUM - 1] = 1;

} i = NUM - 1; //开始寻找下一个满足条件的解 }}//while printf (\"\\n\"); return 0; }

(2) 批处理作业调度 import java.util.*; public class FlowShop {

static int n; //作业数

static int f1; //机器1完成处理时间 static int f; //完成时间和 static int bestf; //当前最优值

static int[][] m; //各作业所需要的处理时间 static int[] x; //当前作业调度 static int[] bestx; //当前最优作业调度 static int[] f2; //机器2完成处理时间

public static void trackback(int i) { if (i == n) {

for (int j = 0; j < n; j++) { bestx[j] = x[j];

} bestf = f; } else {

for (int j = 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]; } } }

private static void swap(int[] x, int i, int j) { int temp = x[i]; x[i] = x[j]; x[j] = temp; }

private static void test() { n = 3;

int[][] testm = {{2, 1}, {3, 1}, {2, 3}}; m = testm;

int[] testx = {0, 1, 2}; x = testx;

bestx = new int[n]; f2 = new int[n]; f1 = 0; f = 0;

bestf = Integer.MAX_VALUE;

trackback(0);

System.out.println(Arrays.toString(bestx)); System.out.println(bestf); }

public static void main(String[] args) { test();

System.out.println(\"Hello World!\"); } }

(3) 数字全排列问题 #include \"stdio.h\" #include \"conio.h\" int num,cont=0; main()

{ int i,n,a[30];

printf(\"enter N :\"); scanf(\"%d\ for(i=1;i<=num;i++) a[i]=i; perm(a,1); printf(\"\\n%d\ getch(); }

int perm(int b[], int i) {int k,j,temp; if(i==num)

{for(k=1;k<=num;k++) printf(\"%d \ printf(\"\\"); 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); }

六、实验结果与思想

这次的实验是回溯法，我也对回溯法有了一个基本印象，所谓回溯法，就是把所有的可行解都遍历一遍，遇到不可行的就回溯到上一步，然后通过添加约束条件和限界条件就可以得到最优解。