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

《最佳调度的回溯算法的实验》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验目的：理解回溯法的原理，掌握调度问题的处理方法，实现最佳调度问题的回溯解决。 问题定义输入：1.      任务数N2.      机器数M3.      随机序列长度t[i],其中t[i]=x表示第i个任务完成需要时间单位x，输出：1.      开销时间besttime，表示最佳调度需要时间单位2.      最佳调度序列bestx[]，其中bestx[i]=x，表示将第i个任务分配给第x个机器执行。实验思想解空间的表示：一个深度为N的M叉树。基本思路：搜索从开始结点（根结点）出发，以DFS

2、搜索整个解空间。每搜索完一条路径则记录下besttime和bestx[]序列开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。测试数据及结果本测试的硬件以及软件环境如下CPU：PM1.5G;内存:768M;操作系统：windowsxpsp2

3、;软件平台：JDK1.5;开发环境：eclipse如图1所示：即为求任务数为10机器数为5的最佳调度的算法结果。图1实验结论以及算法分析通过测试证明算法正确有效。性能分析的方法：使用JDK1.5的System.nanoTime()，计算算法消耗的时间，以此来评价算法。（该方法在JDK1.5以下的版本中不支持）为了不影响算法的准确度，在测试的过程我们注释掉了打印随机字符串的步骤。由于没有使用限界函数进行优化，算法时间和空间复杂度呈指数级增长。所以该算法不适合较大规模的计算。图2图2蓝线表示机器数一定M

4、=3时，n增大时求解最佳调度对所消耗的时间，该趋势随着指数增加。图3图3表示任务数N一定时随着M的增大的增长曲线。图2和图3表明该程序的时间复杂度与理论分析相符合。源代码最佳调度的回溯算法(java描述）BestSchedule.Javapackage bestSchedule;import java.util.Random;public class BestSchedule ...{    /** *//**     * @author icyfire     * 本程序是采用回溯法解决最佳调度问

5、题     *      */    int N;        //任务数    int M;        //机器数    int best;     //最优值    int[] t;      //每个任务所需的时间序列    int[] len;    //每台机器所需时间序列    int[] x;      //当前路径    int[] bestx;  //最优调度：其中bestx[i]=m表示把第i项任务分配给第m台机器            public static void

6、 main(String[] args) ...{     BestSchedule bs =new BestSchedule();//进入主方法,那就先创建一个对象；     bs.showTest();//然后，就开始调用自己的方法，开始求解吧！    }        void showTest()   ...{         N=3//为了简单点就先小点吧。。。N=10; // 任务数         M=2//同上，M=7; //机器数目        Random r =new Ran

7、dom();//java果真比较狠，连个随机数都是一个类的对象！        t=new int [N]; //每个任务的时间        //int sum=0;        for (int i =0;i

8、[M];      //记录每台机器已经安排的时间            best = Integer.MAX_VALUE;  //这又是一个狠招啊，直接将整型的最大值赋给best。//跨平台.        bestx=new int [N];        x =new int[N];       Long startTime = System.nanoTime();//不就是拿系统当前时间当做开始时间吗！//哎，搞得这么复杂。        backtrack(