《最佳调度问题回溯算法分析》由会员分享，可在线阅读，更多相关《最佳调度问题回溯算法分析（10页珍藏版）》请在金锄头文库上搜索。
1、姓名：张先宋学号：SA16225439日期：2016/12/20上机题目:实验七：最佳调度问题（回溯算法）算法设计与分析上机报告实验环境：CPU:corel7 ;内存： 8G;操作系统：WinlO;软件平台 Visualstudio 2013;一、算法设计与分析：题目:-最佳调度冋题（回溯算法）设有n个任务由m个可并行工作的机器来完成，完成任务i需要时间为ti o 试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。算法思想：解空间的表示：一个深度为N的M叉树。int N;/任务数int M;/机器数int best;/最优值in t t;/每个任务所需要的时间序列in t l
2、e n;/每台机器所需要的时间in t x;/当前路径in t bestx;/最优调度基本思路：1 、搜索从开始结点（根结点）出发，以 DFS搜索整个解空间。2、每搜索完一条路径则记录下t和best序列，开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个 新结点，并成为一个新的活结点，也成为当前扩展结点。3、如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成 为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当 前的扩展结点；直至找到一个解或全部解。二、核心代码：1如图所示，即为回溯算法，以深度优先遍历方式遍历解空间树，
3、每次向下遍历一层，意味着记录一次任务的完成序列。Len加上任务序列的时间T,如果不是最优的，回溯，len减去任务的序列时间Tynid backtrackCint dep)if (dep = N)int tiqp = conp (); if (tnp best)best - tup; for (int i=D; i N; i+) bestsEi = xCi:returnfor (i.nt i = 0; i M； i+)leni tdep; idep =i + lF if (lenEi best)(backtr冕ckd巳p + 1); leni -= tdep;)2.计算任务完成的时间。某个机器时
4、间最大，则他就是任务结束的时间打计算完成任务的时间1个引用in亠 oiup ()int t&w = 0:ior (int i = 0； i teirj)temp - leni:Teturn te眄3.解空间如图。在这个图中能清晰地说明问题。 3叉树，机器数为3深度为4, 总共4层，则任务数为4,用3台机器去调度4个任务，把这棵树深度遍历，最 后选出最优值。三、结果与分析: 题目一：卅色“皿7硏玄生学习/W兒生刃上U叩tilt法蛙阳殆巧cZiZKe.tHhSlMb吨EXE-堆尹运彳丁岂芜？E呂昶4；置毗，*wm mt鮎毎牛任募崎狂耕的时怔島67 45 80 ；2 59 95 驚狎 20 绘替调反
5、呼.氏走：L23245at14如图所示，当任务数为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 Ale-硏玄生学习/W丸生字刃上厦口EXE-I哼主运打艺共花专IE F其陥$ 时间是I4?4母牛任势所迂輕前为间是：厲 31 箱丁冈 9 M 騎筛轉诃 12 37 31 31 滋 9 B2 閒附 门桂凋反序列毘：b 111 I I 1 L2 1222ZZ1222如图所示，当任务数为
6、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#描述)public class Bestscheduleint N; /任务数int M; /机器数附录（源代码）int t;/每个任务所需要的时间序列int
7、len;/每台机器所需要的时间int x;/当前路径int best; / 最优值int bestx; / 最优调度 public void showTest() N = 20;M = 5;|Randomr = new Randon();t= new int N; /每个任务的时间 for ( int i = 0; i N; i+)len=new int M; /记录每台机器已安排的时间best = 9999999;bestx =new int N;x =new int N;Stopwatch sw = new Stopwatch ();sw.Start();backtrack(O);sw.S
8、top();TimeSpa nts2 = sw.Elapsed;Console .WriteLine(程序运行总共花费0ms., ts2.TotalMilliseco nds);Con sole .WriteL in e(最优时间是：”)；Console .Write(best+ );Co nsole .WriteL in e(每个任务所花费的时间是：);for ( int i = 0; i N; i+)Con sole .WriteLi ne();Co nsole .WriteLi ne（最佳调度序列是：”）;for ( int i = 0; i N; i+)Con sole .Write(bestxi +);Con sole .ReadKey();if (dep = N)int tmp = comp();if (tmp best) |best = tmp;for ( int i = 0; i N; i+)return ;len i += tdep;xdep = i + 1;if (leni best)len i _= tdep;/计算完成任务的时间int comp()int temp = 0;for ( int i = 0; i temp)return temp;class Programstatic void Main( string args)
