贪心算法设计及其实际应用研究

《贪心算法设计及其实际应用研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哈尔滨师范大学学　年　论　文题目关于贪心算法研究学生***指导教师年级2009级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程学院哈尔滨师范大学年　　月论　文　提　要为满足人们对大数据量信息处理的渴望，解决各种实际问题，计算机算法学得到了飞速的发展。设计一个好的求解算法更像是一门艺术而不像是技术。当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观、高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择

2、；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且所给出的算法一般比动态规划算法更加简单、直观和高效。贪心算法设计及其实际应用研究***摘要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪

3、心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法

4、的特点来解决。关键词：贪心算法；哈夫曼编码；最小生成树；多处最优服务次序问题；删数问题一、贪心算法的基本知识概述（一）贪心算法的核心贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解

5、或较优解。（二）贪心算法的理论基础正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论—拟阵。“拟阵”理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。拟阵M定义为满足下面3个条件的有序对（S，I）：（1）S是非空有限集；（2）I是S的一类具有遗传性质的独立子集族，即若B∈I，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集￠必为I的成员；（3）I满足交换

6、性质，即若A∈I，B∈I且

7、A

8、<

9、B

10、，则存在某一元素x∈B-A，使得A∪{x}∈I。定理1.1拟阵M中所有极大独立子集具有相同大小。引理1.1（拟阵的贪心选择性质）设M=（S，I）是具有权函数M的带权拟阵，且S中元素依权值从大到小排列，又设x∈S是S中第一个使得{x}是独立子集元素，则存在S的最优子集A使得x∈A。引理1.2设M=(S，I)是拟阵。若S中元素x不是空集￠的一个可扩元素，则x也不可能是S中任一独立子集A的可扩展元素。引理1.3（拟阵的最优子结构性质）设x是求带权拟阵M=（S，I）的最优子集的贪心算

11、法Greedy所选择的S中的第一个元素。那么，原问题可简化为求带权拟阵M'=（S'，I'）的最优子集问题，其中S'={y

12、y∈S且{x，y}∈I}I'={B

13、BS-{x}且B∪{x}∈I}M'的权函数是M的权函数在S'上的限制（称M'为M关于元素x的收缩）。定理1.4（带权拟阵贪心算法的正确性）高M=（S，I）是具有权函数W的带权拟阵，算法Greedy返回M的最优子集。适宜于用贪心策略来求解的许多问题都可以归结为在加权拟阵中找一个具有最大权值的独立子集的问题，即给定一个加权拟阵M=（S，I），若能找出一个独立且具有

14、最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。我们认为，针对绝大多数的信息学问题，只要它具备了“拟阵”的结构，便可用贪心策略求解。拟阵理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。二、贪心算法的C++实现（一）哈夫曼算法的实现哈夫曼算法思路为：（1）以n个字母为结点构成n棵仅含一个点的二叉