发布时间 : 星期三 文章基于算法本科最新毕业论文更新完毕开始阅读6a4eaa660166f5335a8102d276a20029bd64638e
3.技术路线、研究方法和研究进度： （1）技术路线 题目分析——收集资料（网络和图书馆）——阅读资料——规划论文结构——整理资料——详细分析整理（贪心算法的基本含义、原理、实现过程、性质、特点、算法优缺点等）——分析该算法的实例及其优缺点（哈夫曼编码、单源最短路径问题(Dijkstra算法)、最小生成树问题(Prim算法、Kruskal算法)）——挑选几个经典实例研究并用c++实现（多处最优服务次序问题、删数问题、汽车加油问题、最优合并问题）——总结。 （2）研究方法 1）文献研究法：通过查询资料来收集研究所需要的基础知识；资料收集方式：利用网络资源、查找相关书籍、收集有关研究课题内容的报刊杂志等； 2）个案研究法、实验法：在资料收集完成之上，建立课题研究结构，思路清楚地对贪心算法的各方面进行分析、探讨、研究；包括：贪心算法的基本含义、基本原理和实现过程，其及贪心算法的性质、贪心算法的特点及优缺点等，分析由贪心算法解决的几个经典问题的理论以及它们各自的优缺点。从现实实际出发，从中选择几例进行深入研究，并以C++语言实现完成。 3）将所研究的内容按合理的思路组合及实例实现完成一篇完整的课题论文； （3）研究进度 2010年10月-2010年11月， 根据课题研究的内容，收集资料 2010年11月- 2010年12月， 深入探讨该算法中的几个经典问题 2010年12月- 2011年1月， 整理研究内容，并作进一步的修改 2011年1月- 2011年2月， 归纳总结，运行程序成功后，形成一份完整的课题论文 4.导师意见： 指导教师（签名）： 年 月 日 5.系意见： 系（盖章） 年 月 日 说明：开题报告应在教师指导下由学生独立撰写。在毕业论文（毕业设计）开始二周内完成，交指导教师审阅，并接受学校和学院检查。
正文
贪心算法设计及其实际应用研究
信息管理系， 402460
摘要：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择,也就是说，不
从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题也能产生整体最优解或者是整体最优解的近似解。本文首先介绍了贪心算法的核心、特点及算法本身存在的问题，接下来介绍了前人已经研究出来的成果，包括哈夫曼编码、单源最短路径、最小生成树等。然后结合实践，研究了多处最优服务次序问题、删数问题、汽车加油问题、最优合并问题、会场安排问题等。最后用代码实现其中的两个问题，对贪心算法的具体实现方法做了详细说明。
关键字：贪心算法；哈夫曼编码；最小生成树；最优服务次序；汽车加油问题
Greedy algorithm design and its practical application
Department of Information Management, University, , Chongqing
Abstract：Greedy algorithm is that, in the problem solving, it always made in the current appears to be the best option. In other words, not the best on the whole to be considered, in a sense. Greedy algorithm is not a right that all problems can be the overall optimal solution, but it covers a wide range of issues that overall optimal solution or approximate solution of the overall optimal solution. This paper describes the core of the greedy algorithm, characteristics and algorithms inherent problems, then presented the results of our predecessors studied out, including Huffman coding, single-source shortest path, minimum spanning tree and so on. Then with practice, study the various optimal service order issues, delete a few issues, car fuel, the optimal merger, venue arrangements and so on. At last, the code to achieve two of them on the greedy algorithm to do the concrete implementation method in detail.
Key words：greedy algorithm；Huffman coding；MST；Optimal service order;Automobile refueling
第1章 引言
1.1研究背景
为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，
为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且所给出的算法一般比动态规划算法更加简单、直观和高效。 1.2研究内容
贪心算法的定义（是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法），贪心算法的基本要素（最优子结构性质、贪心选择性质）、贪心算法的思路及过程，贪心算法的核心（贪心策略）及特性（无回溯）、探讨贪心算法存在的问题。然后分析已有成果运用贪心策略的解法（哈夫曼编码、单源最短路径问题、最小生成树等），结合实际中的例子（多处最优服务次序问题、删数问题、汽车加油问题、会场安排问题、最优合并问题），对贪心算法进行分析与运用。 1.3研究目标
通过本课题的研究来探讨贪心算法理论基础以及对贪心策略在更多实例中的运用做可行的研究，为贪心算法能够运用到更多的实际中的问题作示范。 1.4研究意义
贪心算法是计算机算法策略中常用的一个，往往在需要解决一些最优性问题时，都可以应用贪心算法。贪心算法的用法特点有：一是明显的贪心，一般此类应用问题本身就是贪心；二是贪心数据结构，如：堆，最小树；三是可证明贪心策略的贪心，这是我们最常见的；四是博弈、游戏策略，这些策略大多是贪心；五是求较优解或多次逼近最优解。通过用贪心算法求解以上问题，可以找到解决这些问题的最优算法，为其它的类似问题的解决有示范和例证作用。 1.5 本文组织
本文从如下方面进行组织：先提出贪心算法的基本知识，再从贪心算法的几个现有的成果研究探讨，然后对贪心算法中的几个经典问题进行研究，写出其中两个问题的代码，最后进行总结。