贪心算法：任务调度问题.doc

程序实践报告（2010）数据结构课程设计报告贪心算法：任务调度问题专业计算机科学与技术（软件工程）学生姓名陈亮班级BM计算机091学号0951401134指导教师吴 素 芹起止日期2011.1.10-2011.1.141目 录1 简介12算法说明23测试结果24分析与探讨85小结11参考文献11附 录12附录1 源程序清单121贪心算法1 简介 贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总奏效，然而许多情况下确能达到预期的目的。下面来看一个找硬币的例子。假设有四种面值的硬币：一分、两分、五分和一角。现在要找给某顾客四角八分钱。这时，一般都会拿出四个一角、一个五分、一个两分和一个一分的硬币递给顾客。这种找硬币的方法与其他的方法相比，它所给出的硬币个数是最少的。在这里，就是下意思的使用了贪心算法（即尽可能地先考虑大币值的硬币）。贪心算法并不是从整体最优加以考虑，它所做出的选择只是局部最优选择。一些问题中，使用贪心算法得到的最后结果并不是整体的最优解，这时算法得到的是一次最优解（Suboptimal Solution）。在上述的问题中，使用贪心算法得到的结果恰好就是问题整体的最优解。对于一个具体的问题，怎么知道是否可用贪心算法来解此问题，以及能否得到问题的一个最优解呢？这个问题很难给予肯定的回答。但是，许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到，这是贪心算法可行的第一个基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题化简为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优结构性质。得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。 贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。 可惜的是，它需要证明后才能真正运用到题目的算当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征法中。 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。2算法说明 有n项任务，要求按顺序执行，并设定第i项任务需要ti单位时间。如果任务完成的顺序为1，2，。，n，那么第i项任务完成的时间为ci=t1+.+ti,平均完成时间即为（c1+.+cn）/n.本题要求找到最小的任务平均完成时间。 输入要求：输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个肺负整数t(t=1000000000),每个数之间用空格相互隔开，以一个负数来结束输入。 输出要求：对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0,则对应输出一个空行。 输入例子： 4 4 2 8 1 -1表示有四个任务，各自完成需要的时间单位分别是4，2，8，1，第三行输入-1表示输入结束。 输出例子：要求程序运行后的输出结果为：6. 501.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。3.贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do 求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；贪心算法的理论基础： 借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。1. 拟阵 拟阵M定义为满足下面3个条件的有序对(S,I)： (1)S是非空有限集。 (2)I是S的一类具有遗传性质的独立子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集必为I的成员。 (3)I满足交换性质，即若AI,BI且|A|0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为 。2. 关于带权拟阵的贪心算法 许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。 给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集。 例如，在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。 下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。Set greedy (M,W)A=; 将S中元素依权值W（大者优先）组成优先队列； while (S!=) S.removeMax(x); if (AI) A=Axx; return A；算法greedy的计算时间复杂性为 。引理1 (拟阵的贪心选择性质) 设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设xS是S中第一个使得x是独立子集的元素，则存在S的最优子集A使得x A。 算法greedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。3测试结果图51为正确的数据输入与其运行结果： 图51图52为异常的数据输入与其运行结果：。 图52 图53为异常的数据输入与其运行结果： 图534分析与探讨这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度三按照最短作业优先进行来安排的。 明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。首先，输入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样，由于案例的个数开始不得知，所以可以套用一个for循环，如图5.13所示。for(n=o; n=0;) /*当n小于0的时候，退出程序*/ scanf(“%1d”,&n)； if(n0) 建立一个具有n个元素的数组；for(i=0;i1），把数组的全部元素分成d1个组。所以距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-1d21;increment0;increment=1)/*每次的步长都是通过n值右移位来得到的*/ for(i= increment;i=increment;j-=increment) if (temp*(a+ (j-increment) *(a+j)=*(a+(j-increment);elsebreak;*(a+j) =temp;图5.14 希尔排序的实现（2）计算总的平均完成时间：排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为ACT=ai (n-i)/n（3）输出调度结果：由于输出的结果要求精确到0.01，所以输出的时候需要采用以下输出格式。double r100; /*依次存放每个案例的ACT*/printf( “%.sfn”, ri);/*输出的结果要求精确到0.01*/图5.15 要求输出的精度为0.01另外，程序实现的时候，要求用户一次可以输入一组或多组测试案例的数据，当用户的输入完成后，程序经过计算在屏幕上分行显示这几个案例的结果。因此,在有多个测试案例的情况下，需要设置一个数组，用来存放每一组测试案例的计算结果，如图5.16所示Double r100; /*用来存放每个测试案例的计算结果*/J=0; /*记录测试案例的个数*/For(对每一个测试案例)把计算机得到的最优调度时间存入rj中；J+;/*当输入的n值为负数时，跳出上面的for循环*/For(从0到j)If(ri=-1)printf(“n”); /*输出一个空行*/Else printf(“ %. 2fn”,ri); /*输出的结果要求精确到0.01*/图5.16 有多个测试案例的处理方法5小结通过这次课程设计的学习，更加深刻认识了数据结构的重要性。在课程设计过程中，经过互相的提问，仔细的思考，学会了许多数据结构里之前不懂的问题。很高兴，学会了新的东西。我做的是贪心算法的课程设计，对于这个算法它很有趣，即通过一系列的选择，来选取最好的选择。而且还有许多的应用实例，使我们对算法有了更好的理解。感觉数据结构还是蛮好玩的，就是一个算法就可以控制整个的过程。为了把数据结构学好，不仅要弄好理论上的，而且还要把课程设计学好，联系实际，根据理论把课程设计学好，两者结合。相信一定是可以学好的。通过自己的努力就可以，结果不是那么重要，学到了东西才是最好的。相信自己。参考文献1 刘振安,刘燕君.C程序设计课程设计M.北京机械工业出版社,2004年9月2 谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月3 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月4Mark Allen Weiss,陈越改编.Data Structures and Algorithm Analysis in C(second edition).北京：人民邮电出版社，20055魏宝刚，陈越，王申康.数据结构与算法分析.杭州：浙江大学出版社，20046书本教材 C语言程序设计7书本教材 C+程序设计8书本教材 数据库理论附 录附录1 源程序清单#include #include#includeusing namespace std;void Shellsort( long *a, long n );int main() long n,i,j; long *a,*b;double r100;/* 用来存放每个测试案