《信息计算与科学贪心法算法及其应用.doc》由会员分享，可在线阅读，更多相关《信息计算与科学贪心法算法及其应用.doc（12页珍藏版）》请在三一办公上搜索。
1、上饶师范学院本科毕业论文论文题目： 贪心法算法及其应用 专业： 信息与计算科学 班级： 07数（5） 学号： 07010528 学生姓名： 徐先亮 指导教师姓名： 熊鹏荣 上饶师范学院数学与计算机科学学院2011年5月贪心法及其应用摘要 以贪心法算法理论为背景，依据贪心法算法的两个重要性质，贪心选择性质和最优子结构性质，来解决最小生成树问题、背包问题、带有期限的作业顺序问题及删数问题，找到具体问题最优解。关键字最优解近似解； 子问题； 可行解；局部最优选择；整体最优解；最优子结构； 贪心标准Greedy method and its applicationAbstract Algorithm
2、theory in the context of greedy method, based on greedy method are two important properties of the algorithm, the greedy choice of the nature and properties of the optimal sub-structure to solve the minimum spanning tree problem, knapsack problem, with an operating period of the order of the number
3、of questions and delete questions find the optimal solution of specific problems.显示对应的拉丁字符的拼音字典朗读显示对应的拉丁字符的拼音字典KeywordOptimal approximate solution；subproblem,；feasible solution； local optimal choice；the overall optimal solution；optimal substructure； greedy criteria；mathematical models朗读显示对应的拉丁字符的拼音字
4、典目录绪论1一、贪心算法的背景及理论依据1二、贪心算法解题思路1三、实现该算法的过程 1四、贪心算法的性质2五、运用贪心法解决具体问题3六、总结9致谢9参考文献9绪论：主要是根据贪心法算法的解题思路及具体实现算法的过程，解决涉及到该算法的几个具体实际问题，从中找到解决问题的整体最优解或是整体最优解的近似解，最后总结贪心算法的思想-只顾眼前利益，每次都是选最好的。一、贪心算法的背景及理论依据贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广
5、泛的许多问题他能产生整体最优解或者是整体最优解的近似解。它省去了为查找最优解而去穷尽所有可能而耗费的大量时间。二、贪心算法解题思路1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 三、实现该算法的过程 1.从问题的某一初始解出发； 2.while 能朝给定总目标前进一步 3.do 求出可行解的一个解元素； 4.由所有解元素组合成问题的一个可行解。 四、贪心算法的性质1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法
6、可行第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所做的往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。贪心算法所作的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，我们必
7、须证明每一步所做出的贪心选择最终导致问题的一个整体最优解。通常可以用我们在证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终得到一个整体最优解。其中，证明贪心选择后的问题就简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。2、最优子结构性质 当一个问题的最优解包括着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。五、运用贪心
8、法解决具体问题1、最小生成树问题(1)问题描述及分析讨论无向图的最小生成树问题。构造最小生成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设G = (V, E) 是一个连通网络，U是顶点集V的一个真子集。若（u, v）是G中所有的一个断电在U（即uU）里、另一个端点不再U（即vV-U）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括边（u, v）。这个性质称为MST性质。MST性质可用反证法证明：假设G的任何一颗最小生成树总都不包含边（u，v）。设T是G的一颗最小生成树，但不包含边（u, v）。由于T是树，且是连通的，因此有有一条u到v的路径；且该路径上必
9、有一条连接两个顶点集和的边（u,v）,其中uU,vV-U,否则u和v不连通。当把边（u, v）加入树T时，得到一个包含有边（u, v）的回路，见图1。删去边（u, v）,上述回路即被消除，由此得到另一颗生成树T,T和T的区别仅在于用边（u, v）取代了T中的边（u,v）。因为（u, v）的权=(u, v)的权，故T的权=T的权，因此T也是G的最小生成树，它包含边（u, v）,与假设矛盾！那么如何利用MST性质来构造最小生成树呢？下面我们介绍prim这样的一中贪心算法UUVVuv-u 图（1） 包含边（u，v）的回路(2)算法描述假设G = (V, E)是连通网络，为简单起见，我们用序号1至 n
10、来表示顶点集合，即V = 1，2， ，n。设所求的最小生成树为T = （U , TE）,其中U是T的顶点集，TE 是T的边集。并且将G中边上的权看做是长度。Prim算法的基本思想是：首先从V中人去一个顶点u。，将生成树T置为仅有一个结点u。的树，即置U = u。；然后只要U是V的真子集，就在所有那些其一个端点u已在T，另一个端点v还未在T的边中，找一条最短的边（u，v），并把该条边（u, v）和其不在T中的顶点v,分别并入T的边集TE和顶点集U。如此进行下去，每次往生成树里并入一个顶点和一条边，知道哦啊把所有顶点包括进生成树T为止。此时，必有U = V ,TE 中有n-1条边。MST性质保证上
11、述过程求的的T = (U ,TE)是G的一颗最小生成树。于是不难推出完整的算法。 算法程序如下： PRIM( ) int j，k, m, v, min, max =10000； float d； edge e； for (j =1； jn；j+) Tj-1. Formvex =1 ； Tj-1.endvex = j+1； Tj-1.length = dist0 j ； for(k =0； k n- 1； k+) min = max； for ( j =k ； jn-1； k+) if (T j .lengthmin) min = T j.length； m = j ； e = T m ； T
12、m = T k ； T k = e； V = T k.endvex； for (j=k+1； jn-1； j+) d= dist v-1 Tj .endvex-1 ； if(dT j. length)； Tj.length = d；T j.fromvex = v； 2、背包问题(1)问题描述及分析我们试着用贪心算法来解决背包问题。己知一个容量为weight的背包。现在要从n种物品中选取若干装入背包中，每种物品的重量为w(i)、价值为p(i)。定义一种可行的背包装载为：背包中物品的总重量不能超过背包的容量，并且一个物品要么全部选取，要么不选取。采取怎样的装包方案才会使装入背包的物品总效益值最大?
13、 (2)算法描述如果所有重量的总和小于等于m，那么x(i)=1(1=i=pi+1/wi+1 .m is the knapsack/size and x1:n is the solution vector. for (int i=1；i=n；i+) xi=0.0； initialize x； float U = m； for(i=1；iU) break； xi =1.0； u=wi； 3、带有期限的作业顺序问题(1)问题描述及分析给定一个有n项作业的集合。处理时间ti和di 与每项作业i关联。一个可行解是作业的一个排列使得作业按照顺序进行处理，且每项作业按时完成。定义一个贪心调度使得作业按照期限
14、的非递减顺序进行处理。证明存在一个可行性调度，那么所有的贪心调度都是可行解。(2)算法描述：Void FJS (int d ，int n， int b，int j )/find an optiomal solution J 1: K. It is assumed that /p1 = p 2 =pn and that b = minn, max(di). /initially there are b+1 single node trees.sets set(b)；for (int i=0; i=b;i+ )fi = i；int k = 0；/initialize.for(i=1; in; i+
15、 )/ude greedy rule .int q = set.Collapsingfind(min(n, di);if (fq) k+； jk = I； /select job i.int m = set.collapsingfind(fq-1)；set.weightedunion(m ,q)；f q = fm；/q maybe new root. 4、删数问题:（1）问题描述及分析：键盘输入一个高精度的正整数N（此整数中没有0），去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 输出应包括所去掉的数字的位置和组
16、成的新的正整数。（N不超过240位） 输入数据均不需判错。 （2）算法描述:/代码(C+) #include #include intmain() chara241; ints; inti,j,k; intflag241; intflag2; cina; cins; for(i=0;istrlen(a);i+) flagi=1; for(i=0;is;i+) flag2=1; for(j=0;jak) flagj=0; flag2=0; break; if(flag2=1) j=strlen(a)-1; /coutajflagjendl; while(flagj=0) j-; flagj=0;
17、 for(i=0;istrlen(a);i+) if(flagi!=0) coutai; coutendl; 六、总结 贪心法(greedymethod)就是只顾眼前利益，每次都选最好的。 、解向量 把可行解写成一个N元组的形式，就是解向量。 2、贪心标准 就是眼前“最好”的标准。例如背包问题，标准可以是价值，重量或“性价比” 3、贪心算法 对于解向量的每一维，用贪心标准在所有可能值中选择一个加入到解向量中。 4、什么样的问题可以考虑用贪心？ 贪心选择性质：选择具有无后效性，即不依赖与以后将要作出的选择。 最优子结构：全局最优包含局部最优。致谢：此片论文得以完成,首先要感谢熊鹏荣老师的细心指导。熊老师开阔的视野，为我提供了极大的发挥空间，在这段时间里让我明白了做任何事情要严谨细致、一丝不苟，对人要宽容、宽厚，熊老师宽厚待人的学者风范更是令我无比感动。感谢各位老师在这几年一直在生活中、组织上给予我的教导和无私的帮助，让我在上饶师范学院这个大舞台上有锻炼的能力、自我完善的平台。在此文即将完成之际，我衷心的感谢在此过程中帮助过我的每个人，在这里请接收我最诚挚的谢意！参考文献1.王晓东.计算机算法设计与分析2.潘金贵等.现代计算机常用数据结构和算法3.冯博琴等译.计算机算法4.霍红卫.算法设计与分析5.在网络上查找相关资料
