算法设计和分析资料报告课程论文设计.doc

《算法设计和分析资料报告课程论文设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、理工学院课程论文论文题目贪心法的应用课程名称算法设计与分析姓名学号专业计算机科学与技术年级学院计算机日期（2014年4月10日）课程论文评价标准指标评价容评价等级（分值）得分ABCD选题选题是否新颖；是否有意义；是否与本门课程相关。20-1615-1110-65-0论证思路是否清晰；逻辑是否严密；结构是否严谨；研究方法是否得当；论证是否充分。20-1615-1110-65-0文献文献资料是否翔实；是否具有代表性。20-1615-1110-65-0规文字表达是否准确、流畅；是否符合学术道德规。20-1615-1110-65-0能力是否运用了本门课程的有关理论知识；是否体现了科学研究能力。2

2、0-1615-1110-65-0评阅教师签名：年月日总分：贪心法的应用摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的围可以确定的情况下，可以采用枚举或递归策略，一一比较它们最后找到最优解；但当解的围非常大时，枚举和递归的效率会非常低。这时就可以考虑用贪心策略。贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。关键词：贪心算法；删数问题

3、；最小生成树一、引言在平时解决问题的过程中，当一个问题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以及删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。二、贪心算法的含义和特点（一）贪心算法的含义贪心算法是通过一系列的选择来得到问题解的过程。贪心算法是一种能够

4、得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。（二）贪心算法的特点1、从全局来看，运用贪心策略解决的问题在程序运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖已作出的选择，但并不依赖未作出的选择。2、不能保证最后求出的解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，并不从整体上加以考虑。另外贪心算法只能用来求某些最大或最小解的问题，因为当遇到求解权值最小路径等问题采用贪心算法得到的结果并不是最佳。二、贪心算法在实例中的应用（一）删数问题给定n

5、位正整数a，去掉其中任意k≤ｎ个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的ｎ位正整数ａ和正整数ｋ，设计一个算法找出剩下数字组成的新数最小的删数方案。１、算法原理从最高位开始，依次向低位搜索，一旦遇到前一位（高数）的数大于当前位，则删去前一位，直到删除ｋ个数，如果到达末尾还没有删除ｋ个，则说明现在这个数已经是从小到大排列了，则从最低位开始删除要求的位数。２、过程分析　　　　　　　　ｎ１＝＂１　２　４　３　５　８　６　３＂k=3４比３大删除　　　　　＂１　２　　　３　５　８　６　３＂８比６大删除　　　　　＂１　２　４　３　５　　　６　３＂6比3大删除＂１　２　４　３　５　８

6、　　３＂只看这个实例，有可能归纳不出正确的算法，看下一个实例，再进一步解释。n2=＂2　３　１　１　８　３＂k=33比1大删除＂2　　１　１　８　３＂2比1大删除＂　　１　１　８　３＂8比3大删除＂　１　１　　３＂由实例n1，相邻数字只需从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保真结果的真确性。（二）最小生成树设G=(V,E)是一个无向连通带权图，即一个网络。E的每条边(v,w)的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树的各边的权的总和称为该生成树

7、的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。1、算法原理（1）Prim算法基本思想：在保证连通的前提下依次选出权重较小的n–1条边。G=(V,E)为无向连通带权图，令V={1,2,…,n}。设置一个集合S，初始化S={1}，T=Φ。贪心策略：如果V–S中的顶点j与S中的某个点i连接且(i,j)是E中的权重最小的边，于是就选择j(将j加入S)，并将(i,j)加入T中。重复执行贪心策略，直至V–S为空。（2）K