完整版基于算法本科最新毕业论文.docx

完整版基于算法本科最新毕业论文.docx

《完整版基于算法本科最新毕业论文.docx》由会员分享，可在线阅读，更多相关《完整版基于算法本科最新毕业论文.docx（59页珍藏版）》请在冰点文库上搜索。

完整版基于算法本科最新毕业论文

本科毕业论文（设计）

题目贪心算法设计及其实际应用研究

系别信息管理系

专业计算机科学与技术

年级2007级

学号

姓名

指导教师

成绩_______________________

二〇一一年五月十五日

本科毕业论文（设计）任务书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.1C++语言概述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引言

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。

虽然设计一个好的求解算法更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。

一般情况下,为了获得较好的性能,必须对算法进行细致的调整。

但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。

当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。

贪心算法通过一系列的选择来得到一个问题的解。

它所作的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。

尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。

而且所给出的算法一般比动态规划算法更加简单、直观和高效。

（1）基本知识

贪心算法的含义

贪心算法是通过一系列的选择来得到问题解的过程。

贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。

（2）贪心算法特点及存在的问题

1）贪心算法的特点

从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做出的选择。

2）贪心算法存在的问题

①不能保证求得的最后解是最佳的。

由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑。

②贪心算法只能用来求某些最大或最小解的问题。

例如找零钱问题要求得到最小数量，就可以采用贪心算法，但是在另外一个求解权值最小路径时采用贪心算法得到的结果并不是最佳。

③贪心算法只能确定某些问题的可行性范围。

（3）经典问题解决及其优缺点

1）哈夫曼编码

问题提出：

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。

其压缩率通常在20%～90%之间。

哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。

基本原理：

对每一个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。

这种编码称为前缀码。

编码的前缀性质可以使译码方法非常简单。

由于任一字符的代码都不是其他字符代码的前缀，从编码文件中不断取出代表某一字符的前缀码，转换为原字符，即可逐个译出文件中的所有字符。

可以用二叉树作为前缀编码的数据结构。

在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看做是从树根到代表该字符的树叶的一条道路。

代码中每一位的0或1分别作为指示某结点到左儿子或右儿子的“路标”。

优点：

哈夫曼编码是无损压缩当中最好的方法。

它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。

常见的符号需要很少的位来表示，而不常见的符号需要很多位来表示。

哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。

然而，它并不处理符号的顺序和重复或序号的序列。

缺点：

①慢位流实现②相当慢的解码（比编码慢）③最大的树深度是32（编码器在任何超过32位大小的时候退出）。

2）单源最短路径

问题提出：

给定带权有向图G=（V,E），其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称为源。

现在要计算从源到所有其它各顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

Dijkstra算法

基本思想：

设置顶点集合S并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。

设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。

一旦S包含了所有V中顶点，数组dist就记录了从源到所有其它顶点之间的最短路径长度。

优点：

Dijkstra的思想是按递增长度来产生路径,每次选出当前已经找到的最短的一条路径,它必然是一条最终的最短路径。

因此每次找出当前距离数组中最小的,必然是一条最终的最短路径

缺点：

对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O（n）时间。

这个循环需要执行n-1次，所以完成循环需要O（n2）时间。

算法的其余部分所需要时间不超过O（n2）。

3）最小生成树

问题提出：

设G=（V,E）是无向连通带权图，即一个网络。

E中每条边（v,w）的权为c[v][w]。

如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

生成树上各边权的总和称为该生成树的耗费。

在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

①Prim算法

基本思想：

首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：

选取满足条件iS，jv-s，且c[i][j]最小的边，将顶点j添加到S中。

这个过程一直进行到S=V时为止。

在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

优点：

该算法的特点是当前形成的集合T始终是一棵树。

将T中U和TE分别看作红点和红边集，V-U看作蓝点集。

算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。

MST性质保证了此边是安全的。

T从任意的根r开始，并逐渐生长直至U=V，即T包含了C中所有的顶点为止。

MST性质确保此时的T是G的一棵MST。

因为每次添加的边是使树中的权尽可能小，因此这是一种“贪心”的策略。

缺点：

该算法的时间复杂度为O（n2）。

与图中边数无关，该算法适合于稠密图。

②Kruskal算法

基本思想：

首先将G的n个顶点看成n个孤立的连通分支。

将所有的边按权从小到大排序。

然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：

当查看到第k条边（v,w）时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边（v,w）将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。

这个过程一直进行到只剩下一个连通分支时为止。

此时，这个连通分支就是G的一棵最小生成树。

优点：

当输入的连通带权图有e条边时，则将这些边依其权组成优先队列需要O（e）时间，在上述算法的while循环中，DeleteMin运算需要O（loge）时间，因此关于优先队列所作运算的时间为O（eloge）。

实现UnionFind所需的时间为O（eloge）或O（elog*e）。

所以Kruskal算法所需的计算时间为O（eloge）。

缺点：

当e=Ω（n2）时，Kruskal算法比Prim算法差，但当e=O（n2）时，Kruskal算法却比Prim算法好得多。

Kruskal算法的时间主要取决于边数。

它较适合于稀疏图。

1本课程研究的内容

通过资料收集、实际调查分析，最终形成自己的观点和见解，拟定以下内容进行探析：

（1）基本知识

1）贪心算法的含义

2）贪心算法的基本思路及实现过程

3）贪心算法的核心

4）贪心算法的基本性质

5）贪心算法的特点

6）贪心算法存在的问题

（2）经典问题解决及其优缺点

1）哈夫曼编码

2）单源最短路径问题（Dijkstra算法）

3）最小生成树问题（Prim算法、Kruskal算法）

（3）贪心算法的实际应用

1）多处最优服务次序问题

2）删数问题

3）汽车加油问题

4）最优合并问题

5）会场安排问题

2总结

贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围，因此贪心策略在各级各类信息学竞赛，尤其在对NPC类问题的求解中发挥着越来越重要的作用。

对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。

总之，充分利用贪心算法的优势，从局部最优出发，构造贪心策略比较容易，且简单易行。

参考文献：

[1]严蔚敏,吴伟民.数据结构（c语言版）[M].北京:

清华大学出版社,1997．

[2]M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京:

电子工业出版社,2004．

[3]谭浩强.C++面向对象程序设计[M].北京:

清华大学出版社,2006．

[4]常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,第13卷，第13期，2008.9.

[5]龚雄兴,堆与贪心算法[M],湖北襄樊学院，2003.

[6]张洁,朱莉娟.贪心算法与动态规划的比较[M].新乡师范高等专科科学学报,第19卷，第五期，2005.9.

[7]殷建平.关于贪心算法的正确性证明[M].江西师范大学学报（自然科学版）,第22卷增刊,1998.10.

[8]王晓东.计算机算法设计与分析（第3版）[M]．北京：

电子工业出版社,2007．

[9]余祥宣,崔国华,邹海明.计算机算法基础[M].武汉:

华中科技大学出版社,2000．

[10]卢开澄.计算机算法导引—设计与分析[M].北京:

清华大学出版社,2003．

[11]M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京电子工业出版社（影印版）,51-52.

[13]王晓东.计算算法设计与分析（第二版）[M].北京:

电子工业出版社,2OO4.

[14]王晓东.算法设计与分析[M].北京:

清华大学出版社,2O04.

[15]苏德富,钟诚.计算机算法设计与分析[M].北京:

电子工业出版社,2001:

60-62.

[16]URLforumsthreads134122.aspx

[21]MelhiM,IpsonSS,Boothw.Anoveltriangulationprocedureforthinning[22]FlorescuD,GrunhagenA,KossmannD.XL:

APlatformforWebServices[C].Proc.ofthe1stBiennialConferenceoninnovativeDataSystemsResearch,2003.

本科毕业论文（设计）开题报告

论文题目

贪心算法设计及其实际应用研究

系别专业

信息管理系

计算机科学与技术

年级

2007级

开题日期

2010年11月28日

学号

姓名

指导教师

1.本课题研究意义：

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。

虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。

一般情况下，为了获得较好的性能，必须对算法进行细致的调整。

但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。

当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。

贪心算法通过一系列的选择来得到一个问题的解。

它所作的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。

尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。

而且所给出的算法一般比动态规划算法更加简单、直观和高效。

2.研究内容：

（1）基本知识

1）贪心算法的含义

2）贪心算法的基本思路及实现过程

3）贪心算法的核心

4）贪心算法的基本性质

5）贪心算法的特点

6）贪心算法存在的问题

（2）经典问题解决及其优缺点

1）哈夫曼编码

2）单源最短路径问题（Dijkstra算法）

3）最小生成树问题（Prim算法、Kruskal算法）

（3）贪心算法的实际应用

1）多处最优服务次序问题

2）删数问题

3）汽车加油问题

4）最优合并问题

5）会场安排问题

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

摘要：

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择,也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题也能产生整体最优解或者是整体最优解的近似解。

本文首先介绍了贪心算法的核心、特点及算法本身存在的问题，接下来介绍了前人已经研究出来的成果，包括哈夫曼编码、单源最短路径、最小生成树等。

然后结合实践，研究了多处最优服务次序问题、删数问题、汽车加油问题、最优合并问题、会场安排问题等。

最后用代码实现其中的两个问题，对贪心算法的具体实现方法做了详细说明。

关键字：

贪心算法；哈夫曼编码；最小生成树；最优服务次序；汽车加油问题

Greedyalgorithmdesignanditspracticalapplication

DepartmentofInformationManagement,University,,Chongqing

Abstract：

Greedyalgorithmisthat,intheproblemsolving,italwaysmadeinthecurrentappearstobethebestoption.Inotherwords,notthebestonthewholetobeconsidered,inasense.Greedyalgorithmisnotarightthatallproblemscanbetheoveralloptimalsolution,butitcoversawiderangeofissuesthatoveralloptimalsolutionorapproximatesolutionoftheoveralloptimalsolution.Thispaperdescribesthecoreofthegreedyalgorithm,characteristicsandalgorithmsinherentproblems,thenpresentedtheresultsofourpredecessorsstudiedout,includingHuffmancoding,single-sourceshortestpath,minimumspanningtreeandsoon.Thenwithpractice,studythevariousoptimalserviceorderissues,deleteafewissues,carfuel,theoptimalmerger,venuearrangementsandsoon.Atlast,thecodetoachievetwoofthemonthegreedyalgorithmtodotheconcreteimplementationmethodindetail.

Keywords：

greedyalgorithm；Huffmancoding；MST；Optimalserviceorder;Automobilerefueling

第1章引言

1.1研究背景

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。

虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。

一般情况下，为了获得较好的性能，必须对算法进行细致的调整。

但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。

当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。

贪心算