贪心算法：任务调度问题

数据结构课程设计报告贪心算法：任务调度问题专业计算机科学与技术（软件工程）学生姓名陈亮班级BM计算机091学号0951401134指导教师吴素芹起止日期2011.1.10-2011.1.14***********目录1简介.........................................................................................................................12算法说明.................................................................................................................23测试结果.................................................................................................................24分析与探讨.............................................................................................................85小结.......................................................................................................................11参考文献..................................................................................................................11附录....................................................................................................................12附录1源程序清单.................................................................................................12程序实践报告（2010）1贪心算法1简介贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总奏效，然而许多情况下确能达到预期的目的。下面来看一个找硬币的例子。假设有四种面值的硬币：一分、两分、五分和一角。现在要找给某顾客四角八分钱。这时，一般都会拿出四个一角、一个五分、一个两分和一个一分的硬币递给顾客。这种找硬币的方法与其他的方法相比，它所给出的硬币个数是最少的。在这里，就是下意思的使用了贪心算法（即尽可能地先考虑大币值的硬币）。贪心算法并不是从整体最优加以考虑，它所做出的选择只是局部最优选择。一些问题中，使用贪心算法得到的最后结果并不是整体的最优解，这时算法得到的是一次最优解（SuboptimalSolution）。在上述的问题中，使用贪心算法得到的结果恰好就是问题整体的最优解。对于一个具体的问题，怎么知道是否可用贪心算法来解此问题，以及能否得到问题的一个最优解呢？这个问题很难给予肯定的回答。但是，许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到，这是贪心算法可行的第一个基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题化简为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优结构性质。得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。可惜的是，它需要证明后才能真正运用到题目的算当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征法中。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。程序实践报告（2010）22算法说明有n项任务，要求按顺序执行，并设定第i项任务需要t[i]单位时间。如果任务完成的顺序为1，2，。。。，n，那么第i项任务完成的时间为c[i]=t[1]+….+t[i],平均完成时间即为（c[1]+....+c[n]）/n.本题要求找到最小的任务平均完成时间。输入要求：输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个肺负整数t(t=1000000000),每个数之间用空格相互隔开，以一个负数来结束输入。输出要求：对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0,则对应输出一个空行。输入例子：44281-1表示有四个任务，各自完成需要的时间单位分别是4，2，8，1，第三行输入-1表示输入结束。输出例子：要求程序运行后的输出结果为：6.501.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。3.贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算程序实践报告（2010）3法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法的基本要素：1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；程序实践报告（2010）43.只能求满足某些约束条件的可行解的范围。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；贪心算法的理论基础：借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。1.拟阵拟阵M定义为满足下面3个条件的有序对(S,I)：(1)S是非空有限集。(2)I是S的一类具有遗传性质的独立子集族，即若BÎI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集Æ必为I的成员。(3)I满足交换性质，即若AÎI,BÎI且|A||B|，则存在某一元素xÎB-A，使得A∪{x}ÎI。例如，设S是一给定矩阵中行向量的集合，I是S的线性独立子集族，则由线性空间理论容易证明(S,I)是一拟阵。拟阵的另一个例子是无向图G=(V,E)的图拟阵。给定拟阵M=(S,I)，对于I中的独立子集AÎI，若S有一元素xÎA，使得将x加入A后仍保持独立性，即A∪{x}ÎI,则称x为A的可扩展元素。当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集。下面的关于极大独立子集的性质是很有用的。定理1：拟阵M中所有极大独立子集大小相同。这个定理可以用反证法证明。程序实践报告（2010）5若对拟阵M=(S,I)中的S指定权函数W，使得对于任意xÎS，有W(x)0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为。2.关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。给定带权拟阵M=(S,I)，确定S的独立子集AÎI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集。例如，在最小生成树问题可以表示为确定带权拟阵的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。Setgreedy(M,W){A=Æ;将S中元素依权值W（大者优先）组成优先队列；while(S!=Æ){S.removeMax(x);if(A∪I)A=A{x}∪{x};}returnA；}算法greedy的计算时间复杂性为。引理1(拟阵的贪心选择性质)程序实践报告（2010）6设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设xÎS是S中第一个使得{x}是独立子集的元素，则存在S的最优子集A使得xÎA。算法greedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。3测试结果图5—1为正确的数据输入与其运行结果：图5—1程序实践报告（2010）7图5—2为异常的数据输入与其运行结果：。图5—2图5—3为异常的数据输入与其运行结果：图5—3程序实践报告（2010）84分析与探讨这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度三按照最短作业优先进行来安排的。明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。