最佳调度的回溯算法的实验

1、实验目的:理解回溯法的原理，掌握调度问题的处理方法，实现最佳调度问题的回溯解 决。问题定义输入：1. 任务数n2. 机器数m3. 随机序列长度ti,其中ti=x表示第i个任务完成需要时间单位x, 输出：1. 开销时间besttime,表示最佳调度需要时间单位2. 最佳调度序列bestx,其屮bestxi=x,表示将第i个任务分配给 第x个机器执行。实验思想解空间的表示：一个深度为n的m叉树。基本思路：搜索从开始结点（根结点）出发，以dfs搜索整个解空间。毎搜索完一条路径则记录下besttime和bestx序列开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结 点处向纵深方向移至

2、一个新结点，并成为一个新的活结点，也成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死 结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当 前的扩展结点；直至找到一个解或全部解。测试数据及结果本测试的硬件以及软件环境如下cpu： pm 1.5g;内存:768m;操作系统：windows xp sp2;软件平台：jdk2.5;开 发环境：eclipse如图1所示：即为求任务数为10机器数为5的最佳调度的算法结果。j bestschedule. javaqio bestschedule2. classjj i£s. javapubl

3、ic static void main(string args) bestschedule bs =ne< best schedule ();bs. showtest ():void showtest 0|n=10; /任务数m=5： 机器数目random r =ner random ():t=new int n: /每个任务的时间/int sum=0;for (int i =0;i<n;i+)ti=r. nextint(5*n);/sum+=t i:len =ne» int m;"记录每台机器已经安排的时间best 二 integer.工炖肚： bestx=n

4、ev int n;x =nev int n:lon? st art time = svstem. nanotisseo :问题javadoc声明貝控制台属性进度凰其飒當騷出貝-冷已终止y muffmandemo swt 应用程序c:program filesjavajdkl. 5. obinjavaw. exe ( 2008-1-18 上午02:12:22)totle time is 13520155nsbesttime:40eachjob costs:8 19 6 18 18 34022 16bestschedule:1 1112 2 1344罔中d o.实验结论以及算法分析通过测试证明算法

5、正确有效。性能分析的方法：使用jdk1.5的，计算算法消耗的时间，以此 来评价算法。（该方法在jdk1. 5以下的版本中不支持）为了不影响算法的准确度，在测试的过程我们注释掉了打印随机字符串的步骤。由于没有使用限界函数进行优化，算法时间和空间复杂度呈指数级增长。所以该算法不适 合较大规模的计算。图2蓝线表示机器数一定m=3吋，n增人吋求解最佳调度对所消耗的吋间，该 趋势随着指数增加。n=10任务数一定n=10,随着机器数m增大图3图3表示任务数n 定时随着m的增大的增长曲线。图2和图3表明该程序的时间复杂度与理论分析相符合。源代码最佳调度的回溯算法（java描述）bestschedule ja

6、vapackage bestschedule;import java.util.random;日田public class bestschedule i白由 /*i * author icyfirei*木程序是采用回溯法解决最佳调度问题*/int n; /任务数int m; 机器数int best; 最优值int t； 每个任务所需的时间序列int len; 每台机器所需时间序列int x; 当前路径int bestx; 最优调度：其中bestxi=m表示把第i项任务分配给第m台机器白由 public static void main(string args) bestschedule bs

7、=new bestschedule(); 进入主方法，那就先创建一个对彖;bs.showtest();/然后，就开始调用自己的方法，开始求解吧！void showtest()白由i n=3 为了简单点就先小点吧。n=10;任务数i m=2 /同上，m=7;机器数目random r =new random();/java杲真比较狠，连个随机数都是一个类的对象!it=new int n; 每个任务的时间i/int sum=0;ifor (int i =0;i<n;i+)白由ti=r.nextlnt(5*n);/这个会是什么东西呢，噢，是随机的给每个任务分配/时间。天，不带这么玩的吧！/sum

8、+=ti;- i len =new int m;记录每台机器己经安排的时间best = lnteger.max_value; 这又是一个狠招啊，直接将整型的最大值赋给best。跨平台.ibestx=new int n;x =new intn;long starttime = system.nanotime(); 不就是拿系统当前时间当做开始时间吗！哎，搞得这么复杂。backtrack(o);/开始调用回溯方法啦！从0开始！long endtime = system.nanotime();/好吧，记录结束时间。下面的代码将所有得到的信息进行输岀。system.out.println(utotle

9、 time is " + (endtime - starttime) + " ns");!system.out.println(”best time:");system.out.pri ntln(best);system.out.println("each job costs:");i for (int i=0;i<n;i+)system.out.print(ti+n ");system.out.println(" best schedule:");i for (int i=0;i<n;i+)

10、isystem.out.print(bestxi+"");i i 回溯搜索void backtrack (int dep)白由iif (dep=n) 如果dep=n的话，证明又有一条更优的路径找到了 ！应该是白由iint tmp = comp(); 然后算一下走这条路径所需要的时间。iif(tmp<best)如果时间比当前的最有时间小的话，对当前的最有时间以及白由 其对应的路径进行更新！best=tmp; 这里更新当前的最优时间；ifor(int i=0;ivn;i+) /这里更新当前的最优路径。白由 ibestxi=xi;- - return;然后返回！-i /那么，如果dep!二n呢，就是述没有找到一条完整的路径。好吧，接着找下一个节 点吗？暂时不清楚，接着往下看。for(int i=0;i<m;i+)对所有的机器进行遍历！ 一个机器一个机器的来。ileni+=tdep; 好吧，当前机器的工作时间又要增加了。同情！xdep=i+1;当前路径的第dep层，应该是i吧，怎么变成i+1 了呢，好吧,一会再说！。这个地方吗，应该是编号和机器好差1iif(leni<best)应该是总时间吧，还是leni呢，好奇怪！白由知道了，这里的总时间是执行时间最长的那个机器的时间。ba