《贪心算法的分析与实际应用.pdf》由会员分享，可在线阅读，更多相关《贪心算法的分析与实际应用.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-.XXXX 师大学计算机与信息工程学院师大学计算机与信息工程学院算法设计与分析结课论文算法设计与分析结课论文题目题目贪心算法的分析与实际应用专业专业计算机科学与技术班级班级 1402 班学号学号 1430090056XXXX 王悦宁任课教师任课教师洋完成日期完成日期 2015-1-18.-可修遍-.-可修遍-.贪心算法的分析与实际应用王悦宁摘摘要：要：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解
2、。本文主要介绍了贪心算法的核心、特点及算法本身存在的问题。关键词：关键词：贪心算法；最优解；背包问题；马踏棋盘The greedy algorithm analysis and practical applicationThe greedy algorithm analysis and practical application王悦宁Tianjin normal universityputer and Information Engineering CollegeTianjin300387AbstractAbstract：Greedy algorithm refers to, in the s
3、olution of the problem, always make in the current view is the bestchoice. That is to say, not to be considered as a whole, he made only in a sense of the local optimal solution. Thegreedy algorithm is not able to obtain the global optimal solution for all problems, but for a wide range of problems,
4、he can produce the global optimal solution or the approximate solution of the global optimal solution. This papermainly introduces the core of the greedy algorithm, the characteristics and the existing problems of the algorithmitself.Key wordsKey words：greedy algorithm; optimal solution; knapsack pr
5、oblem;能总是产生整体最优解，但对诸如最短路径问题、0 0 引言引言研究背景：研究背景：为了满足人们对大数据量信息处理的渴望，为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的算求解算法更像是一门艺术而不是像技术，但仍存在一些行之有效的、能够用于解决许多问题的算法设计方法。当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常给出一个简单，直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心
6、选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的字问题。尽管贪心算法对许多问题不最小生成树问题、哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且说给出的算法一般比动态规划算法更加简单、直观和高效。1 1 贪心算法贪心算法1.11.1 贪心算法概述贪心算法概述贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法
7、做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，.-可修遍-.通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心法不要回溯。贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些
8、量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪心算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪心算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪心选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。1.21.2 贪心算法基本思想贪心算法基本思想用局部解构造全局
9、解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法的思想本质就是分治，或者说：分治是贪心的基础。每一次都形成局部最优解，换一种方法说，就是每次都处理处一个最好的方案。1.31.3 贪心算法的核心贪心算法的核心贪心算法的核心问题是选择能生产最优解的最优度量标准，即具体的贪心策略。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法。其实，从“贪心策略”一词我们便可看出，贪心策略总是做出在当前看来是最优的选择，.也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上
10、的局部最优解，而许多问题的自身的特性决定论该问题可以运用贪心策略得到最优解或较优解。1.41.4 贪心算法特性贪心算法特性贪心算法可解决的问题通常大部分都有如下的特性: 有一个以最优方式来解决的问题。为了构造问题的解决方案， 有一个候选的对象的集合:比如不同面值的硬币。 随着算法的进行， 将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个
11、函数一样，此时不考虑解决方法的最优性。 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 最后，目标函数给出解的值。为了解决问题， 需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算确工作，那么找到的第一个解通常是最优的。1.51.5 贪心算法的理论基础贪心算法的理论基础- -拟阵拟阵贪心策略是最接近人类认知思维的一
12、种解题策略。但是，越是显而易见的方法旺旺越是难以证明。“拟阵”理论是一种能够确定贪心策略何时能产生最优解的理论。拟阵 M 定义为满足下面 3 个条件的有序对（S,I）:（1）S 是非空有限集；（2） I是S的一类具有遗传性质的独立子集族，即若 BI，则 B 是 S 的独立子集，且 B 的任意子集也都是 S 的独立子集。空集比为 I 的子集；-可修遍-.（3） I 满足交换性质， 即若 AI， BI， 且|A|B|,则存在某一元素 xB-A,使得 AxI；定理 2.1 拟阵 M 中所有极大独立子集具有相同大小。引理 2.1 （拟阵的贪心选择性质）设M=（S,I）是具有权函数 M 的带权拟阵， 且
13、 S 中元素依权值从大到小排列，又设 xS 是 S 中的第一个使得x是独立子元素，则存在 S 的最优子集 A 使得 xA。引理 2.2 设 M=（S,I）是拟阵。若 S 中元素 x不是空集的一个可扩元素，则x 也不可能是 S 中任一独立子集 A 的可扩展元素。引理 2.3（拟阵的最优子结构性质）设 x 是求带权拟阵 M=（S,I）的最优子集的贪心算法 Greedy所选择的 S 中的第一个元素。那么，原问题可简化为求带权拟阵 M=（S,I）的最优子集问题。定理 2.4（带权拟阵贪心算法的正确性）高M=（S,I）是具有权函数 W 的带权拟阵，算法 Greedy返回 M 的最优子集。适宜贪心策略来求
14、解的许多问题都可以归结为在加权拟阵中找一个具有最大全权值独立子集的问题，即给定一个加权拟阵 M=（S,I），若能找出一个独立且具有最大可能权值的子集 A， 且 A 不被 M 中比它更大的独立子集所包含， 那么 A 为最优子集，也是一个最大独立子集。我们认为，针对绝大多数的信息学问题，只要具备了拟阵的结构便可用贪心策略求解。拟阵理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。1.61.6 贪心算法的优缺点贪心算法的优缺点贪心算法是一种重要的算法设计策略而且其效率高。贪心算法并不从整体最优考虑他所做出的选择只是在某种意义上的局部最优选择，即在当前看来最好的选择。希望通过每次所作的贪心选
15、择导致最终结果是问题的一个最优解。贪心算法具有良好的爬坡能力，一般情况下该算法都可以较快的求出满足计算精度要求的近似最优解，当算法不能在限定的时间给，找满足问题要求的近似最优解时，给出一个可行解及其计算误差，作为决策参考。但随着问题规模和复杂的不断提升，单一的算法在其收敛性和求解速度等方面已经表现出的局限性，即使贪心算法的效率很高也只适用于少量实例。2 2 利用贪心算法解决问题利用贪心算法解决问题2.12.1 背包问题背包问题.2.1.1 问题描述0-10-1 背包问题背包问题 有一个背包，背包容量是M=150。 有 7 个物品， 物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最
16、大，但不能超过总容量。由于每次装东西进背包，我们只考虑能否装进，以及是否当前状态下的最优选择，也就是说，我们需要用背包的容量去设计一个数组，存储每一单位个容量的最大价值是多少，以此类推，获得背包容量下的最大价值是多少。2.1.2 贪心算法策略目标函数：pi 最大约束条件是装入的物品总重量不超过背包容量：wi=M(M=150），每次选取单位重量价值最大的物品，成为解本题的策略。值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由
17、在贪心策略中存在的子问题的最优解得来的。对于例题中的3 种贪心策略， 都是无法成立 （无法被证明）的，解释如下：贪心策略：选取价值最大者。反例：W=30物品：A B C重量：28 12 12价值：30 20 20根据策略，首先选取物品 A，接下来就无法再选取了，可是，选取 B、C 则更好。贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。贪心策略：选取单位重量价值最大的物品。反例：W=30物品：A B C重量：28 20 10价值：28 20 10根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择 A，则答案错误。-可修遍-.【注意：如果物品可以分割为任意大小，
18、那么策略3 可得最优解】对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的。这样，上面的反例就解决了。但是，如果题目是如下所示，这个策略就也不行了。W=40物品：A B C重量：25 20 15价值：25 20 152.1.3 贪心解决背包问题的算法实现代码如下：#include struct goodinfofloat p; /物品效益float w; /物品重量float X; /物品该放的数量int flag; /物品编号;/物品信息结构体void Insertionsort(goodinfo goods,int n)/插入排序，按
19、 pi/wi 价值收益进行排序int j,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n)float cu;int i,j;for(i=1;i=n;i+)goodsi.X=0;.cu=M; /背包剩余容量for(i=1;icu)/当该物品重量大与剩余容量跳出break;goodsi.X=1;cu=cu-goodsi.w;/确定背包新的剩余容量if(i=n)goodsi.X=cu/goodsi.w;/该物品所要放的量for(j=
20、2;j=n;j+)goods0=goodsj;i=j-1;while (goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;/cout最优解为:endl;for(i=1;i=n;i+)cout第i件物品要放:;coutgoodsi.Xendl;void main()cout运用贪心法解背包问题endl;int j,n;float M;goodinfo *goods;/定义一个指针while(j)coutn;goods=new struct goodinfo n+1;/coutM;coutendl;-可修遍-.int i;for(i
21、=1;i=n;i+) goodsi.flag=i;cout请输入第igoodsi.w;cout请输入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比coutendl;Insertionsort(goods,n);bag(goods,M,n);coutpress to run agianendl;coutpress to exitj;2.22.2 马踏棋盘的贪心算法马踏棋盘的贪心算法2.1.1 问题描述马的遍历问题。在 88 方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。其实马踏棋盘的问题很早就有人提
22、出，且早在1823 年，J.C.Warnsdorff 就提出了一个有名的算法。在每个结点对其子结点进行选取时， 优先选择出口最小的进行搜索，出口的意思是在这些子结点中它们的可行子结点的个数，也就是子结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现死结点(顾名思义就是没有出口又没有跳过的结点)，这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局
23、部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算.机，这种方法完全可以用手工求出解来，其效率可想而知。2.1.2 贪心算法策略首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下:（1）输入初始位置坐标 x,y;（2） 步骤 c:如果 c 64 输出一个解，返回上一步骤 c-(x,y) c计算(x,y)的八个方位的子结点，选出那此可行的
24、子结点循环遍历所有可行子结点，步骤 c+重复 2显然是一个递归调用的过程，大致如下:#define N 8void dfs(int x,int y,int count)int i,tx,ty;if(countN*N)output_solution();/输出一个解return;for(i=0; i8; i+)tx=hni.x;/hn保存八个方位子结点ty=hni.y;stxty=count;dfs(tx,ty,count+1);/递归调用stxty=0;3 3 总结总结贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问
25、题确定一个可行性围。贪心算法所做的选择依赖于以往所做过的选择，绝不依赖于将来的选择，这使得算法再编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对于一个问题可以使同时使用几种方法去解决，贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解时，就需要判断贪心性质的正确性了。与回溯-可修遍-.法、动态规划法等比较，它的适用区域相对狭窄，总之如果一个贪心解决方案存在就可以使用它。 参考文献参考文献 谭浩强.C+面向对象程序设计M.清华大学，2006璟，计算机算法引论-设计与分析技术M。科学，2003：104114王晓东，计算机算法设计与分析M.电子工业，2001；百度文库OLwenku.baidu./view/e3f5e8486d728.html常友渠，肖贵元，曾敏。贪心算法的探讨与研究J。电力高等专科学校学报，2008：第三期好搜百科OLbaike.haosou./doc/5722.html百度百科OL。baike.baidu./link?url=Ph8yyXUJQTWdWTPaDW6NW_0bK6QSsa073ZocSnkY3AAfpsh7Pckvdxneulz6IdENMWeDQp-MEeW5AqmuagDUnq.-可修遍-