当前位置:首页 >> 计算机软件及应用 >>

最佳调度的回溯算法


实验目的:
理解回溯法的原理,掌握调度问题的处理方法,实现最佳调度问题的回溯解 决。

问题定义
输入: 1. 2. 3. 输出: 1. 2. 开销时间 besttime,表示最佳调度需要时间单位 最佳调度序列 bestx[],其中 bestx[i]=x,表示将第 i 个任务分配给 第 x 个机器执行。 任务数 N 机器数 M 随机序列长度 t[i],其中 t[i]=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
package bestSchedule;

import java.util.Random;

public class BestSchedule {

/** * @author icyfire * 本程序是采用回溯法解决最佳调度问题 * */

int N; int M; int best; int[] t; int[] len; int[] x;

//任务数 //机器数 //最优值 //每个任务所需的时间序列 //每台机器所需时间序列 //当前路径

int[] bestx; //最优调度:其中 bestx[i]=m 表示把第 i 项任务分配给第 m 台机器

public static void main(String[] args) { BestSchedule bs =new BestSchedule(); //进入主方法,那就先创建一个对象; bs.showTest(); } //然后,就开始调用自己的方法,开始求解吧!

void showTest() { N=3 //为了简单点就先小点吧。。。N=10; // 任务数 M=2 //同上,M=7; //机器数目 Random r =new Random(); t=new int [N]; //每个任务的时间 //int sum=0; for (int i =0;i<N;i++) { t[i]=r.nextInt(5*N); //这个会是什么东西呢, 噢, 是随机的给每个任务分配 //时间。天,不带这么玩的吧! //sum+=t[i]; } len =new int [M]; //记录每台机器已经安排的时间 //java 果真比较狠,连个随机数都是一个类的对象!

best = Integer.MAX_VALUE;

//这又是一个狠招啊, 直接将整型的最大值赋给 best。 //跨平台.

bestx=new int [N]; x =new int[N]; Long startTime = System.nanoTime(); //不就是拿系统当前时间当做开始时间吗!

//哎,搞得这么复杂。 backtrack(0); //开始调用回溯方法啦!从 0 开始! //好吧,记录结束时间。

Long endTime = System.nanoTime();

//下面的代码将所有得到的信息进行输出。 System.out.println("Totle time is " + (endTime - startTime) + " ns");! System.out.println("best time:"); System.out.println(best); System.out.println("each job costs:"); for (int i=0;i<N;i++) System.out.print(t[i]+" "); System.out.println(" best schedule:"); for (int i=0;i<N;i++) System.out.print(bestx[i]+" "); }

//回溯搜索 void backtrack (int dep) { if (dep==N) { int tmp = comp(); //然后算一下走这条路径所需要的时间。 if(tmp<best) { best=tmp; //如果时间比当前的最有时间小的话,对当前的最有时间以及 //其对应的路径进行更新! //这里更新当前的最优时间; //如果 dep==N 的话,证明又有一条更优的路径找到了!应该是

for(int i=0;i<N;i++) //这里更新当前的最优路径。 { bestx[i]=x[i]; } } return; } //那么,如果 dep!=N 呢,就是还没有找到一条完整的路径。好吧,接着找下一个节 //点吗? 暂时不清楚,接着往下看。 for(int i=0;i<M;i++) //对所有的机器进行遍历!一个机器一个机器的来。 //然后返回!

{ len[i]+=t[dep]; x[dep]=i+1; //好吧,当前机器的工作时间又要增加了。同情! //当前路径的第 dep 层,应该是 i 吧,怎么变成 i+1 了呢,好吧, //一会再说!。。这个地方吗,应该是编号和机器好差 1. if(len[i]<best) { //应该是总时间吧,还是 len[i]呢,好奇怪! //知道了,这里的总时间是执行时间最长的那个机器的时间。 backtrack(dep+1); } len[i]-=t[dep]; } } //那么就去找下一层的吧。

//计算完成任务的时间 int comp() { int tmp =0; for (int i=0;i<M;i++) //这里吗,计算完成时间是执行时间最长的机器的运行时间!! { if(len[i]>tmp) { tmp=len[i]; } } return tmp;

}

}


赞助商链接
相关文章:
更多相关标签: