下载文档原格式
关于贪⼼算法的研究关于贪⼼算法的研究[摘要] 本⽂对贪⼼算法进⾏较详细的研究。
第⼀部分明确其基本概念，第⼆部分介绍常见的贪⼼模型，第三部分给出常⽤的贪⼼证明⽅式，第四部分介绍贪⼼的经典算法，第五部分与其他算法进⾏⽐较，最后总结贪⼼算法的优劣性、竞赛应⽤及前景。
[关键词] 贪⼼算法、Prim、kruskal、Dijkstra、Huffman、拟阵、证明贪⼼算法是在信息学竞赛中⼀个常⽤的重要算法。
在许多的经典算法中都处处藏着贪⼼的思想。
MST中的Prim和Kruskal都是很优的贪⼼算法。
还有Dijkstra的单源最短路径和数据压缩(Huffman)编码以及Chvatal的贪⼼集合覆盖启发式。
其实很多的智能算法（启发式算法），就是贪⼼算法和随机化算法结合。
这样的算法结果虽然也是局部最优解，但是⽐单纯的贪⼼算法更靠近最优解，例如遗传算法，模拟退⽕算法。
贪⼼算法是与⼈类通常思维⽅式极其相近的算法，所以使⽤贪⼼算法时最⼤的困难通常不是构造贪⼼，⽽是证明贪⼼算法的正确性。
本⽂将对贪⼼算法的模型与包含贪⼼的经典算法进⾏介绍，同时给出贪⼼算法的证明⽅式。
最后总结贪⼼算法的优劣性、竞赛应⽤及前景。
[⽬录]1 贪⼼算法的基本概念 (2)1.1 定义 (2)1.2 基本特性 (2)1.3 基本思路 (2)2 贪⼼模型 (2)2.1 硬币问题 (2)2.2 装载问题 (3)2.3 部分背包问题 (4)2.4 乘船问题 (6)2.5 区间问题 (8)2.6 选点问题 (9)2.7 顺序问题 (11)3 贪⼼证明 (13)3.1 公式法 (13)3.2 交换参数法 (13)3.3 归纳法 (13)3.4 反证法 (13)4 经典贪⼼算法 (13)4.1 Prim (14)4.2 Kruskal (14)4.3 Dijkstra (14)4.4 Huffman (14)5 拟阵 (14)6 贪⼼算法与其他算法的⽐较 (15)6.1 贪⼼与动态规划的⽐较 (15)6.2 基本特性贪⼼与分治的⽐较 (16)7 总结 (16)8 参考⽂献 (16)1 贪⼼算法的基本概念1.1 定义贪⼼算法(Greedy Algorithm)，⼜称贪婪算法，它在对问题求解时，能根据每次所求得的局部最优解，推导出全局最优解或最优⽬标。
实验3贪心算法（定稿）第一篇：实验3 贪心算法（定稿）《算法设计与分析》实验报告实验3贪心算法姓名学号班级实验日期实验地点一、实验目的1、掌握贪心算法的设计思想。
2、理解最小生成树的相关概念。
二、实验环境1、硬件环境 CPU：酷睿i5 内存：4GB 硬盘：1T2、软件环境操作系统：Windows10 编程环境：jdk 编程语言：Java三、实验内容：在Prim算法与Kruskal算法中任选一种求解最小生成树问题。
1、你选择的是：Prim算法2、数据结构（1）图的数据结构——图结构是研究数据元素之间的多对多的关系。
在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。
图形结构——多个对多个，如（2）树的数据结构——树结构是研究数据元素之间的一对多的关系。
在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。
树形结构——一个对多个，如3、算法伪代码 Prim(G,E,W)输入：连通图G 输出：G的最小生成树T 1.S←{1};T=∅ 2.While V-S ≠∅ do3.从V-S中选择j使得j到S中顶点的边e的权最小；T←T∪{e}4.S←S∪{j}3、算法分析时间复杂度：O(n)空间复杂度：O(n^2)4、关键代码（含注释）package Prim;import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE;staticint Prim(intgraph[][], intn){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ intlowcost[]=newint[n+1];/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ intmst[]=newint[n+1];intmin, minid, sum = 0;/* 默认选择1号节点加入生成树，从2号节点开始初始化*/ for(inti = 2;i<= n;i++){/* 标记1号节点加入生成树 */ mst[1] = 0;/* n个节点至少需要n-1条边构成最小生成树 */ for(inti = 2;i<= n;i++){/* 找满足条件的最小权值边的节点minid */ for(intj = 2;j<= n;j++){/* 输出生成树边的信息:起点，终点，权值 */System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} }5、实验结果（1）输入（2）输出最小生成树的权值为：生成过程：(a)(b)(d)(e)(c)四、实验总结（心得体会、需要注意的问题等）这次实验，使我受益匪浅。
《基于贪心算法的动态规划策略》篇一一、引言在计算机科学和优化理论中，动态规划和贪心算法是两种常用的解决优化问题的方法。
动态规划更侧重于通过保存子问题的解来避免重复计算，而贪心算法则倾向于在当前状态下做出最优选择。
本文将探讨如何结合这两种算法的思想，设计一种基于贪心算法的动态规划策略，以解决一些具有挑战性的实际问题。
二、背景及问题阐述在实际生活中，我们常常需要面对一系列具有复杂约束的优化问题。
这些问题通常需要在有限的时间内，通过计算寻找一种最满意的解决方案。
例如，在资源分配、路径规划、网络流等问题中，我们往往需要在满足一定约束条件下，追求某种指标（如成本、时间、效率等）的最优化。
针对这些问题，本文提出了一种基于贪心算法的动态规划策略。
三、贪心算法与动态规划的结合1. 贪心策略贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
它的特点是在每一步选择中都只考虑当前状态，而不从整体最优上加以考虑。
2. 动态规划动态规划是一种通过保存子问题的解来避免重复计算，从而解决最优化问题的方法。
它通常将问题分解为若干个子问题，并保存子问题的解以供后续使用。
结合这两种算法的思想，我们可以设计一种基于贪心策略的动态规划方法。
具体而言，我们可以在动态规划的过程中，利用贪心策略来指导子问题的选择和解决。
这样可以在保证解的质量的同时，提高算法的效率。
四、策略设计及实施1. 问题分解与建模首先，我们需要将问题分解为若干个子问题，并建立相应的数学模型。
这通常涉及到对问题的深入理解和分析，以确定哪些子问题的解对最终结果具有关键影响。
2. 贪心策略的引入在建立数学模型后，我们可以引入贪心策略来指导子问题的选择和解决。
具体而言，我们可以在每一步选择中，根据当前状态和目标函数的特点，选择最有利于达到全局最优的子问题进行处理。
3. 动态规划的实现在引入贪心策略后，我们可以利用动态规划的思想来求解问题。
对k-means聚类算法的改进研究摘要:本文针对k-means算法对初值的依赖性，基于最小生成树原理选取聚类中心进行聚类。
根据寻找最优初值的思想提出了一种改进的k-means算法，将最小生成树的构造算法之一的卡斯克鲁尔（Kruskal Algorithm）算法以及贪心算法(Greedy Algorithm)的思想引入到k-means算法中。
关键字：k-means算法最小生成树贪心策略一、算法的改进思路的形成无论是原始的k-means算法还是加入了聚类准则函数的k-means算法,都有一个共同的特点,即采用两阶段反复循环过程，算法结束的条件是不再有数据元素被重新分配：1)指定聚类，即指定数据x i到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近；2)修改聚类中心。
k-means算法中急需解决的问题主要有三个：(l)在k-means算法中,k是事先给定的，这个k值的选定是很难估计的。
很多时候，我们事先并不知道给定的数据集应分成多少类最合适，这也是k-means 算法的一个不足。
有的算法是通过类的自动合并和分裂，得到较为合理的类型数目k，例如ISODALA算法。
关于k-means算法中聚类数目k值的确定，有些根据方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分墒来验证最佳分类数的正确性。
在文献[26]中，使用了一种结合全协方差矩阵的RPCL算法，并逐步删除那些只包含少量训练数据的类。
而其中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。
它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法，使之远离输入值。
(2)在k-means算法中常采用误差平方和准则函数作为聚类准则函数，考察误差平方和准则函数发现：如果各类之间区别明显且数据分布稠密，则误差平方和准则函数比较有效；但是如果各类的形状和大小差别很大，为使误差平方和的值达到最小,有可能出现将大的聚类分割的现象。
![贪婪算法思想及其应用[5篇模版]](https://img.taocdn.com/s1/m/e84e86f581eb6294dd88d0d233d4b14e85243ed2.png)
贪婪算法思想及其应用[5篇模版]第一篇：贪婪算法思想及其应用贪婪算法思想及其应用摘要：贪婪算法也称作贪心算法，它没有固定的算法框架，算法设计的关键是贪婪策略的选择，并且所选的贪婪策略要具有无后向性。
关键词：贪婪策略，无后向性，最优正文：一．贪婪算法的定义：贪婪算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。
二．贪婪算法思想：贪婪算法采用逐步构造最优解的方法，即在每个阶段，都选择一个看上去最优的策略（在一定的标准下）。
策略一旦选择就不可再更改，贪婪决策的依据称为贪婪准则，也就是从问题的某一个初始解出发并逐步逼近给定的目标，以尽可能快的要求得到更好的解。
而且它在设计时没有固定的框架，关键在于贪婪策略的选择。
但要注意的是选择的贪婪策略要具有无后向性，即某阶段状态一旦确定下来后，不受这个状态以后的决策的影响，也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关。
三．贪婪算法的优缺点：贪婪算法的优点在于在求解问题的每一步它都是选择最优解，这样算法就容易实现也易于理解，同时也提高了效率并节省了时间。
然而贪婪算法的缺点也是不容忽视的，由于它采取逐步获得最优解的方法而不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。
因此贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它都能得出整体最优解或者是整体最优解的近似解。
四.实例参考：下面就列举用贪婪算法成功得出问题最优解的例子：例：一个小孩拿着一美元去商店买糖果，花了33美分，售货员需要找回67美分给小孩，而美分的面值有25,10,5,1这几种。
问题是售货员找个小孩的钱币的个数应是最少的，但同时要满足67美分这个条件。
分析：选择硬币时所采用的贪婪准则如下：每一次都选择面值最大的货币来凑足要找的零钱总数，但前提是不能超出要找的67美分。
解：我们用贪婪算法来处理这个问题，首先我们肯定会选择面值为25的货币，这样的货币我们需要两枚，然后我们依据贪婪准则选择面值为10的货币，这样的货币我们需要一枚，接着继续选择面值为5的货币一枚和面值为1的货币两枚。
《基于贪心算法的动态规划策略》篇一一、引言在计算机科学和优化理论中，动态规划和贪心算法是两种重要的策略。
动态规划通过将问题分解为子问题并存储子问题的解来寻找全局最优解，而贪心算法则采取当前看起来最优的行动，并不考虑未来可能产生的影响。
在实际应用中，将这两种策略结合，即基于贪心算法的动态规划策略，能够有效地处理一些复杂问题，如路径规划、资源分配、图形理论等。
本文旨在深入探讨这种策略的理论基础和应用场景。
二、理论基础2.1 动态规划动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。
它的核心思想是将问题分解为若干个子问题，并将子问题的解存储起来，避免重复计算。
2.2 贪心算法贪心算法则是通过采取当前看来最优的选择来达到全局最优解的一种策略。
这种策略在每一步都采取最优解，尽管可能忽略某些更长的长远利益。
然而，对于某些问题，这种策略却能够产生最优解。
基于这两者，我们可以构建基于贪心算法的动态规划策略。
这种策略在处理问题时，首先使用动态规划的思想将问题分解为子问题并存储子问题的解，然后利用贪心算法的思想在每一步选择当前最优的子问题解决方案。
三、基于贪心算法的动态规划策略的应用3.1 路径规划问题在路径规划问题中，我们常常需要找到一条从起点到终点的最短路径或最优路径。
这时，我们可以首先使用动态规划来找到可能的路径组合，然后使用贪心算法在每一步都选择当前看来最优的路径。
3.2 资源分配问题在资源分配问题中，我们需要在有限的资源下实现最优的分配。
例如，如何分配公司的预算以达到最大的效益。
我们可以通过动态规划来找到可能的资源分配方案，然后利用贪心算法的思想在每一步都选择能够带来最大收益的资源分配方案。
四、实践中的挑战与改进方向尽管基于贪心算法的动态规划策略在很多问题上表现出了优秀的性能，但仍然存在一些挑战和改进空间。
首先，如何准确地确定何时使用动态规划和何时使用贪心算法是一个需要深入研究的问题。
贪心算法及其在算法设计中的应用一、引言贪心算法作为一种常见且经典的算法思想，在算法设计中有着广泛的应用。
它的基本思想是以局部最优解为基础，逐步将这些局部最优解组合起来，获得全局最优解。
许多实际问题都能够运用贪心算法来解决，例如最小生成树、货仓选址、背包问题等。
本文旨在介绍贪心算法的相关概念、基本思路以及其在算法设计中的应用。
首先，我们将简要阐述贪心算法的定义和特点。
接着，我们将介绍几个基于贪心算法的经典问题，并提供具体的算法实现方法。
最后，我们将总结贪心算法的优缺点以及适用范围，为读者提供一个透彻了解贪心算法的工具。
二、贪心算法的定义和特点贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望得到全局最优解的问题解决思想。
简单来说，贪心算法是建立在剪枝的思想上，在每一步中选择一个当前状态下最优的可行解，并淘汰掉其他的选择。
这种优化方法通常需要有某些限制条件，并且随着每步的选择，已经作出的决策不能被撤回。
与其他一些算法相比，贪心算法有其独特的优势。
首先，贪心算法的时间复杂度通常比较低，运行速度较快。
其次，贪心算法的思路简单明了，易于实现和理解。
但需要注意的是，贪心算法在某些情况下可能无法得到全局最优解，而是只能得到局部最优解。
三、贪心算法的应用1. 最小生成树最小生成树问题是指，在一个无向图中，连接所有节点且总权重最小的树。
可以使用贪心算法来解决这个问题。
具体的操作是，从一个点出发，一步步地寻找到紧邻它的最短边，将这个节点标记为已访问。
接下来，继续访问与它相邻的未访问节点中，边权重最小的点，直到所有的节点都被访问过。
时间复杂度为O(n^2)，其中n为节点的数量。
2. 货仓选址货仓选址问题是指，在一个二维平面上，从几个点中选出一个点作为货仓位置，使得所有点到该位置的距离之和最小。
可以使用贪心算法来解决这个问题。
具体的操作是，寻找平均数，并将其作为货仓位置。
时间复杂度为O(n)，其中n为点的数量。
贪心算法总结什么是贪心算法？贪心算法（Greedy Algorithm）是一种用于求解优化问题的常见算法，其核心思想是在每一步都选择当前最优解，希望最终能够得到全局最优解。
贪心算法在每一步仅考虑局部最优，而不关心全局最优，因此它的计算速度较快。
然而，由于贪心算法没有考虑全局，在某些情况下可能无法得到最优解。
贪心算法并不适用于所有的问题，只适用于一些特殊的问题，例如背包问题、最小生成树问题等。
在实际应用中，需要根据具体问题的特点来判断是否可以使用贪心算法来解决。
贪心算法的基本思路贪心算法的基本思路可以概括为以下几步：1.确定最优解的性质：首先要确定在每一步选择中，能够得到局部最优解。
2.构造贪心选择：根据最优解的性质，每一步都做出一个贪心选择，选择能够获得当前最大或最小收益的方案。
3.确定限制条件：确定问题的限制条件，包括物品的容量、时间限制等。
4.根据限制条件，进行剪枝策略：如果某种选择在限制条件下无法满足要求，则需要进行剪枝，排除该选择。
5.循环执行贪心选择，直到问题得到解决。
贪心算法的优缺点贪心算法具有以下优点：•计算速度快：贪心算法在每一步只考虑局部最优解，不需要对全局进行搜索，因此计算速度较快。
•算法思路简单：贪心算法的思路相对简单，易于理解和实现。
•适用范围广：贪心算法适用于一些特殊问题，如最短路径、最小生成树等。
然而，贪心算法也存在一些缺点：•可能无法得到最优解：由于贪心算法仅考虑局部最优解，而不关心全局最优解，因此可能无法得到最优解。
•需要满足贪心选择性质：贪心算法要求问题具有贪心选择性质，即每一步都能够得到局部最优解。
如果问题不具备这个性质，贪心算法可能不适用。
贪心算法的应用场景贪心算法适用于一些特殊的问题，以下是一些常见的应用场景：1. 最短路径问题最短路径问题是指在一个加权有向图中，找出从一个顶点到另一个顶点的最短路径。
贪心算法可以用来解决一些简单的最短路径问题，如Dijkstra算法。
贪心算法实验小结
最近，我和我的同学们在实验室里进行了一次关于贪心算法的实验，探究贪心算法在旅行商问题中的应用。
实验的准备工作非常简单，我们只需要准备好实验所需的数据，并将其输入到计算机中即可。
之后，我们使用贪心算法来解决这个旅行商问题，运用贪心思想，在遍历所有城市时，选择当前停留时间最短的城市作为下一站，以期最终获得最短的旅行路线。
实验的过程中，我们发现，贪心算法可以有效地解决旅行商问题，即使在城市数量较多的情况下，它仍然能够在较短的时间内得到最优解。
除了旅行商问题之外，贪心算法还可以应用于其他许多其他问题，比如背包问题，最大化问题等。
在这次实验中，我们研究到了贪心算法的原理和应用，对于贪心算法在求解复杂问题中的重要性有了更深的认识。
此外，我们也体会到了贪心算法的局限性，它只能获得局部最优解，而不能保证全局最优解。
总之，本次实验对我们的研究有很大的帮助，不仅加深了对贪心算法的认识，而且还能够更好地理解其在实际问题中的应用，让我们更加清楚如何有效地利用贪心算法来解决复杂问题。
贪⼼算法总结简介贪⼼算法（英⽂：greedy algorithm），是⽤计算机来模拟⼀个“贪⼼”的⼈做出决策的过程。
这个⼈⼗分贪婪，每⼀步⾏动总是按某种指标选取最优的操作。
⽽且他⽬光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想⽽知，并不是所有的时候贪⼼法都能获得最优解，所以⼀般使⽤贪⼼法的时候，都要确保⾃⼰能证明其正确性。
本⽂主要介绍，在解决诸多贪⼼算法的问题之后的⼼得。
常⽤场景最常见的贪⼼算法分为两种。
「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从⼩到⼤）选择。
」。
「我们每次都取 XXX 中最⼤/⼩的东西，并更新 XXX。
」（有时「XXX 中最⼤/⼩的东西」可以优化，⽐如⽤优先队列维护）第⼀种是离线的，先处理后选择，第⼆种是在线的，边处理边选择。
常见的出题背景为:确定某种最优组合（硬币问题）区间问题（合理安排区间）字典序问题最值问题A最优组合硬币问题是贪⼼算法⾮常经典的题⽬，关于最优组合问题，我认为主要分为两种类型:简单 -- 直接排序之后按照某种策略选取即可复杂 -- 除了按照贪⼼策略外，还需要进⾏某些处理或者模拟硬币问题硬币问题有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。
现在要⽤这些硬币来⽀付A元，最少需要多少枚硬币？假设本题⾄少存在⼀种⽀付⽅法。
0≤C1、C5、C10、C50、C100、C500≤1090≤A≤109本题是上述说的简单类型的题⽬，简⽽⾔之要使得硬币最少，则优先使⽤⼤⾯额的硬币。
因此本题的解法便⾮常清晰了，只需要从后往前遍历⼀遍即可（默认为硬币已经按⾯额⼤⼩进⾏排序）const int V[6] = {1, 5, 10, 50, 100, 500};int A, C[6]; // inputvoid solve(){int ans(0);for (int i = 5; i >= 0; -- i){int t = min(A / V[i], C[i]);A -= t * V[i];ans += t;}cout << ans << '\n';}零花钱问题POJ3040 AllowanceDescriptionAs a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like topay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.Input* Line 1: Two space-separated integers: N and C* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.Output* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowanceSample Input3 610 11 1005 120Sample Output111这题的题⽬⼤意是:农场主每天都要给贝西⾄少为C的津贴。
本科毕业论文（设计）题目贪心算法设计及其实际应用研究系别信息管理系专业计算机科学与技术年级2006级学号***************姓名蒋远丽指导教师汪维清成绩_______________________二〇一〇年五月十五日目录西南大学本科毕业论文（设计）任务书 (I)文献综述 (i)西南大学本科毕业论文（设计）开题报告 ............................... - 1 - 正文 . (4)摘要 (4)第1章引言 (5)1.1研究背景 (5)1.2研究内容 (6)1.3研究目标 (6)1.4研究意义 (6)1.5 本文组织 (6)第2章贪心算法的基本知识概述 (8)2.1 贪心算法定义 (8)2.2 贪心算法的基本思路及实现过程 (8)2.3贪心算法的核心 (8)2.4贪心算法的基本要素 (9)2.5 贪心算法的理论基础 (10)2.6贪心算法存在的问题 (11)第3章经典问题解决及其优缺点 (12)3.1 哈夫曼编码 (12)3.2单源最短路径问题(Dijkstra算法) (14)3.3最小生成树问题(Prim算法、Kruskal算法) (16)第4章多处最优服务次序问题 (19)4.1 问题的提出 (19)4.2 贪心选择策略 (19)4.3 问题的贪心选择性质 (19)4.4 问题的最优子结构性质 (19)4.5 算法结果分析 (20)第5章删数问题 (21)5.1 问题的提出 (21)5.2 贪心算法策略 (21)5.3 问题的贪心选择性质 (21)5.4 问题的最优子结构性质 (21)5.5 编码 (22)第6章汽车加油问题 (23)6.1 问题的提出 (23)6.2 编码分析 (23)6.3 贪心算法策略 (23)6.4 贪心算法正确性证明 (24)6.5 贪心算法时间复杂度分析 (24)第7章最优合并问题 (25)7.1 问题的提出 (25)7.2 原理分析 (25)7.3 算法时间复杂度分析 (25)第8章会场安排问题 (26)8.1 问题的提出 (26)8.2 编码分析 (26)8.3 贪心算法 (26)8.4 最优解证明 (27)8.5 算法时间复杂度分析 (27)第9章贪心算法的C++实现 (28)9.1 C++语言概述 (28)9.2 具体实现步骤 (29)9.3程序编码与程序调试 (33)第10章总结与展望 (35)10.1总结 (35)10.2展望 (35)参考文献 (36)附录 (37)致谢 (45)本科毕业论文（设计）指导教师评阅表 ..................................... a 本科毕业论文（设计）交叉评阅表 ......................................... b 本科毕业论文（设计）答辩记录 ........................................... c西南大学本科毕业论文（设计）任务书论文（设计）题目贪心算法设计及其实际应用研究系别、专业信息管理系计算机科学与技术学生姓名蒋远丽学号 222006602054062 指导教师姓名汪维清开题日期2009年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的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈v-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条边。
