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

1、算法设计与分析上机报告姓名：张先木学号：SA16225439日期：2016/12/20上机题目：实验七：最佳调度问题（回溯算法）实验环境：CPU:coreI7 ;内存： 8G;操作系统:Win10;软件平台 Visualstudio 2013;一、算法设计与分析：题目：最佳调度问题（回溯算法）设有n个任务由m个可并行工作的机器来完成，完成任务i需要时间为ti。 试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。算法思想：解空间的表示：一个深度为N的M叉树。int N;/任务数int M;/机器数int best;/最优值int口 t;/每个任务所需要的时间序列int口 len

2、;/每台机器所需要的时间int口 x;/当前路径int口 bestx;/最优调度基本思路：1、搜索从开始结点（根结点）出发，以DFS搜索整个解空间。2、每搜索完一条路径则记录下t和best序列，开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个 新结点，并成为一个新的活结点，也成为当前扩展结点。3、如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成 为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当 前的扩展结点；直至找到一个解或全部解。二、核心代码：1.如图所示，即为回溯算法，以深度优先遍历方式遍历解空间树，每次向下

3、 遍历一层，意味着记录一次任务的完成序列。Len加上任务序列的时间T，如果 不是最优的，回溯，len减去任务的序列时间T土 I七1用void backtrack tint dep)(if (dep = N)(int tup = coup ();if (trip best)best = tup;for tint i = 0; i N; i十十)bests i = kl:return;for (int i = 0; i M; i+)leni += tdep;xdep -i+1;if (lenEi best)(backtrack(dep + 1);)lenEi -= tEdep:2.计算任务完成的时

4、间。某个机器时间最大，则他就是任务结束的时间。* 18斜第技或大孕计算完成任务的时间1个引用int conj) 0(int teirg - 0:fox (int i = 0; i tenp)Itemp = leni:return tE皿；3.解空间如图。在这个图中能清晰地说明问题。3叉树，机器数为3.深度为4, 总共4层，则任务数为4,用3台机器去调度4个任务，把这棵树深度遍历，最 后选出最优值。三、结果与分析:题目一：中国斜革成*大家如图所示，当任务数为20,机器数为4,总共耗时57835.5837ms,总结：当任务数大于20，机器数大于5时，系统崩溃，所以回溯算法的时间复杂 度较大。算法源

5、代码（C#描述）public class BestScheduleint N;/任务数int M;/机器数附录（源代码）int best;/最优值int口 t;/每个任务所需要的时间序列int口 len;/每台机器所需要的时间int口 x;/当前路径int口 bestx;/最优调度public void showTest（）N = 20;M = 5;Random r = new Random();t=new intN;/每个任务的时间 for (int i = 0; i N; i+) ti = r.Next(1,100);/随机数生成每个任务所需要的时间 len=new intM;/记录每台机

6、器已安排的时间 best = 9999999;bestx = new intN;x = new int N;Stopwatch sw = new Stopwatch (); sw.Start();backtrack(0);sw.Stop();TimeSpan ts2 = sw.Elapsed;Console.WriteLine(程序运行总共花费0ms.”, ts2.TotalMilliseconds);Console.WriteLine(最优时间是：)；Console.Write(best+);Console.WriteLine(每个任务所花费的时间是：)； for (int i = 0; i

7、 N; i+) Console.Write(ti + );Console.WriteLine();Console.WriteLine(最佳调度序列是：)； for (int i = 0; i N; i+) Console.Write(bestxi + );Console.ReadKey();void backtrack(int dep)if (dep = N)int tmp = comp(); if (tmp best) best = tmp;for (int i = 0; i N; i+) bestxi = xi;return;for (int i = 0; i M; i+)leni += tdep;xdep = i + 1;if (leni best)backtrack(dep + 1);leni -= tdep;/计算完成任务的时间int comp()int temp = 0;for (int i = 0; i temp)tem