（完整版）基于算法本科最新毕业论文设计

本科毕业论⽂（设计）

题⽬贪⼼算法设计及其实际应⽤研究系别信息管理系专业计算机科学与技术年级2007级学号姓名指导教师

成绩_______________________⼆〇⼀⼀年五⽉⼗五⽇⽬录

本科毕业论⽂（设计）任务书 ............................................⽂献综述..............................................................本科毕业论⽂（设计）开题报告 ...................................... - 1 正⽂..................................................................摘要..................................................................第1章引⾔...........................................................

1.1研究背景...........................................................1.2研究内容...........................................................1.3研究⽬标...........................................................1.4研究意义...........................................................

1.5 本⽂组织..........................................................第2章贪⼼算法的基本知识概述 .........................................2.1 贪⼼算法定义......................................................

2.2 贪⼼算法的基本思路及实现过程 ......................................2.3贪⼼算法的核⼼.....................................................2.4贪⼼算法的基本要素.................................................2.5 贪⼼算法的理论基础................................................

2.6贪⼼算法存在的问题.................................................第3章经典问题解决及其优缺点 .........................................3.1 哈夫曼编码........................................................3.2单源最短路径问题(Dijkstra算法) (1)

3.3最⼩⽣成树问题(Prim算法、Kruskal算法) (1)第4章多处最优服务次序问题 (1)4.2 贪⼼选择策略 (1)4.3 问题的贪⼼选择性质 (1)

4.4 问题的最优⼦结构性质 (1)4.5 算法结果分析 (1)5.1 问题的提出 (1)5.2 贪⼼算法策略 (1)5.3 问题的贪⼼选择性质 (1)5.4 问题的最优⼦结构性质 (1)5.5 编码 (1)

第6章汽车加油问题 (1)6.1 问题的提出 (1)6.2 编码分析 (1)6.3 贪⼼算法策略 (1)6.4 贪⼼算法正确性证明 (2)6.5 贪⼼算法时间复杂度分析 (2)第7章最优合并问题 (2)7.1 问题的提出 (2)7.2 原理分析 (2)

7.3 算法时间复杂度分析 (2)第8章会场安排问题 (2)8.1 问题的提出 (2)8.2 编码分析 (2)8.3 贪⼼算法 (2)8.4 最优解证明 (2)

8.5 算法时间复杂度分析 (2)第9章贪⼼算法的C++实现 (2)9.1 C++语⾔概述 (2)9.2 具体实现步骤 (2)9.3程序编码与程序调试 (2)第10章总结与展望 (3)10.1总结 (3)10.2展望 (3)参考⽂献 (3)附录 (3)致谢 (4)

本科毕业论⽂（设计）指导教师评阅表 ....................................本科毕业论⽂（设计）交叉评阅表 ........................................本科毕业论⽂（设计）答辩记录 ..........................................本科毕业论⽂（设计）任务书

论⽂（设计）题⽬贪⼼算法设计及其实际应⽤研究系别、专业信息管理系计算机科学与技术学⽣姓名学号指导教师姓名开题⽇期2011年11⽉28⽇

注：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]URL forumsthreads134122.aspx

[21] MelhiM,Ipson S S,Boothw.A novel triangulation procedure for thinning

[22] Florescu D,Grunhagen A,Kossmann D.XL:A Platform for Web Services[C].Proc.of the 1st Biennial Conference oninnovative Data Systems Research, 2003.本科毕业论⽂（设计）开题报告