算法设计与分析论文

贪心算法不在贪心中爆发，就在贪心中灭亡 武汉理工大学计算机科学与技术学院班摘要 本文介绍贪心算法的基本意义以及算法的使用范围， 并通过具体的案例来分 析贪心 算法的具体应用，从而指出其特点和存在问题。关键字：贪心算法，贪心策略， TSP、0/1 背包引言我们用了 13 周的时间学完了算法设计与分析这本书。这本书中涵盖了 大量的常 见算法，包括蛮力法、分治法、动态规划法、贪心算法等等。我最有印 象的就是贪心算 法。 贪心算法是一种有合理的数据组织和清晰高效的算法， 它简 单有效。下面我们来详 细解读一下这个算法。1. 贪心算法的含义贪心算法可以简单描述为 :对一组数据进行排序， 找出最小值， 进行处理， 再 找 出最小值， 再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状 态下最好 或最优的选择，从而希望得到结果是最好或最优的算法。2. 贪心算法的基本思想贪心算法，法如其名，每次都贪心的选取当前最优解，一旦确定了当前解， 不管将来 有什么结果， 之后都不会再修正，这一点与动态规划法比起来稍有逊色。 如果一个问题 的最优解只能用蛮力法穷举得到， 则贪心法不失为寻找问题近似最 优解的一个较好办 法。贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行， 根据某 个优化测度， 每一步都要确保能获得局部最优解。 每一步只考虑一个数据， 他的 选取应该满足局部优化的条件。 若下一个数据和部分最优解连在一起不再是可行 解时， 就不把该数据添加到部分解中， 直到把所有数据枚举完， 或者不能再添加 算法停止。3. 贪心算法的基本要素3.1 贪心选择贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择， 即贪 心选择 来达到。 这是贪心算法可行的第一个基本要素， 也是贪心算法与动态规划 算法的主要区 别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择 就将所求 问题简化为一个规模更小的子问题。 对于一个具体问题， 要确定它是否 具有贪心选择的 性质， 我们必须证明每一步所作的贪心选择最终能得到问题的最 优解。通常可以首先证 明问题的一个整体最优解， 是从贪心选择开始的， 而且作 了贪心选择后， 原问题简化 为一个规模更小的类似子问题。 然后，用数学归纳法 证明，通过每一步贪心选择，最终 可得到问题的一个整体最优解。3.2 最优子结构当一个问题的最优解包含其子问题的最优解时， 质。运 称此问题具有最优子结构性 用贪心策略在每一次转化时都取得了最优解。 问题的最优子结构性质是该 问题可用贪心算法或动态规划算法求解的关键特征。 贪心算法的每一次操作都对 结果产生直接影响， 而动态规划则不是。 贪心算法对每个子问题的解决方案都做 出选 择，不能回退 ;动态规划则会根据以前的选择结果对当前进行选择，有回退 功能。动态规 划主要运用于二维或三维问题，而贪心一般是一维问题。4. 贪心算法的核心贪心算法的核心问题是选择能产生问题最优解的最优度量标准， 即具体的贪 心策 略。贪心策略决定着贪心算法是爆发或者是灭亡。所以，选择一个合理、正 确的贪心策略 是至关重要的。下面用例子说明:第一个例子我们选用大家熟知的 0/1 背包问题。给定 n 种物品和一个背包。物品i的重量是W,其价值为乂，背包的容量为C。在选择物品i装入背包时，不可以选 择物品i的一部分，一定要全部装入背包，i乞i乞n。应如何选择装 入背包的物品，使得装入背包中物品的总价值最大 ？设xi表示物品i装入背包的情况，根据问题的要求，有如下约束条件和目标函数:nZ WVi= Ci 丄 i-亠I-亠0兰Xj兰1(1兰i兰n)nmax、vi xi并使目标函数式达到最大的解i丄于是，背包问题归结为寻找一个满足约束条件式， 向量 X =(X，X2,x n)。现在有一个容量为 50 的背包，共有三个物品，重量为别为 20、30、10，价 值分别为 60、120、50。现使用贪心算法来放置物品，贪心策略也对应有三种， 分别是根据重量、价格、重量与价格比。根据重量的贪心策略，即优先放置重量小的物品，以此来达到放置更多个物 品的目的。首先需要将物品按照重量从小到大重新排序，然后从小到大的放置物品，直至下个物品无法放进背包为止。伪代码如下：publicclass worseGreedy publicstaticvoiddepend/ onDepWeight( double 叩 a.double c, int ans)/ the / weight to select/ goodsdouble w =System. arraycn ewdouble a0. opy (a0, 0, w, 0, w.len gthEn umerati on Search sea =；len gth ); new En umerati on Search。；Quick. Sort (w);length ; i+) for ( int i = 0; wi = c & i w. c = c - wi;int j = sea.search(a0, wi); ansj = 1;程序的运行结果见附录。 根据价格的贪心策略，即优先放置价格比较高的物品，以此来达到背包价格 更高的目的。首先需要将物品按照价格从大到小重新排序，然后依次放置物品， 直至下个物品超出背包容量为止。伪代码如下：publicstaticvoid DepPrice( double a, double c, int ans) / depend on/ the price/ to select goodsdouble p = newdouble a1. length ;System. arraycopy (a1, 0, p, 0, p. length );EnumerationSearch sea = new EnumerationSearch();Quick. Sort (p);int i = (p. length - 1);int j = sea.search(a1, pi);while (a0j = 0) c = c - a0j;ansj = 1;i-;j = sea.search(a1, pi); 程序的运行结果见附录。 根据重量与价格比值的贪心策略，即优先放置“性价比”高的 物品，以此来 达到背包价格最大的目的。 首先需要求出各个物品的价格与重量的比值， 然后按 照这个参数来重新排序物品， 价重比高的放前面。 最后一次放入物品， 直至下 个 物品超出背包容量为止。伪代码如下：publicstaticvoidDepWePr( double a,double c, int ans) / dependon/ the/ weight/ andpricedouble w = newdouble a0. System. arraycopy (a0, 0, w, 0, w.length ; / the weight of goodslength ); / copy the arraydouble p = n ewdouble a0. len gth ;/ the price of goodsSystem. arraycopy (a1, 0, p, 0, p.len gth ); / copy the arraydouble pw =newdouble w. length ;for ( int i = 0; i w.len gth ; i+)/ price/weight pwi = pi / wi;double wpw =System. arraycopySystem. arraycopyn ewdouble 2w.(w, 0, wpw0, 0, w. (pw, 0, wpw1, 0, w.len gth ;/ record the table of/ weight and pw len gth );len gth );En umerati on Search seanew En umerati on Search();Quick. Sort (pw);int i = (pw. len gth - 1); int j = sea.search(wpw1, pwi); while (wpw0j = 0) c = c - wpw0j;an sj = 1;i-;j = sea.search(wpw1, pwi); 程序运行结果见附录。 根据程序运行的结果，我们分别得到三个答案。放置的物品方案分别为：10 20、30 20、10 30 0如此看来，根据价格的贪心策略是最“贪心”的。 其实不然，根 据价格与重量比值的贪心策略的适应范围更加广阔，效果一般来说 也更加的好。本例中 受到小数据的局限性，无法发挥出其真正的效果。贪心策略之所以能成为贪心算法的核心，就是因为它决定着贪心算法是爆发 还是灭 亡，以及爆发的程度。上面的例子用三种不同的贪心策略， 结果也截然不 同。当扩大问题规模时，这种差距就更加的明显。5. 贪心算法的特点货郎担问题（或称旅行商问题或巡回售货员问题），是 NP 问题中的著名问题 它通常 的提法是：货郎到各村去卖货，再回到出发点处，每村到且仅到一次。为 其设计一种路 线，使得所用旅行售货的时间最短。建立数学模型时，把村庄设为结点，村庄与村庄之间的路线设为结点之间的带权的边，则货郎担问题转化为在图上寻求最优Hamilton 圈问题。即在加权图上求一个 Hamilton 圈 Ch 使得W(Ck)二、w(e) = min各个 Hamilton 圈的权。e誉k 贪心算法每选入一边都保证了是当前可选边中权值最小的边， 这便是“贪心”的含义。基本思想为首先选择图中任意顶点u,并将u置于顶点集合的子集S中。如果S是顶点集合V的真子集，就继续选择顶点j添加到子集S中，cij是权值最小的边。按照同样的步骤不断进行贪心选择，直到子集S=V 为止。此时，选取到的所有的边就构成了一棵最小生成树。伪代码如下：publicvoid find( int distanee,int j=1; /start ing city for ( int i=0;idistanee.an si=j;j=mi n(dista ncej-1,a ns);privateint min( int a, int b)int minN=0;int temp=100;En umerati on Search sea = for ( int i=0;ia. length ;i+)int ans)length ;i+)new En umerati on Search();if (sea.search(b, (i+1)=-1) if (ai3-5-8-4-6-7-2-1 ，而贪心算法的答案为： 1-3-4-2-5-6-7-8-1 。动态规划法需要走的路程为 21 ，而贪心算法需要 走的路 程为 25。这就是贪心算法的特点，虽快但不一定准。贪心算法每次都是 局部寻优， 很 容易会陷入局部最优解的波谷。 所以，贪心算法总结起来一共有三 个小缺点。1) 不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是 最优的 选择，因此并不从整体上加以考虑。2) 贪心算法只能用来求某些最大或最小解的问题。从前面的讨论中，背包 问题要 求得到最大价值是可行的，但是在另外一个求解最小路径时采用 贪心算法得到 的结果并不是最佳。3) 贪心算法只能确定某些问题的可行性范围。 贪心算法的优点已经提到了，就是 快，通常是线性到二次式，不需要多少额 外的内存。 一般二次方级的存储要浪费额外的 空间， 而且那些空间经常得不出正 解。但是，使用贪心算法时，这些空间可以帮助算法 更容易实现且更快执行。如 果有正确贪心性质存在，那么一定要采用 !因为它容易编写， 容易调试，速度极 快，并且节约空问。几乎可以说，此时它是所有算法中最好的。6.结束语贪心算法是很常见的算法， 贪心策略是最接近人的日常思维的一种解题策略， 虽然 它不能保证求得的最后解一定是最佳的， 但是它可以为某些问题确定一个可 行性范围。 贪心算法所作的选择依赖于以往所作过的选择， 但决不依赖于将来的 选择，这使得算法 在编码和执行过程中都有一定的速度优势。 对于一个问题的最 优解只能用穷举法得到 时， 用贪心算法是寻找问题最优解的较好算法。 对一个问 题可以同时用几种方法解 决， 贪心算法并不是对所有的问题都能得到整体最优解 或是最理想的近似解时， 就需 判断贪心性质的正确性了。 与回溯法、 动态规划法 等比较，它的适用区域相对狭窄许总之，如果一个贪心解决方案存在，就使用它7.参考文献：1 肖衡浅析贪心算法J荆楚理工学院学报.2009.092 常友渠，肖贵元，曾敏贪心算法的探讨与研究J重庆电力高等专科学校学报.第 13 卷 , 第 3 期3 汪莹论贪心算法在图论中的应用J南京邮电大学学报4 董军军动态规划算法和贪心算法的比较与分析J软件导刊.第7 卷第 2 期5 林章美 .货郎担问题的若干解法 J.6 王红梅算法设计与分析M北京：清华大学出版社.200677 江红，余青松.Java程序设计教程M.8.附录源代码:package Algorithm.ZeroPack.C onimport SOVU.util.Sca nner;import java.util.Arrays;import Algorithm.ZeroPack.Greedy.*;publicclass Con sole * param args*/publicstaticvoidmain( Stri ng args) / TODO Auto-ge nerated method stubScanner in = new Scann er(System. int n um; / in ); / input something the n umber of items double c; / the capacity of the rucksack);System. out .println(How big is this rucksack capacity?c = in.n extDouble();System. out .println(How manu items? );num = in.n extI nt();intan s1=n ewi ntn um;/ the an swerintan s2=n ewi ntn um;/ the an swerintan s3=n ewi ntn um;/ the an swerfor(int i = C);i n um; i+)/ i nitializationan s1i = 0;an s2i = 0;an s3i = 0;double table =System. out .println(n ewdouble 2 num; please in put the table/ the weight and price);for (int i = 0; i n um; i+) /in put the tableSystem. out .println(The weight of NO.+ (i + 1) + is: );table0i = in.n extDouble();+ (i + 1) +is: );System. out .println( The price of NO. table1i = in.n extDouble();worseGreedy. DepWeight (table, c, an s1);System. out .println(Depend on theweight +Arrays. toStri ng (an s1);worseGreedy. DepPrice (table, c, an s2);System. out .println(Depend on thedouble w =n ewdouble a0.System arraycopy (a0, 0, w, 0, w. double p =n ewdouble a0.System .arraycopy (a1, 0, p, 0, p.double pw = n ewdouble w.for ( int i = 0; i w.len gthprice +Arrays. toStr ing (an s2)； betterGreedy. DepWePr (table, c, ans3);len gth ;/ the weight of goodslen gth ) ;/ copy the arraylen gth ;/ the price of goodslen gth ) ;/ copy the arraylen gth ;；i+)System. out .println( price +Arrays. toStri ngSystem. out .println(Depe nd on the weight and (an s3);over );package Algorithm.ZeroPack.Greedy;import QuickSort.Quick;import Search.E numerati on Search;publicclass betterGreedy publicstaticvoidDepWePr( double a,depend ondouble c, int ans) / the/ weight/ andpricedouble wpw =n ewdouble 2w.len gth ;/ record the table of/ weight and pwSystem. arraycopySystem. arraycopy(w, 0, wpw0, 0, w. (pw, 0, wpw1, 0, w.len gth );len gth );/ price/weight pwi = pi / wi;Quick. Sort (pw);int i = (pw.len gth - 1);int j = sea.search(wpw1, pwi);while (wpw0j = 0) c = c - wpw0j;En umerati on Search seanew En umerati on=Search();an sj = 1;i-;j = sea.search(wpw1, pwi);package Algorithm.ZeroPack.Greedy;import QuickSort.Quick;import Search.E numerati on Search;/publicclass worseGreedy publicstaticvoid DepWeight( double 叩 a. double c, int ans)depend/ on/ the/ weight to select/ goodsdouble w = n ewdouble a0. len gth ;System. arraycopy (a0, 0, w, 0, w. len gth );En umerati on Search sea =new En umerati on Search();Quick. Sort (w);for (int i = 0; wi = c & i w.len gth ; i+) c = c - wi;int j = sea.search(a0, wi);an sj = 1;depend onpublicstaticvoidDepPrice( double 叩a, double c, int ans) / the price/ to select goodsdouble p = n ewdouble a1. len gth ;System. arraycopy (a1, 0, p, 0, p.len gth );En umerati on Search sea =new En umerati on Search();Quick. Sort (p);int i = (p.len gth - 1);int j = sea.search(a1, pi);while (a0j = 0) c = c - a0j;an sj = 1;i-;j = sea.search(a1, pi);package QuickSort; publicclass Quick publicstaticvoid Sort( double a) QuickSort (a,0,a. length -1);privatestaticvoid QuickSort( double r, int first , int end)int pivot;if (firstend)pivot= Partition (r,first,end); QuickSort (r,first,pivot-1); QuickSort (r,pivot+1,end); privatestaticint Partition ( double r, int first , int end) int i=first;int j=end;double tmp;while (ij)while (ij&ri=rj) j-;if (ij)tmp=ri; ri=rj;rj=tmp; i+;while (ij&ri=rj) i+;if (ij)tmp=ri; ri=rj;rj=tmp; j-; return i;package Search;publicclass EnumerationSearch publicint search( double a, double goal)int add=-1;for ( int i=0;ia. length ;i+)if (ai=goal)publicintintforadd=i; break ;return add;search( int a,add=-1;(int i=0;ia.lengthif (ai=goal)add=i;break return add;int goal)；i+)package TSP.console;import java.util.Arrays;import TSP.find.*;publicclass console /* param args*/ publicstaticvoid main(String args) / TODO Auto-generated method stubint distance = / 各个节点之间路径长度的二维数组0, 2, 1, 3, 4, 5, 5, 6,1, 0, 4, 4, 2, 5, 5, 6,5, 4, 0, 2, 2, 6, 5, 6,5, 2, 2, 0, 3, 2, 5, 6,4, 2, 4, 2, 0, 3, 5, 6,4, 2, 4, 2, 3, 0, 5, 6,4, 2, 4, 2, 4, 3, 0, 6,4, 2, 4, 2, 8, 3, 5, 0;int ans =newint distance. length ;Arrays. fill (ans, 0);TSPadjline fin = new TSPadjline();long preTime = System.currentTimeMillis();fin.find(distance, ans);long aftTime = System.currentTimeMillis();long currentTime = aftTime - preTime;ms );System. out .println( the time is ： + currentTime+ System. out .println(Arrays. toString (ans);int s=0; / 路程for ( int i=0;ians. length -1;i+) s=s+distanceansi-1ansi+1-1; s=s+distanceansans. length -1-1ans0-1;System. out .println( 路程： +s);package TSP.fi nd;import Search.E numerati on Search;publicclass TSPadjl ine /adjace nt line publicvoid find( int distanee,int j=1; /start ing cityfor ( int i=0;idistanee. length an si=j; j=mi n(dista ncej-1,a ns); privateint min( int a, int b)int minN=0;int temp=100;En umerati on Search sea =newfor ( int i=0;ia. length ;i+) if (sea.search(b, (i+1)=-1) if (ai Cons 口 I 色(l)Java Application D:Program Ales (x86)VavajreAbhjavaw.exe (2013-12-6 下AMslOrOS) How Mg lachls mu+qouZ capacity?Haw ma.nu items?Depend on the weightlf 0尸 1 pricelr 1FDepend on th 皂 0 weight and price G,Depend on rheoverpl 皂 ase input the： 匸 ableThe weight of 30 1 xa:The price of NO 申 1 is:The weigiht of NO. 2 is:The price of NO.2 is:The weight af N0 3 13!i aThe price of NO 3 is: 背包问题截图怎 Problems Javadoc 庖 Oedaration 曰 Console 3J X娥1vterminatedTSP Java Application D:Program Files (x&6)Javajrei7bfnjavaw.exe (2013-12-6 下=04:21:57 路轻为E 20457613对应城市顺序：0-A -4-7-3-5-6-1 -0 最垣鞠为：21i0生成斎有合法玻市流用时：2618Dv秒幼态眾划求解过程用时： 1 0莹秒动态规划法求解TSP问题RI Probllems i Jwadoc 圖 DedarationJ 闫 Console 、X Ivtenninated Console 卩 iavai Application D:Program Files (x86)Javajre7lbirtjavaw.exe (2013-12-6 FAR05:31:22) the tiree i : Oms llr 4 仏 2f 5, 6, 7f sj踣程：25贪心算法求解TSP问题