贪心算法浅析
贪心算法浅析
摘要：本文讲述了贪心算法的基本思路及实现过程，贪心算法的特点、存在的问题以及应用。并通过贪心算法的特点举例列出了几个经典问题，通过对问题的探讨和研究，对贪心算法有了更加深入的了解。
关键词：贪心算法；最优解；最优子结构问题；删数问题；活动安排问题
贪心算法的基本思路及实现过程
1贪心的基本思想
用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。
利用贪心策略解题，需要解决两个问题：
（1）该题是否适合于用贪心策略求解；
（2）如何选择贪心标准，以得到问题的最优/较优解。
2贪心算法的实现过程
（1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题；
（2）从问题的某一初始解出发：
While（能朝给定目标前进一步）
求出可行解的一个解元素；
（3）由所有解元素组合成问题的一个可行解。
贪心算法的特点
贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点：
（1）如何贪心
怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。
具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。
（2）贪心的正确性
要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。
贪心算法存在的问题
（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；
（2）贪心算法只能用来求某些最大或最小解的问题；
（3）贪心算法只能确定某些问题的可行性范围
贪心算法的应用
1哈夫曼编码
2 0-1背包问题
3磁盘文件的存储
4生产调度问题
5信息查询
贪心算法经典应用举例
删数问题
问题提出：给定n位正整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。
分析：n位数a可表示为x1x2…xixjxk…xn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为T，其最优解A=(y1，y2…yk)表示依次删去的k 个数，在删去k个数后剩下的数字按原次序排成的新数。即最优值记为TA。
本问题采用贪心算法求解，采用最近下降点优先的贪心策略：即x1 证明：先来证明该问题具有贪心选择性质，即对问题T删除最近下降点的数xj后得到的N1是n一1位数是中最小的数。 根据数的进制特点，对a按权展开得： a=x1*10n-1+x2*10n-2+...+xi*10n-i+xj*10n-j+xk*10n-k+ (x) 则有：Nl=x1*10n-2+x2*10n-3+...+xi*10n-i-1+xk*10n-k+ (x) 假设删去的不是xj而是其它位，则有 N2=x1*10n-2+x2*10n-3+...+xi*10n-i-1+xj*10n-k+ (x) 因为有x1 因此删数问题满足贪心选择性质。 删数问题的C++代码： #include #include using namespace std; int main() { string n; int s,i,x,l,m; printf("请输入一个正整数和将要删去的个数!\n"); while(cin>>n>>s) { i=-1,m=0,x=0; l=n.length(); while(x { i++; if(n[i]>n[i+1])//出现递减,删除递减的首数字 { n=n.erase(i,1); x++;// x统计删除数字的个数 i=-1;//从头开始查递减区间 } if(i==l-x-2&&x m=1;//已经无递减区间,m=1脱离循环 } printf("最后结果为:\n"); cout< } } 问题的最优子结构性质 在进行了贪心选择后，原问题T就变成了对N1如何删去k-1个数的问题T’，是原问题的子问题。若A=(xj，A’)是原问题T的最优解，则A’是子问题T’的最优解，其最优值为TA’。 证明：假设A’不是子问题T’的最优解，其子问题的最优解为B’，其最优值记为TB’，则有TB’ 因此，删数问题满足最优子结构性质。 从以上贪心选择及最优子结构性质的证明可知删数问题用贪心算法可以求得最优解。 活动安排问题 问题：设有n个活动的集合E={1,2,...,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且Si 证明：这个问题可以使用贪心算法进行求解。其实这个问题的关键并不是如何用贪心算法求解，而是如何证明这个问题可以用贪心算法求解。鉴于证明的复杂性，还是不在此讨论证明问题。其实贪心算法问题的证明无非都是用数学归纳法证明，不错就是那个传说中万能证明法，数学归纳法。还是直接讨论实现过程吧。 实现：首先将活动按照活动的结束时间非递减：F1<=F2<=...<=Fn排序。如果所给的活动未排序，则先将活动按此序排列，时间复杂度一般为O(nlogn)可解决。以下是解决问题的算法。 1 //贪心算法-活动安排的实现 2 3 #include "stdafx.h" 4 #include "stdio.h" 5 6 template 7 void GreedySelector(int n,Type s[],Type f[],bool A[]) 8 { 9 A[0]=1; //第一个直接选取 10 int j=0; 11 for(int i=1;i 12 { 13 if(s[i]>=f[j]){A[i]=true;j=i;} //如果第i+1的活动的开始时间大于或等于第i个活动的结束时间，则标记该活动 14 else A[i]=false; 15 } 16 } 17 18 int _tmain(int argc, _TCHAR* argv[]) 19 { 20 //初始化数据 21 int n=3; 22 int s[3]={1,2,4}; //开始时间 23 int f[3]={3,3,5}; //结束时间 24 bool A[3]={0,0,0}; //数组A用于标记是否选择活动，1表示选择，0表示不选择 25 26 GreedySelector 27 for(int i=0;i 28 { 29 printf("%d\n",A[i]); 30 } 31 } 该算法的贪心选择的意义是使剩余的可安排的时间段极大化，以便安排尽可能多的相容活动。也就是说，每次选择完了之后，保证这次的选择之后留下的时间是最多的。 时间复杂度：GreedySelector算法效率极高。当输入的数据是已经按照结束时间非递减排序好的时候，算法只需要O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。 总结 贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。贪心算法所作的选择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。总之，如果一个贪心解决方案存在，就可以使用它。 参考文献 [1] 严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997． [2] M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京:电子工业出版社,2004． [3] 常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,第13卷，第13期，2008.9. [4]龚雄兴,堆与贪心算法[M],湖北襄樊学院，2003. [5] 张洁,朱莉娟.贪心算法与动态规划的比较[M].新乡师范高等专科科学学报,第19卷，第五期，2005.9. [6] 殷建平.关于贪心算法的正确性证明[M].江西师范大学学报（自然科学版）,第22卷增刊,1998.10. 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数 19. （ D ）是贪心算法与动态规划算法的共同点。 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。 应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。 2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。 代码如下： #include for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i 基于贪心算法与最小路径的基因组组装优化问题 摘要 随着人类基因组计划的实施和飞速发展，基因组测序拼接作为生物信息学的核有着极其重要的应用价值。新的测序技术大量涌现，产生的reads 长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。本文通过如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法，建立数学模型来解决基因组组装问题。 针对问题一，首先，利用相应的软件对原基因组G 进行切割，利用全基因鸟枪法测序对切割后的短基因进行测序，得到较小的基因组j i G ,通过对比多条任意切割后相似的基因组j i G 从而找出个别碱基对存在的识别错误。而对于基因组中存在的重复片段可以通过两个read 之间的DNA 片段的长度满足一定的分布规律即pared end read 来解决。 接下来对比任意两个11 1m n read 和3 2 2 m n read 是否相等，通过MATLAB 软件建立n m 阶的关联矩阵，最后利用图论中的最短路径方法使更多的基因组能拼接在一起，尽可能使拼接出来的基因组在原基因组的覆盖率达到最大。 针对问题二，先把附件给出的数据提取出来导入MATLAB 中，再结合问题一给出的模型对基因组进行重组，从而得到新的基因。 最后，基于对基因组组装的研究，为使重组基因能更接近原基因序列，对问题一提出模型进行合理性的评价。 关键词：基因组组装 全基因鸟枪法测序 贪心算法 最短路径 一、问题的重述 1.1问题背景 快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。 1.2问题提出 确定基因组碱基对序列的过程称为测序（sequencing）。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。通常的做法是，将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有两个短片段序列分别为 ATACCTT GCTAGCGT GCTAGCGT AGGTCTGA 则有可能基因组序列中包含有ATACCTT GCTAGCGT AGGTCTGA这一段。当然，由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列。对组装效果的评价主要依据组装序列的连续性、完整性和准确性。连续性要求组装得到的（多条）序列长度尽可能长；完整性要求组装序列的总长度占基因组序列长度的比例尽可能大；准确性要求组装序列与真实序列尽可能符合。 利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、de Bruijn 图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。 具体解决问题如下： 问题一：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。 问题二：现有一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪进行测序，测序策略以及数据格式的简要说明见附录一和附录二，测得的读长数据见附录三，测序深度（sequencing depth）约为70×，即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 摘要：作业和测试的自动组卷是在线形成性考核系统的核心内容。本文在深入研究贪心算法的基础上，提出了基于贪心算法的自动组卷算法，分析了题库和作业库的约束条件，实现了快速高效的组卷过程。最后给出具体实例加以论证。该算法已经成功应用于实际的在线形成性考核系统中。 关键词：贪心算法；在线形成性考核；约束条件；组卷 一、引言目前，常用的自动组卷算法有随机选取算法、回溯试探算法、蛮力法和遗传算法等，这些算法对在线考试系统确实具有一定的应用价值，但这些方法生成的作业卷和测试卷在试卷的科学性和合理性上考虑较少。在综合研究以上各种算法的优缺点后，保证达到较好时间效率和空间效率的基础上，采用贪心算法为核心和随机选取算法为辅助的组卷算法，应用于在线形成性考核系统在线作业和在线测试中，能够达到较好的组卷效果，并且达到教学辅助效果。决定组卷效率和作业卷质量的主要因素有两个：一是题库和作业库的结构；二是组卷算法的设计。二、贪心算法简介贪心算法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个全局的最优解。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法的基本要素。一是贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。二是最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。在题库组卷问题中，其最优子结构性质表现为：若a是对于e的题库组卷问题包含试题1的一个最优解，则相容作业卷集合a′= a-{1}是对于e′= {i∈e：si≥f1}的题库组卷问题的一个最优解。三、基于贪心算法的在线形成性考核系统组卷算法1、在线形成性考核系统结构在线形成性考核是指对学生学习过程的测评，是对学生课程学习的阶段性考核，是加强教学过程管理、检验学习效果的重要措施。在该系统中，管理员模块主要负责数据导入导出和系统维护，按照学生的课程注册信息绑定学生的班级、课程、辅导教师及恢复误删除成绩；教师模块完成课程形成性考核方案设计，作业题设计，查询考核内容，作业管理，作业批阅，查询批阅结果，删除已批阅但学生要求重做的作业成绩，学生信息管理，查询作业完成情况，到课率录入；学生模块主要功能是查看形考方案、主持教师、辅导教师、导学教师，在线作业，在线测试，作业成绩及反馈查询。在线形成性考核系统结构如图1所示。图1 在线形成性考核系统结构2、题库设计首先需要确定的是试题组织的方式。为了保证达标原则、全面性原则和主要性原则，最好将试题库与具体的知识内容进行关联，也即以课程知识点为核心组织试题库。然后就要考虑试题本身固有的特性参数，主要有题型、试题内容、答案、难度系数等。难度系数是试题难易程度的指标，也是试卷生成中的一个重要参数，它可以由教师录入试题时给定，并且在同一门课程中要坚持相同的标准，并且难度标准初始设定时要充分考虑到所要测试学生的程度范围。难度系数一般用等级来表示, 在五级难度系数中, 一级难度为最低, 五级难度为最高。题型分为客观题和主观题。客观题分单项选择题、多项选择选、判断题和填空题，主观题分计算题、简答题和论述题。3、作业库设计组卷方式可以按需求由主持老师进行客观题和主观题自由组卷。客观题在学生完成并提交成功后，系统自动阅卷并给出成绩。主观题在学生完成并提交后，由辅导老师阅 实验03 贪心算法 一、实验目的 1.掌握贪心算法的基本思想 2.掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明 3.掌握贪心算法求解问题的方法 二、实验内容 1.认真阅读算法设计教材,了解贪心算法思想及方法; 2.设计用贪心算法求解最优装载哈夫曼编码、单源最短路径、最小生成树的 java程序 三、求解的问题 1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中 各个字符出现的频率，求各个字符的哈夫曼编码方案。 2.给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。 这里路的长度是指路上各边权之和。 3.设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为 c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。求G的最小生成树。 四、实验程序 1．哈夫曼编码 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|-1次的“合并”运算后产生最终所要求的树T。下面所给出的算法huffmanTree中，编码字符集中的每一字符c的频率是f（c）。以f 为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后，产生一棵新的树，其频率为合并两棵树的频率之和，并将新树插入优先队列Q。 private static class Huffman implements Comparable{ Bintree tree; float weight; private Huffman(Bintree tt,float ww) { tree=tt;weight=ww; } public int compareTo(Object x){ float xw=((Huffman) x).weight; if(weight 武汉理工大学 算法设计与分析论文题目：贪心算法应用研究 姓名：吴兵 学院：信息工程 专业班级：电子133 学号： 1409721303131 任课教师：张小梅 目录 摘要 (1) 1.绪论 (2) 2贪心算法的基本知识概述 (3) 2.1 贪心算法定义 (3) 2.2 贪心算法的基本思路及实现过程 (3) 2.3贪心算法的核心 (3) 2.4贪心算法的基本要素 (4) 2.5 贪心算法的理论基础 (6) 2.6 贪心算法存在的问题 (7) 3贪心算法经典应用举例 (8) 3.1删数问题 (8) 3.2 汽车加油问题 (10) 3.3会场安排问题 (12) 4.总结 (16) 5.参考文献 (17) 摘要 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。 关键词：贪心算法最小生成树多处最优服务次序问题删数问题 大学计算机考试模拟题（理工类） 一、简答题（本题共6个小题，每小题5分，共30分） 1. 什么是信息社会？信息社会的主要特征是什么？P32 第4题参见P13 P14 2. 什么是CPU，简述CPU的基本组成和功能P108 第18.(1) 参见P77 3. 什么是操作系统？简述操作系统的主要功能。P109 第24题参见P89 4. 人类问题求解的一般思维过程是什么？简要说明参见P112图3-1 描述 5. 什么是枚举法？说明枚举法的优缺点。参见P113第6段, P132穷举法 6. 什么是浏览器/服务器（B/S）三层体系结构，画图并简要说明。P340第10题参见P316 P276 二、单项选择题（本题共20个小题，每小题1分，共20分） 1. 下列容不属于信息素养（Information Literacy）的是 A．信息意识B．信息知识 C．分析能力D．信息道德 2. 阿兰·麦席森·图灵（Alan Mathison Turing）对计算机科学的发展做出了巨大贡献，下列说法不正确的是 A．图灵是著名的数学家、逻辑学家、密码学家，被称为计算机科学之父。 B．图灵最早提出关于机器思维的问题，被称为人工智能之父。 C．图灵创立了二进制。 D．“图灵奖”是为奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家而设立的。 3. 最早的机械式计算机“加法器”的发明人是 A．帕斯卡B．巴贝奇 C．莱布尼茨D．布尔 4. 巴贝奇的“分析机”到他终生都没有制造出来，下列说确的是（） A．设计原理有错误B．设计精度不够 C．设计图纸不够完善D．机械加工的工艺水平达不到它要求的精度 5. 以集成电路为基本元件的第三代计算机出现的时间为（）。A．1965—1969B．1964—1975 C．1960—1969D．1950—1970 6. 在计算机中，引入16进制，主要目的是（）。 A．计算机中的数据存储采用16进制 B．计算机中的数据运算采用16进制 C．缩短2进制字串的长度 D．计算机的存地址采用16进制编制 7. 设计算机字长为16位，采用补码表示，可表示的整数的取值围是（）。A．0～65535B．-32767～32767 C．-32768～32767D．-32767～32768 8. 下列叙述中，正确的是( )。 A．所有十进制小数都能准确地转换为有限位二进制小数 B．汉字的计算机码就是国标码 C．所有二进制小数都能准确地转换为十进制小数 D．存储器具有记忆能力，其中的信息任何时候都不会丢失 9. 关于微处理器，下列说法错误的是（） A、微处理器就是微机的CPU，由控制器运算器和存储器组成。 B、微处理器不包含存储器。 C、微处理器执行CPU控制部件和算术逻辑部件的功能。 D、微处理器与存储器和外围电路芯片组成微型计算机。 10. 关于操作系统，下列叙述中正确的是（）。 实验五应用贪心算法求解背包问题 学院：计算机科学与技术专业：计算机科学与技术 学号：班级：姓名： 、 实验内容： 背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是n ，假设W w i和v i（1 i n）w i 1i，求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 二、算法思想： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三、实验过程： #in elude { float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序，按pi/wi 价值收益进行排序，一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益，重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j; Computer Knowledge and Technology 电脑知识与技术软件设计开发本栏目责任编辑：谢媛媛第6卷第35期(2010年12月)基于贪心算法的0-1背包问题 陈曦 （九江学院，江西九江332005） 摘要：贪心算法是解决问题的一种算法，因其解决问题时具有简单性、直观性和高效性而备受青睐。当待解决的问题具有最优子结构和贪心选择性质时，就可以考虑用贪心算法求解。0-1背包问题是计算机问题中一个普遍的问题，文章中详述了用贪心算法如何解决0-1背包问题。并得出用贪心算法求解此问题能得到最优解。 关键词：0-1背包；贪心算法；动态规划中图分类号：TP312文献标识码：A 文章编号：1009-3044(2010)35-10061-02 Based on the Greedy Algorithm of 0-1Knapsack Problems CHEN Xi (Jiujiang University,Jiujiang 332005,China) Abstract:The greedy algorithm is the solution to the problem of an algorithm,because of its solving problems with simplicity,intuitive and the efficiency is favour.When un-solved problems that have the most YouZi structure and moment-the greedy-choice properties,can con -sider to use greedy algorithm.0-1knapsack problems in computer problems is a common problem in the text,was described by the greedy algorithm to solve 0-1knapsack problems.And obtained by greedy algorithm for solving this problem can obtain optimal solutions.Key words:0-1knapsack;greedy algorithm;dynamic programming 1算法设计与分析是一门集应用性、创造性、实践性为一体的综合性极强的课程[1-2] 一个高效的程序不仅需要“编程技巧”，更需要合理的数据组织和清晰高效的算法。当一个问题具有最优子结构时，根据其具体情况可以用动态规划算法或者贪心算法来求解，但是问题同时具有贪心选择性质时，选择贪心算法更优，贪心算法通常会给出一个简单、直观和高效的解法[3]。 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。 作为一种算法设计技术，贪心法是一种简单的方法。与动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。这种局部最优选择并不能保证总能获得全局最优解，但是通常能得到较好的近似最优解。例如，平时购物找钱时，为使找回的零钱的硬币数量最少，从最大面值的币种开始，按递减的顺考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小的面值的币种。这就是在采用贪心算法。这种方法在这里总是最优，因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1,5,和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币，但是最优的解答应是3个5单位面值的硬币。 1.1贪心算法解题思路 贪心算法[4]是经常用到的一种解题方法，往往在解决最优问题时都可以用贪心算法求解。其解题思路为： 1）建立数学模型来描述问题。 2）把求解的问题分成若干子问题。 3）对每一对问题求解，得到子问题的局部最优解。 4）把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进do 求出可行解的一个元素； 由所有解元素组合成问题的一个可行解。 虽然贪心算法有时并不能得到最优解，但是经过证明贪心算法能提高问题的解决效率。 收稿日期：2010-10-15 作者简介：陈曦（1982-），女，江西九江人，讲师，硕士，主要研究方向为计算机应用。 E-mail:xsjl@https://www.wendangku.net/doc/5d18961879.html, https://www.wendangku.net/doc/5d18961879.html, Tel:+86-551-56909635690964ISSN 1009-3044Computer Knowledge and Technology 电脑知识 与技术Vol.6,No.35,December 2010,pp.10061-1006210061 智能算法30个案例分析 【篇一：智能算法30个案例分析】 智能算法是我们在学习中经常遇到的算法，主要包括遗传算法，免 疫算法，粒子群算法，神经网络等，智能算法对于很多人来说，既 爱又恨，爱是因为熟练的掌握几种智能算法，能够很方便的解决我 们的论坛问题，恨是因为智能算法感觉比较“玄乎”，很难理解，更 难用它来解决问题。 因此，我们组织了王辉，史峰，郁磊，胡斐四名高手共同写作 matlab 智能算法，该书包含了遗传算法，免疫算法，粒子群算法， 鱼群算法，多目标pareto 算法，模拟退火算法，蚁群算法，神经网络，svm 等，本书最大的特点在于以案例为导向，每个案例针对一 个实际问题，给出全部程序和求解思路，并配套相关讲解视频，使 读者在读过一个案例之后能够快速掌握这种方法，并且会套用案例 程序来编写自己的程序。本书作者在线，读者和会员可以向作者提问，作者做到有问必答。 本书和目录如下：基于遗传算法的tsp算法（王辉） tsp (旅行商问题—traveling salesman problem)，是典型的np 完全问题，即其 最坏情况下的时间复杂性随着问题规模的增大按指数方式增长，到 目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进 化算法，其基本原理是仿效生物界中的“物竞天择、适者生存” 的演 化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代 的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决 tsp 问题等组合优化问题具有较好的寻优性能。 基于遗传算法和非线性规划的函数寻优算法（史峰）遗传算法提供 了求解非线性规划的通用框架，它不依赖于问题的具体领域。遗传 算法的优点是将问题参数编码成染色体后进行优化，而不针对参数 本身，从而不受函数约束条件的限搜索过程从问题解的一个集合开始，而不是单个个体，具有隐含并行搜索特性，大大减少陷入局部 最小的可能性。而且优化计算时算法不依赖于梯度信息，且不要求 目标函数连续及可导，使其适于求解传统搜索方法难以解决的大规模、非线性组合优化问题。 用于模式分类、模式识别等方面．但 bp 算法收敛速度慢，且很容易 陷入局部极小点，而遗传算法具有并行搜索、效率高、不存在局部 实验五：贪心算法求解背包问题 实验内容 应用贪心算法求解离散背包问题，分析时间复杂度。 有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1<=i<=n），设求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 算法思想 ?动态规划的思想： –对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。 – 引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS 的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。 我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]， ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1 [i] = CH2[j]还是CH1[i] != CH2[j]，就可以计算出ch[i][j]。 算法 length(string CH1,string CH2,int b[MAX][MAX]) //用于构建动态数组 //输入：两字符窜 //输出：最长公共子序列 for(i=1;i<=ch1Len;i++)//二重循环求解 for(int j=1;j<=ch2Len;j++) { if(CH1[i-1]==CH2[j-1])//相等字符 { ch[i][j]=ch[i-1][j-1]+1; b[i][j]=0; } else if(ch[i-1][j]>=ch[i][j-1])//上比较大 { ch[i][j]=ch[i-1][j]; b[i][j]=1; } else//左比较大 { ch[i][j]=ch[i][j-1]; b[i][j]=-1; } } printCS(int b[MAX][MAX],string x,int i,int j) //回溯求出最长子序列输出 //输入：标记数组 //输出：最长子序列 if(i == 0 || j == 0)//边界，返回 return; if(b[i][j] == 0) { printCS(b, x, i-1, j-1);//左上 cout< 1、PCA和LDA的区别？ PCA是一种无监督的映射方法，LDA是一种有监督的映射方法。PCA只是将整组数据映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据部的分类信息。因此，虽然做了PCA后，整组数据在表示上更加方便（降低了维数并将信息损失降到了最低），但在分类上也许会变得更加困难；LDA在增加了分类信息之后，将输入映射到了另外一个坐标轴上，有了这样一个映射，数据之间就变得更易区分了（在低纬上就可以区分，减少了很大的运算量），它的目标是使得类别的点距离越近越好，类别间的点越远越好。 2、最大似然估计和贝叶斯方法的区别？p(x|X)是概率密度函数，X是给定的训练样本的集合，在哪种情况下，贝叶斯估计接近最大似然估计？ 最大似然估计把待估的参数看做是确定性的量，只是其取值未知。利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值(模型已知，参数未知）。贝叶斯估计则是把待估计的参数看成是符合某种先验概率分布的随机变量。对样本进行观测的过程，把先验概率密度转化为后验概率密度，利用样本的信息修正了对参数的初始估计值。 当训练样本数量趋于无穷的时候，贝叶斯方法将接近最大似然估计。如果有非常多的训练样本，使得p(x|X)形成一个非常显著的尖峰，而先验概率p(x)又是均匀分布，此时两者的本质是相同的。 3、为什么模拟退火能够逃脱局部极小值？ 在解空间随机搜索，遇到较优解就接受，遇到较差解就按一定的概率决定是否接受，这个概率随时间的变化而降低。实际上模拟退火算法也是贪心算法，只不过它在这个基础上增加了随机因素。这个随机因素就是：以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。 4、最小错误率和最小贝叶斯风险之间的关系？ 基于最小风险的贝叶斯决策就是基于最小错误率的贝叶斯决策，换言之，可以把基于最小错误率决策看做是基于最小风险决策的一个特例，基于最小风险决策本质上就是对基于最小错误率公式的加权处理。 5、SOM的主要功能是什么？怎么实现的？是winner-all-take-all 策略吗？ SOM是一种可以用于聚类的神经网络模型。 自组织映射（SOM）或自组织特征映射（SOFM）是一种使用非监督式学习来产生训练样本的输入空间的一个低维（通常是二维）离散化的表示的人工神经网络（ANN）。自组织映射与其他人工神经网络的不同之处在于它使用一个邻近函数来保持输入控件的拓扑性质。SOM网络中, 某个输出结点能对某一类模式作出特别的反应以代表该模式类, 输出层上相邻的结点能对实际模式分布中相近的模式类作出特别的反映,当某类数据模式输入时, 对某一输出结点产生最大刺激( 获胜结点) , 同时对获胜结点周围的一些结点产生较大刺激。在训练的过程中, 不断对获胜结点的连接权值作调整, 同时对获胜结点的邻域结点的连接权值作调整; 随着训练的进行, 这个邻域围不断缩小, 直到最后, 只对获胜结点进行细微的连接权值调整。 不是winner-all-take-all 策略。获胜结点产生刺激，其周围的结点也会产生一定程度的兴奋。 6、期望算法需要哪两步？请列出可能的公式并做必要的解释。 E-Step和M-Step。E-Step叫做期望化步骤，M-Step为最大化步骤。 整体算法的步骤如下所示： 1、初始化分布参数。 2、(E-Step)计算期望E，利用对隐藏变量的现有估计值，计算其最大似然估计值，以此实现期望化的过程。 3、(M-Step)最大化在E-步骤上的最大似然估计值来计算参数的值算法设计与分析实验报告贪心算法
计算机算法设计与分析习题和答案解析
【精选】贪心算法的应用
贪心算法详解分析
背包问题的贪心算法
基于贪心算法与最短路径的基因组组装最优拼接问题---1411
贪心算法的应用
基于贪心算法的在线形成性考核系统组卷研究
计算机算法与分析贪心算法实验报告
算法分析与设计选修课-贪心算法应用研究
大学计算机基础mooc习题集整理(含答案解析)
c应用贪心算法求解背包问题
基于贪心算法的0_1背包问题
智能算法30个案例分析
算法设计和分析实验四：贪心算法求解背包问题
模式识别习题集答案解析