《贪心算法日历调度问题》由会员分享，可在线阅读，更多相关《贪心算法日历调度问题（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告题目：贪心算法：任务调度问题一、简介算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。任何 程序基本上都是要用特定的算法来实现的。算法性能的好坏，直接决定了所实现程 序性能的优劣。贪心算法通过一系列的选择来得到的一个问题的解。它所做的每一 个选择都是当前的状态下某种意义的最好选择，即贪心选择。希望通过每次所做的 贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然 而在许多情况下能达到预期的目的。贪心算法采用的是逐步构造最优解的方法。在每个阶段，都做出一个看上去最 优的决策，做出贪心决策的依据称为贪心准则。本实验的目的是设计一个程序，具体实验
2、内容步骤包括排序、计算总的平均完 成时间、输出调度结果。因此，实验任务如下：有n项任务，要求按顺序执行，并设定第i项任务需要t i单位时间。如果任务 完成的顺序为1, 2，n,那么第i项任务完成的时间为ci=tl+t i, 平均完成时间(Average Completion time)即为(c1+ +cn)/n本题要求找 到最小的任务平均完成时间。输入要求：输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于 2000000 的整数n,接着下面一行开始列出n个非负整数t (tW1000000000),每一个数之间 用空格相互隔开，以一个负数来结束输入。输出要求：对每一个测试案例，打印它
3、的最小平均完成时间，并精确到0.01.每个案例对应 的输出结果都占一行。如输入某一个案例中任务数目n=0,则对应输出一个空行。二、算法说明1、贪心算法的基本要素：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即 贪心选择来达到，这是贪心算法可行的第一个基本要素。对于一个具体问题，要确 定它是否具有贪心选择 性质，必须证明每一步所做的贪心选择最终将会得到问题 的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解， 使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子 问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个
4、 整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在 于利用该问题的最优子结构性质。最优子结构性质是一个问题的最优解包含着它的子问题的最优解时，这个性质 是该问题可用贪心算法求解的一个关键特征。2、贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，已尽可能快的求更好的解。 当达到算法中的某一部不能继续前进时，算法停止。Huffman编码：Huffman编码也是贪心算法思想的一个较为典型的应用，被广泛的用于 文件压缩合文件传输中。它的应用背景主要是为了减少文件传输或者文件保存中的大小。在文 件中，通常都含有出现次数很多的符号如数字、空格和换行符，而某些特定字符
5、如z和x等出 现次数相对很少，也就是说，在文件中，出现频率最大和最小的字符之间通常存在着很大的差 别。Huffman编码就是提供一种较好的编码方法，它能保证出现频率高的字符的编码较短，从 而降低表示文件所需的总比特数三、测试结果本实验通过输入数据进行排序、计算总的平均完成时间以及输出调度结果来 认识贪心算法。正确的数据输入与其运行结果是：异常的数据输入与其运z是:C:UsersllenovoDeskto pDe bugC ppi .exe51 6 4 kerror!日工key to continueinputPress异常的数据输入与其运行结果是：四、分析与探讨这个题目属于贪心算法应用中的任务
6、条度文图。要得到所有任务的平均完成时 间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等 待的时间与自身执行需要的时间爱你之和。这样给出的调度三按照最短作业优先进 行安排的。明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。首先， 输入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个 数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继 续输入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样，由于 案例的个数开始不得知，所以可以套用一个 for 循环，如图所示：For(n=0;n=0;)/*当n小于0的时候，
7、推出程序*/Scanf (“ld”，&n)；if(n0)建立一个具有n个元素的数组；For(i=0;ivn;i+)继续读入这n个作业的完成时间；进行主要的调度运算；输出得到的最优调度结果；else if(n=0)输出一个空行：所以，对每组输入，其基本过程是：读入n个任务的运行时间，进行主要的调度运 算。已经明确了采用最短作业优先的程序思想，所以主要的调度运算包括 3个步骤：(1) 排序：将数组按从小到大排序。排序方法很多，如：冒泡排序、希尔排序、堆排序)此题用希尔排序实现， 如图 5.14所示.它的基本思想是：先取一个小于n的整数d作为第一个增量；这里选取n的一1半作为第一个增量(increm
8、e nt=1)，把数组的全部元素分成d个组。所以距离为1d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d d 重复上述的分组和排序，直至所取的增量 d 1(d d d d ),即所有记21t= t t-121录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入排序方法。void shells。rt(long *a, long n )long I,j, increment;long temp;/*第一个增量值为n/2，以后每一次的增量都是上一个增量值的一半*/ for (increment 二 nl;increment0;increment=l)/*
9、每次的步长都是通过n值右移位来得到的*/for(i= increment;in; i+)/*对每一组里面的元素进行插入排序*/t emp = *(a+i);for(j 二i;j二increment;j-二increment)if (temp*(a+ (j-increment) *(a+j)=*(a+(j-increment);elsebreak;*(a+j)二temp;图 5.14 希尔排序的实现（2）计算总的平均完成时间：排序完成后，数组 a 中的元素以升序的方式排序， 因此总的平均完成时间为ACT二工ai X（n-i）/n（3）输出调度结果：由于输出的结果要求精确到 0.01，所以输出的时
10、候需要采用 以下输出格式。double r100; /*依次存放每个案例的ACT*/printf（ “.sfn”，ri）; /*输出的结果要求精确到0.01*/图 5.15 要求输出的精度为 0.01另外，程序实现的时候，要求用户一次可以输入一组或多组测试案例的数据，当用户的输入完成后，程序经过计算在屏幕上分行显示这几个案例的结果。因 此,在有多个测试案例的情况下，需要设置一个数组，用来存放每一组测试案例 的计算结果，如图 5.16 所示Double r100;/*用来存放每个测试案例的计算结果*/J=0；/*记录测试案例的个数*/For(对每一个测试案例)把计算机得到的最优调度时间存入rj中
11、；J+；/*当输入的n值为负数时，跳出上面的for循环*/For(从 0 到 j)If(ri=-l)printf( “n”)；/*输出一个空行*/Else printf( “ %. 2fn” ,ri); /*输出的结果要求精确到 0.01*/图 5.16 有多个测试案例的处理方法 附录 原代码#include #include #include using namespace std;void Shellsort( long *a, long n );int main()long n,i,j;long *a,*b;double r100;/* 用来存放每个测试案例的计算结果 */ j=0;/*
12、 记录测试案例的个数 */*读入用户的输入，若当前输入为负数，则程序终止*/ for( n = 0; n = 0 ; )scanf( %ld, &n );if(n 2000000)printf(too much for the project!n); exit(0);if( n 0 )b = (long*)malloc( n * sizeof( long ) );a = b;for(i=0; i 1000000000)printf(too much for the project!n);exit(0);/* 对输入中出现任务时间为负数的异常处理 */ if(*(b+i) 0 ; i-,a+ )
13、rj+= (double)*a/(double)n * i;j+;free( b );/*当n为0时，标志相应的r数组值为一1,输出时碰到一1则输出一个空行*/else if ( n = 0 )rj+=-1;for(i=0;i1; increment0; increment=1 )for(i = increment; i =increment; j-= increment)if( temp *(a + (j-increment) )*(a+j)= *( a+ (j-increment) );elsebreak;*(a+j) = temp;参考文献1 严蔚敏，吴伟民数据结构（C语言版）清华大学出版社，1997年4月2 谭浩强.C程序设计（第三版）
