[贪心算法论文终稿.docVIP

本科毕业论文（设计） 题 目 贪心算法设计及其实际应用研究 系 别 信 息 管 理 系 专 业 计算机科学与技术 年 级 2006级 学 号 222006602054062 姓 名 蒋 远 丽 指 导 教 师 汪 维 清 成 绩 _______________________ 二〇一〇年五月十五日 目 录 西南大学本科毕业论文（设计）任务书 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  西南大学本科毕业论文（设计）任务书 论文（设计）题目 贪心算法设计及其实际应用研究 系别、专业 信息管理系计算机科学与技术 学生姓名 蒋远丽 学号 222006602054062 指导教师姓名 汪维清 开题日期 2009年11月28日 论文（设计）的主要内容（技术指标）与要求： 本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的性质，通过研究几个经典问题，将贪心算法应用到实际中。 进 度 安 排 研究进度安排： 2009年10月-2009年11月，根据课题研究的内容，收集资料 2009年11月- 2009年12月，深入探讨该算法中的几个经典问题 2009年12月- 2010年1月，整理研究内容，并作进一步的修改 2010年1月- 2010年2月，归纳总结，形成一份完整的课题论文 系意见： 注：1、任务书由指导老师填写。 2、任务书必须在第七学期13周前下达给学生。  文献综述 贪心算法设计及其实际应用研究 蒋远丽 西南大学荣昌校区信息管理系，重庆荣昌 402460 摘 要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速