《算法设计与分析》实验报告5

 

实验名称: 作业调度问题

系    别:xxx           

专    业:xxx           

班    级:xxx

姓    名:xxx          

学    号:xxx

实验日期:xx年xx月xx日

1.  算法题目

根据回溯法的设计思想和算法步骤，要求学生设计一个回溯算法，用于解决作业调度的问题。作业调度问题，作为经典的组合问题，需要考虑所有任务的全排列。带有回溯的递归调用，可以在中间环节中发现回溯后的后续操作是否还有必要继续进行的可能性，从而实现剪枝，减少搜索n!空间的范围。因此带回溯的搜索算法可以解决该问题，至少在时间效率上有很大的提高。

 

2.  设计思路与步骤

答：1 初始化变量X[i]

 2 设置解空间的第一个位置的值

3 对每一个x属于Sk 循环执行下列操作 k>=1

  3.1 Xk=x

  3.2 将Xk加入X

  3.3 if(X是最终解) 输出结果bestTime

  3.4 if(X是部分解) 填写下一个位置 k = k + 1;

  3.5 else 回溯，恢Xk和k:x[k] = -1; k = k - 1;   

 

3.  算法实现与代码

 

#include<stdio.h>

//const int n = 3;

#define N 3

int BatchJob(int a[], int b[], int n);

 

int main()

{

int a[N] = { 2, 5, 4 }, b[N] = { 3, 2, 1 };

int bestTime = BatchJob(a, b, 3);

printf("最短作业时间是：%d\n", bestTime);

return 0;

}

 

int BatchJob(int a[], int b[], int n)

{

int i, j, k;

int x[10], sum1[10], sum2[10];

int bestTime = 1000;                     //假定最后完成时间不超过1000

for (i = 1; i <= n; i++)

{

x[i] = -1;

sum1[i] = 0;

sum2[i] = 0;

}

sum1[0] = 0; sum2[0] = 0;

k = 1;

while (k >= 1)

{

x[k] = x[k] + 1;

while (x[k] < n)

{

for (i = 1; i < k; i++)       //检测作业x[k]是否重复处理

if (x[i] == x[k])

break;

if (i == k) {              //作业x[k]尚未处理

sum1[k] = sum1[k - 1] + a[x[k]];

if (sum1[k] > sum2[k - 1]) sum2[k] = sum1[k] + b[x[k]];

else sum2[k] = sum2[k - 1] + b[x[k]];

if (sum2[k] < bestTime)

break;

else

x[k] = x[k] + 1;//剪枝

}

else x[k] = x[k] + 1;             //作业x[k]已处理

}

if (x[k] < n && k == n)        //得到一个作业安排

if (bestTime > sum2[k]){

bestTime = sum2[k];

printf("最短的作业安排是：");

for (j = 1; j <= n; j++)

printf("%d ",x[j] + 1);

////数组下标从0开始，打印作业编号从1开始

}

 

if (x[k] < n && k < n)

k = k + 1;                     //是解的子集，安排下一个作业

else {  

x[k] = -1; k = k - 1;             //重置x[k]，回溯

}

}

return bestTime;

}

 

4.  测试用例与结果

 

5.  问题与总结

答：xxx。