贪心算法论文终稿

《贪心算法论文终稿》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本科毕业论文（设计）题目贪心算法设计及其实际应用研究系别信息管理系专业计算机科学与技术年级2006级学号222006602054062姓名蒋远丽指导教师汪维清成绩_______________________二〇一〇年五月十五日nn目录西南大学本科毕业论文（设计）任务书I文献综述i西南大学本科毕业论文（设计）开题报告-1-正文1摘要1第1章引言21.1研究背景21.2研究内容21.3研究目标21.4研究意义21.5本文组织3第2章贪心算法的基本知识概述42.1贪心算法定义42.2贪心算法的基本思路及实现过程42.3贪心算法的核心42.4贪心算法的基本要素52.

2、5贪心算法的理论基础62.6贪心算法存在的问题7第3章经典问题解决及其优缺点83.1哈夫曼编码83.2单源最短路径问题(Dijkstra算法)103.3最小生成树问题(Prim算法、Kruskal算法)12第4章多处最优服务次序问题154.1问题的提出154.2贪心选择策略154.3问题的贪心选择性质154.4问题的最优子结构性质154.5算法结果分析16nn第5章删数问题175.1问题的提出175.2贪心算法策略175.3问题的贪心选择性质175.4问题的最优子结构性质175.5编码18第6章汽车加油问题196.1问题的提出196.2编码分析196.3贪心算

3、法策略196.4贪心算法正确性证明206.5贪心算法时间复杂度分析20第7章最优合并问题217.1问题的提出217.2原理分析217.3算法时间复杂度分析21第8章会场安排问题228.1问题的提出228.2编码分析228.3贪心算法228.4最优解证明238.5算法时间复杂度分析23第9章贪心算法的C++实现249.1C++语言概述249.2具体实现步骤259.3程序编码与程序调试29第10章总结与展望3110.1总结3110.2展望31参考文献32nn附录33致谢41本科毕业论文（设计）指导教师评阅表a本科毕业论文（设计）交叉评阅表b本科毕业论文（设计）答辩

4、记录cnnnn西南大学本科毕业论文（设计）任务书论文（设计）题目贪心算法设计及其实际应用研究系别、专业信息管理系计算机科学与技术学生姓名蒋远丽学号222006602054062指导教师姓名汪维清开题日期2009年11月28日论文（设计）的主要内容（技术指标）与要求：本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的性质，通过研究几个经典问题，将贪心算法应用到实际中。进度安排研究进度安排：2009年10月-2009年11月，根据课题研究的内容，收集资料2009年11月-2009年12月，深入探讨该算法中的

5、几个经典问题2009年12月-2010年1月，整理研究内容，并作进一步的修改2010年1月-2010年2月，归纳总结，形成一份完整的课题论文系意见：注：1、任务书由指导老师填写。2、任务书必须在第七学期13周前下达给学生。nnnnnn文献综述贪心算法设计及其实际应用研究蒋远丽西南大学荣昌校区信息管理系，重庆荣昌402460摘要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是

6、在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。关键词：贪心算法；哈夫曼编码；最小生成树；多处最优服务次序问题；删数问题0引言

7、为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。nn当一个问题具有最优子结构性质和贪心选择性质时，

8、贪心算法通常会给出一个简单、直观和高效