发布时间 : 星期六 文章基于算法本科最新毕业论文更新完毕开始阅读6a4eaa660166f5335a8102d276a20029bd64638e
(此文档为word格式，下载后您可任意编辑修改！)
本科毕业论文（设计）
题 目 贪心算法设计及其实际应用研究
系 别 信 息 管 理 系 专 业 计算机科学与技术 年 级 2007级 学 号 姓 名 指 导 教 师 成 绩 _______________________
二〇一一年五月十五日
I
目 录
本科毕业论文（设计）任务书 ............................................ 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
I
第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
I
附录 ................................................................. 33 致谢 ................................................................. 41 本科毕业论文（设计）指导教师评阅表 .................................... a 本科毕业论文（设计）交叉评阅表 ........................................ b 本科毕业论文（设计）答辩记录 .......................................... c
I