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

《最佳调度问题 回溯算法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、度优先遍历方式遍历解空间树，每次向下遍历一层，意味着记录一次任务的完成序列。Len加上任务序列的时间T，如果不是最优的，回溯，len减去任务的序列时间T2.计算任务完成的时间。某个机器时间最大，则他就是任务结束的时间。3.解空间如图。在这个图中能清晰地说明问题。3叉树，机器数为3.深度为4，总共4层，则任务数为4，用3台机器去调度4个任务，把这棵树深度遍历，最后选出最优值。三、结果与分析：题目一:如图所示，当任务数为10，机器数为7，总共耗时34.0782ms，最有时间为95单位时间，每个任务所花费时间就是随机数生成的时间序列是：67，45，80，32，59，95，

4、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

5、;//任务数intM;//机器数intbest;//最优值int[]t;//每个任务所需要的时间序列int[]len;//每台机器所需要的时间int[]x;//当前路径int[]bestx;//最优调度publicvoidshowTest(){N=20;M=5;Randomr=newRandom();t=newint[N];//每个任务的时间for(inti=0;i

6、t[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;i

7、iteLine();Console.WriteLine("最佳调度序列是：");for(inti=0;i