算法分析论文 贪心算法研究.doc

贪心算法研究软工1203 吴康伟 201226630314摘 要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一 步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。关键词：贪心算法；哈夫曼编码；最小生成树；多处最优服务次序问题；删数问题1.基本知识贪心算法的含义：贪心算法是通过一系列的选择来得到问题解的过程。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值。2.贪心算法特点从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做出的选择。或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。3.贪心算法存在的问题 （1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑。 （2）贪心算法只能用来求某些最大或最小解的问题。例如找零钱问题要求得到最小数量，就可以采用贪心算法，但是在另外一个求解权值最小路径时采用贪心算法得到的结果并不是最佳。 （3）贪心算法只能确定某些问题的可行性范围。 4.经典问题解决及其优缺点 （1）哈夫曼编码 问题提出：哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 基本原理：对每一个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单。由于任一字符的代码都不是其他字符代码的前缀，从编码文件中不断取出代表某一字符的前缀码，转换为原字符，即可逐个译出文件中的所有字符。可以用二叉树作为前缀编码的数据结构。在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看做是从树根到代表该字符的树叶的一条道路。代码中每一位的0或1分别作为指示某结点到左儿子或右儿子的“路标”。优点：哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多位来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。 缺点1.慢位流实现2.相当慢的解码（比编码慢）3.最大的树深度是32（编码器在任何超过32位大小的时候退出）。 （2）单源最短路径 问题提出：给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 Dijkstra算法 基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，数组dist就记录了从源到所有其它顶点之间的最短路径长度。 优点：Dijkstra的思想是按递增长度来产生路径,每次选出当前已经找到的最短的一条路径,它必然是一条最终的最短路径。因此每次找出当前距离数组中最小的,必然是一条最终的最短路径。缺点：对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O（n2）时间。算法的其余部分所需要时间不超过O（n2）。 （3）最小生成树 问题提出：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。的一棵最小生成树。Prim算法 基本思想：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jv-s，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。优点：该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U=V，即T包含了C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小，因此这是一种“贪心”的策略。 缺点：该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。 Kruskal算法 基本思想：首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。 优点：当输入的连通带权图有e条边时，则将这些边依其权组成优先队列需要O(e)时间，在上述算法的while循环中，DeleteMin运算需要O(loge)时间，因此关于优先队列所作运算的时间为O(eloge)。实现UnionFind所需的时间为O(eloge)或O(elog*e)。所以Kruskal算法所需的计算时间为O(eloge)。 缺点：当e=(n2)时，Kruskal算法比Prim算法差，但当e=O(n2)时，Kruskal算法却比Prim算法好得多。Kruskal算法的时间主要取决于边数。它较适合于稀疏图。5.贪心算法的实际应用 （1）多处最优服务次序问题 （2）删数问题 （3）汽车加油问题 （4）最优合并问题 （5）会场安排问题总 结 贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解