贪心算法设计及其实际应用研究毕业论文.doc

贪心算法设计及其实际应用研究毕业论文 目 录 本科毕业论文（设计）任务书 I 文献综述 i 本科毕业论文（设计）开题报告 - 1 - 正文 1 摘要 1 第1章 引言 2 1.1研究背景 2 1.2研究内容 2 1.3研究目标 2 1.4研究意义 2 1.5 本文组织 3 第2章 贪心算法的基本知识概述 4 2.1 贪心算法定义 4 2.2 贪心算法的基本思路及实现过程 4 2.3贪心算法的核心 4 2.4贪心算法的基本要素 5 2.5 贪心算法的理论基础 6 2.6贪心算法存在的问题 7 第3章 经典问题解决及其优缺点 8 3.1 哈夫曼编码 8 3.2单源最短路径问题(Dijkstra算法) 10 3.3最小生成树问题(Prim算法、Kruskal算法) 12 第4章 多处最优服务次序问题 15 4.1 问题的提出 15 4.2 贪心选择策略 15 4.3 问题的贪心选择性质 15 4.4 问题的最优子结构性质 15 4.5 算法结果分析 16 第5章 删数问题 17 5.1 问题的提出 17 5.2 贪心算法策略 17 5.3 问题的贪心选择性质 17 5.4 问题的最优子结构性质 17 5.5 编码 18 第6章 汽车加油问题 19 6.1 问题的提出 19 6.2 编码分析 19 6.3 贪心算法策略 19 6.4 贪心算法正确性证明 20 6.5 贪心算法时间复杂度分析 20 第7章 最优合并问题 21 7.1 问题的提出 21 7.2 原理分析 21 7.3 算法时间复杂度分析 21 第8章 会场安排问题 22 8.1 问题的提出 22 8.2 编码分析 22 8.3 贪心算法 22 8.4 最优解证明 23 8.5 算法时间复杂度分析 23 第9章 贪心算法的C++实现 24 9.1 C++语言概述 24 9.2 具体实现步骤 25 9.3程序编码与程序调试 29 第10章 总结与展望 31 10.1总结 31 10.2展望 31 参考文献 32 附录 33 致谢 41 本科毕业论文（设计）指导教师评阅表 a 本科毕业论文（设计）交叉评阅表 b 本科毕业论文（设计）答辩记录 c  本科毕业论文（设计）任务书 论文（设计）题目 贪心算法设计及其实际应用研究 系别、专业 信息管理系计算机科学与技术 学生姓名 学号 指导教师姓名 开题日期 2011年11月28日 论文（设计）的主要内容（技术指标）与要求： 本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的性质，通过研究几个经典问题，将贪心算法应用到实际中。 进 度 安 排 研究进度安排： 2010年10月-2010年11月，根据课题研究的内容，收集资料 2010年11月- 2010年12月，深入探讨该算法中的几个经典问题 2010年12月- 2011年1月，整理研究内容，并作进一步的修改 2011年1月- 2011年2月，归纳总结，形成一份完整的课题论文 系意见： 注：1、任务书由指导老师填写。 2、任务书必须在第七学期13周前下达给学生。  文献综述 贪心算法设计及其实际应用研究 信息管理系， 402460 摘 要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。 关键词：贪心算法；哈夫曼编码；最小生成树；多处最优服务次序问题；删数问题 0 引言 为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你