最佳调度的回溯算法.doc

实验目的：理解回溯法的原理，掌握调度问题的处理方法，实现最佳调度问题的回溯解决。问题定义输入：1. 任务数N2. 机器数M3. 随机序列长度ti,其中ti=x表示第i个任务完成需要时间单位x，输出：1. 开销时间besttime，表示最佳调度需要时间单位2. 最佳调度序列bestx，其中bestxi=x，表示将第i个任务分配给第x个机器执行。实验思想解空间的表示：一个深度为N的M叉树。基本思路：搜索从开始结点（根结点）出发，以DFS搜索整个解空间。每搜索完一条路径则记录下besttime 和bestx序列开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。测试数据及结果本测试的硬件以及软件环境如下CPU：PM 1.5G; 内存:768M;操作系统：windows xp sp2;软件平台：JDK1.5;开发环境：eclipse 如图1所示：即为求任务数为10机器数为5的最佳调度的算法结果。图1实验结论以及算法分析通过测试证明算法正确有效。性能分析的方法：使用JDK 1.5的System.nanoTime()，计算算法消耗的时间，以此来评价算法。（该方法在JDK1.5以下的版本中不支持）为了不影响算法的准确度，在测试的过程我们注释掉了打印随机字符串的步骤。由于没有使用限界函数进行优化，算法时间和空间复杂度呈指数级增长。所以该算法不适合较大规模的计算。 图2图2 蓝线表示机器数一定M=3时，n增大时求解最佳调度对所消耗的时间，该趋势随着指数增加。图3图3表示任务数N一定时随着M的增大的增长曲线。图2和图3表明该程序的时间复杂度与理论分析相符合。源代码最佳调度的回溯算法(java描述）BestSchedule.Java packagebestSchedule;importjava.util.Random;publicclassBestSchedule./*/*authoricyfire*本程序是采用回溯法解决最佳调度问题*/intN;/任务数intM;/机器数intbest;/最优值intt;/每个任务所需的时间序列intlen;/每台机器所需时间序列intx;/当前路径intbestx;/最优调度：其中bestxi=m表示把第i项任务分配给第m台机器 publicstaticvoidmain(Stringargs).BestSchedulebs=newBestSchedule(); /进入主方法,那就先创建一个对象；bs.showTest(); /然后，就开始调用自己的方法，开始求解吧！voidshowTest().N=3 /为了简单点就先小点吧。N=10;/任务数M=2 /同上，M=7;/机器数目Randomr=newRandom(); /java果真比较狠，连个随机数都是一个类的对象！t=newintN;/每个任务的时间/intsum=0;for(inti=0;iN;i+).ti=r.nextInt(5*N); /这个会是什么东西呢，噢，是随机的给每个任务分配 /时间。天，不带这么玩的吧！/sum+=ti;len=newintM;/记录每台机器已经安排的时间best=Integer.MAX_VALUE; /这又是一个狠招啊，直接将整型的最大值赋给best。 /跨平台.bestx=newintN;x=newintN;LongstartTime=System.nanoTime(); /不就是拿系统当前时间当做开始时间吗！ /哎，搞得这么复杂。backtrack(0); /开始调用回溯方法啦！从0开始！LongendTime=System.nanoTime(); /好吧，记录结束时间。 /下面的代码将所有得到的信息进行输出。System.out.println(Totletimeis+(endTime-startTime)+ns);！System.out.println(besttime:);System.out.println(best);System.out.println(eachjobcosts:);for(inti=0;iN;i+)System.out.print(ti+);System.out.println( bestschedule:);for(inti=0;iN;i+)System.out.print(bestxi+);/回溯搜索voidbacktrack(intdep). if(dep=N) /如果dep=N的话，证明又有一条更优的路径找到了！应该是.inttmp=comp(); /然后算一下走这条路径所需要的时间。if(tmpbest) /如果时间比当前的最有时间小的话，对当前的最有时间以及. /其对应的路径进行更新！best=tmp; /这里更新当前的最优时间；for(inti=0;iN;i+) /这里更新当前的最优路径。.bestxi=xi;return; /然后返回！ /那么，如果dep！=N呢，就是还没有找到一条完整的路径。好吧，接着找下一个节 /点吗? 暂时不清楚，接着往下看。for(inti=0;iM;i+) /对所有的机器进行遍历！一个机器一个机器的来。.leni+=tdep; /好吧，当前机器的工作时间又要增加了。同情！xdep=i+1; /当前路径的第dep层，应该是i吧，怎么变成i+1了呢，好吧， /一会再说！。这个地方吗，应该是编号和机器好差1.if(lenibest) /应该是总时间吧，还是leni呢，好奇怪！. /知道了，这里