算法分析论文

1、贪心算法研究摘 要 ： 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直 接去求每一 步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解， 这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体 上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的 特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于 以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪 心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法 解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路 及

2、实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算 法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希 望通过贪心算法的特点来解决。关键词 ：贪心算法；哈夫曼编码；最小生成树；多处最优服务次序问题；删数问 题1. 基本知识贪心算法的含义：贪心算法是通过一系列的选择来得到问题解的过程。贪心算法 是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看 来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择 只是在某种意义上的局部最优解算法。这种策略是一种很简洁的方法，对许多问 题它能产生整体最优解，但不能保证总是有效，因为它不是

3、对所有问题都能得到 整体最优解，只能说其解必然是最优解的很好近似值。2. 贪心算法特点从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，后面的 每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未 做出的选择。或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法 说，就是每次都处理出一个最好的方案。3. 贪心算法存在的问题（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优 的选择，因此并不从整体上加以考虑。（2）贪心算法只能用来求某些最大或最小解的问题。例如找零钱问题要求得到最 小数量，就可以采用贪心算法，但是在另外一个求解权值最小路

4、径时采用贪心算 法得到的结果并不是最佳。（3）贪心算法只能确定某些问题的可行性范围。4. 经典问题解决及其优缺点（ 1）哈夫曼编码 问题提出：哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压 缩率通常在20%- 90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立 一个用 0，1 串表示各字符的最优表示方式。基本原理：对每一个字符规定一个 0，1 串作为其代码，并要求任一字符的代码都 不是其它字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方 法非常简单。由于任一字符的代码都不是其他字符代码的前缀，从编码文件中不 断取出代表某一字符的前缀码，转换为原字符，即可逐个

5、译出文件中的所有字符。 可以用二叉树作为前缀编码的数据结构。在表示前缀码的二叉树中，树叶代表给定的字符， 并将每个字符的前缀码看做是从树根到代表该字符的树叶的一条道路 代码中每一位的 0或 1分别作为指示某结点到左儿子或右儿子的“路标” 。 优点：哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每 个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而 不常见的符号需要很多位来表示。哈夫曼算法在改变任何符号二进制编码引起少 量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。 缺点 1. 慢位流实现 2. 相当慢的解码 （比编码慢） 3. 最大的

6、树深度是 32（编码器在 任何超过 32 位大小的时候退出） 。（2）单源最短路径 问题提出：给定带权有向图 G=（V,E） ，其中每条边的权是非负实数。另外，还给定 V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra 算法 基本思想：设置顶点集合 S 并不断地作贪心选择来扩充这个集合。 一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到 u且中间只经过S中顶点的路称为从 源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应

7、的最短特殊路径长度。Dijkstra 算法每次从V-S中取出具有最短特殊路长度的顶点 u，将u添加到S中, 同时对数组dist作必要的修改。一旦 S包含了所有V中顶点，数组dist就记录 了从源到所有其它顶点之间的最短路径长度。优点：Dijkstra 的思想是按递增长度来产生路径，每次选出当前已经找到的最短的 一条路径 , 它必然是一条最终的最短路径。因此每次找出当前距离数组中最小的 , 必然是一条最终的最短路径 缺点：对于具有 n 个顶点和 e 条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra 算法的主循环体需要 0(n)时间。这个循环需要执行n-1次，所 以完成循环需要

8、0 ( n2)时间。算法的其余部分所需要时间不超过0 ( n2)。( 3)最小生成树问题提出：设 G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，贝V称 G'为G的 生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为 G的最小生成树。的一棵最小生成树。Prim算法 基本思想：首先置 S=1，然后，只要S是V的真子集，就作如下的 贪心选择：选取满足条件 i?S ， j?v-s ，且 cij 最小的边，将顶点 j 添加到 S 中。这个过程一直进行到S=V时为止。在这个过程中选取到的

9、所有边恰好构成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个孤立的连通分支。将所有 的边按权从小到大排序。然

10、后从第一条边开始，依边权递增的顺序查看每一条边， 并按下述方法连接两个不同的连通分支：当查看到第 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=Q(n2)时，Kruskal算法比Prim算法差，但当e=0(n2)时，Kruskal算法却比 Prim 算法好得多。 Kruskal 算法的时间主要取决于边数。它较适合于稀 疏图。5. 贪心算法的实际应用(1)多处最优服务次序问题 (2)删数问题 (3)汽车加油问题 (4)最优合并问题 ( 5)会场安排问题总结贪心算法是很常见的算法， 贪心策略是最接近人的日常思维