最佳调度问题 回溯算法分析.docx

《算法设计与分析》上机报告

姓名： 张先荣 学号： S日期： 2016/12/20

上机题 实验七：最佳调度问题(回溯算法)目：

实验环境：

CPU:coreI7 ; 内存: 8G ;操作系统:Win10 ;软件平台 Visualstudio2013 ;

一、算法设计与分析：

题目:

最佳调度问题(回溯算法)

设有n个任务由m个可并行工作的机器来完成，完成任务i需要时间为ti。试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。

算法思想：

解空间的表示：

一个深度为N的M叉树。intN;//任务数

intM;//机器数intbest;//最优值

int[]t;//每个任务所需要的时间序列int[]len;//每台机器所需要的时间int[]x;//当前路径

int[]bestx;//最优调度基本思路：

1、搜索从开始结点（根结点）出发，以DFS搜索整个解空间。

2、每搜索完一条路径则记录下t和best序列，开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个

新结点，

并成为一个新的活结点，也成为当前扩展结点。

3、如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展

结点；直至找到一个解或全部解。

二、核心代码：

如图所示，即为回溯算法，以深度优先遍历方式遍历解空间树，每次向下遍历一层，意味着记录一次任务的完成序列。Len加上任务序列的时间T，如果不是最优的，回溯，len减去任务的序列时间T

计算任务完成的时间。某个机器时间最大，则他就是任务结束的时间。

解空间如图。在这个图中能清晰地说明问题。3叉树，机器数为3.深度为4，总共4层，则任务数为4，用3台机器去调度4个任务，把这棵树深度遍历，最后选出最优值。

三、结果与分析：

题目一:

如图所示，当任务数为10，机器数为7，总共耗时34.0782ms，最有时间为

95单位时间，每个任务所花费时间就是随机数生成的时间序列是：67，45，80，

32，59，95，37，46，28，20.机器调度顺序是1，2，3，2，4，5，6，6，1，

4

如图所示，当任务数为20，机器数为2，总共耗时18.2999ms，最有时间为

474单位时间，每个任务所花费时间就是随机数生成的时间序列是：73，31，66，

7，50，9，11，53，66，90，99，12，37，31，31，38，9，82，60，93.

如图所示，当任务数为20，机器数为4，总共耗时57835.5837ms，

总结：

当任务数大于20，机器数大于5时，系统崩溃，所以回溯算法的时间复杂度较大。

算法源代码（C#描述）

publicclassBestSchedule

{

附录（源代码）

intN;//任务数intM;//机器数intbest;//最优值

int[]t;//每个任务所需要的时间序列int[]len;//每台机器所需要的时间int[]x;//当前路径

int[]bestx;//最优调度publicvoidshowTest()

{

N=20;

M=5;

Randomr=newRandom();t=newint[N];//每个任务的时间for(inti=0;iN;i++)

{

t[i]=r.Next(1,100);//随机数生成每个任务所需要的时间

}

len=newint[M];//记录每台机器已安排的时间best=9999999;

bestx=newint[N];x=newint[N];

Stopwatchsw=newStopwatch();sw.Start();

backtrack(0);

sw.Stop();

TimeSpants2=sw.Elapsed;Console.WriteLine(程序运行总共花费{0}ms.,

ts2.TotalMilliseconds);

Console.WriteLine(最优时间是：);Console.Write(best+);

Console.WriteLine(每个任务所花费的时间是：);for(inti=0;iN;i++)

{

Console.Write(t[i]+ );

}

Console.WriteLine();Console.WriteLine(最佳调度序列是：);for(inti=0;iN;i++)

{

Console.Write(b