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

最佳调度的回溯算法


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

问题定义
输入: 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;

}

}


相关文章:
最佳调度的回溯算法.doc
最佳调度的回溯算法 - 实验目的: 理解回溯法的原理,掌握调度问题的处理方法,实
最佳调度问题 回溯算法.doc
最佳调度问题 回溯算法_工学_高等教育_教育专区。最佳调度问题,回溯算法,中科大
最佳调度问题(回溯算法).doc
《算法设计与分析》上机报告姓名: 上机题目: 学号: 日期: 最佳调度问题(回溯算法) 实验环境: CPU: 2.10GHz ; 内存: 6G ; 操作系统:Win7 64 位 ;软件平台...
深度优先搜索与回溯算法_图文.ppt
深度优先搜索与回溯算法 - 深度优先搜索与回溯算法 回溯是计算机解题中常用算法
第5章 回溯法.ppt
学习要点 ? 理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架 (1)递归...易见,最佳调度方案是1, 3, 2, 其完成时间和为18。 tji 机器1 2 3 2 ...
算法第5章 回溯法_图文.ppt
算法第5章 回溯法 - 第5章 回溯法 ? 学习要点 ? 理解回溯法的深度优先搜索策略 ? 掌握用回溯法解题的算法框架 ? (1)递归回溯最优子结构性质 ? (2)迭代...
第五章 回溯算法_图文.ppt
河北金融学院 1 孟东霞 信息管理与工程系 5.1 回溯算法框架 5.2 装载问题 ...? F2i i ?1 n 批处理作业调度问题要求对于给定的 n 个 作业,制定最佳作业...
回溯算法批处理作业调度.doc
回溯算法批处理作业调度 批处理作业调度 回溯算法 2011-08-15 20:16:22|...批处理作业调度问题要求对于给定的 n 个作业,制定一个最佳的作业调度方案,使其...
算法第5章 回溯法_图文.ppt
算法第5章 回溯法 - 第5章 回溯法 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯最优子结构性质 (2)...
算法分析_回溯法(很不错).ppt
算法分析_回溯法(很不错)_计算机软件及应用_IT/计算机_专业资料。算法分析 回溯...易见, 最佳调度方案是1,3,2,其完成时间和为18。 批处理作业问题 ?解空间:...
第5章-回溯法-习题_图文.ppt
回溯 len[i] += t[dep]; //安排任务dep(左子树) if (len[i]<best) search(dep+1); len[i] -= t[dep]; //右子树 } } 19 最佳调度问题算法...
Lecture 06-回溯算法_图文.ppt
ldliu@ecust.edu.cn 华东理工大学 信息学院计算机系 Lecture 06 回溯算法 ? ?...易见,最佳调度方案是1,3,2,其完成时间和为 18。 ?解空间:排列树 void ...
0028算法笔记【回溯法】批作业调度问题和符号三角....doc
0028算法笔记【回溯法】批作业调度问题和符号三角形问题_天文/地理_自然科学...批处理作业调度问题要求对于给定的 n 个作业,制定最佳作业调度方案,使其完成时 ...
第6章 回溯算法_图文.ppt
第6章 回溯算法 - 第6章 回溯算法 6.1 回溯算法的理论基础 6.1.1 问题的解空间 6.1.2 回溯法的基本思想 6.1.3 子集树与排列树 6.2 流水作业调度...
算法思想之5回溯法.pdf
第5 章 回溯算法 5.1 回溯算法框架 5.2 装载问题 5.3 批处理作业问题 ...最佳调度方 案是1,3,2。 f=3+7+8=18 swap(x[t], x[i]); } } ...
第五章. 回溯法_图文.ppt
第五章. 回溯法 - 算法设计与分析 >回溯法 有限离散问题总可以用穷举法
第5章 回溯法.doc
? 掌握用回溯法解题的算法框架 (1)递归回溯最优子结构性质 (2)子集树算法...易见,最佳调度方案是 1,3,2,其完成 时间和为 18。 解空间:排列树 class ...
算法设计与分析-回溯_图文.ppt
算法设计与分析-回溯 - 第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯 (2)迭代回溯 ? ...
第五章. 回溯法_图文.ppt
第五章. 回溯法 - 算法设计与分析 >回溯法 有限离散问题总可以用穷举法
5-算法回溯法_图文.ppt
5-算法回溯法 - 第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯 (2)迭代回溯 ? ?...
更多相关标签: