算法分析论文

《算法分析论文》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、法只能用来求某些最大或最小解的问题。例如找零钱问题要求得到最小数量，就可以采用贪心算法，但是在另外一个求解权值最小路径时采用贪心算法得到的结果并不是最佳。（3）贪心算法只能确定某些问题的可行性范围。4.经典问题解决及其优缺点（1）哈夫曼编码问题提出：哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。基本原理：对每一个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。编码的前缀性质

5、可以使译码方法非常简单。由于任一字符的代码都不是其他字符代码的前缀，从编码文件中不断取出代表某一字符的前缀码，转换为原字符，即可逐个译出文件中的所有字符。可以用二叉树作为前缀编码的数据结构。在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看做是从树根到代表该字符的树叶的一条道路。代码中每一位的0或1分别作为指示某结点到左儿子或右儿子的“路标”。优点：哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多位来表示。哈夫曼算法在改变任何符号

6、二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。缺点1.慢位流实现2.相当慢的解码（比编码慢）3.最大的树深度是32（编码器在任何超过32位大小的时候退出）。（2）单源最短路径问题提出：给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra算法基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度

7、已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，数组dist就记录了从源到所有其它顶点之间的最短路径长度。优点：Dijkstra的思想是按递增长度来产生路径,每次选出当前已经找到的最短的一条路径,它必然是一条最终的最短路径。因此每次找出当前距离数组中最小的,必然是一条最终的最短路径。缺点：对于具有

8、n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时