发布时间 : 星期四 文章基于算法本科最新毕业论文更新完毕开始阅读6a4eaa660166f5335a8102d276a20029bd64638e
优点：该算法的特点是当前形成的集合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 on innovative Data Systems Research, 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）会场安排问题