Chapter13-贪婪算法

贪婪算法是一种什么方法贪婪算法（Greedy Algorithm）是一种简单而经典的算法设计方法，通常用于解决优化问题。

贪婪算法每一步都采取当前情况下最优的选择，希望最终得到全局最优解。

本文将介绍贪婪算法的基本原理、应用场景以及一些经典的贪婪算法实例。

基本原理贪婪算法的基本原理是通过局部最优解来推导得到全局最优解。

在每一步中，贪婪算法选择当前看起来最好的选择，而不考虑之后的结果能否达到最优。

这种直观的选择策略有时可以给出全局最优解，但并非在所有问题中都成立。

贪婪算法的设计过程通常包含以下几个步骤：1. 定义问题的解空间和解集合，将问题转化成对这些解的选择和判定。

2. 根据问题的特点，设计选择策略，确定选择的标准。

3. 使用选择策略，逐步构建解，直到满足问题要求或无法继续选择。

需要注意的是，贪婪算法只能提供近似解，不能保证一定能得到最优解。

因此，在应用贪婪算法时需要仔细分析问题的性质，确定贪婪选择的合理性。

应用场景贪婪算法通常应用于具有贪婪选择性质的问题，即每一步都可以做出局部最优选择的问题。

这种性质常见于以下场景：最小生成树在图论中，最小生成树问题是指在一个连通无向图中找到一棵包含所有顶点且边权重之和最小的树。

典型的贪婪算法解决该问题的方法是普利姆算法（Prim's Algorithm）和克鲁斯卡尔算法（Kruskal's Algorithm）。

普利姆算法从一个起始顶点出发，每次选择与当前生成树连接的最短边对应的顶点，直到生成树包含所有顶点。

而克鲁斯卡尔算法则是从边集合中每次选择最小的边，同时保证不形成环，直到生成树包含所有顶点。

背包问题背包问题是在给定背包容量和一系列物品的重量和价值的情况下，如何选择物品放入背包中，使得背包中物品的总价值最大。

贪婪算法在背包问题的解决中有时也能给出较好的近似解。

一种典型的贪婪算法解决背包问题的方法是基于每个物品的单位价值（即单位重量所能获得的价值）来进行选择。

中国数学建模-编程交流-贪婪算法feifei7 重登录隐身用户控制面板搜索风格论坛状态论坛展区社区服务社区休闲网站首页退出>> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱(0)中国数学建模→学术区→编程交流→贪婪算法您是本帖的第672 个阅读者* 贴子主题：贪婪算法b等级：职业侠客文章：472积分：951门派：黑客帝国注册：2003-8-28第11 楼1.3.6 最小耗费生成树在例1 - 2及1 - 3中已考察过这个问题。

因为具有n个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。

至少可以采用三种不同的贪婪策略来选择这n-1条边。

这三种求解最小生成树的贪婪算法策略是：K r u s k a l算法，P r i m算法和S o l l i n算法。

1. Kruskal算法(1) 算法思想K r u s k a l算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。

注意到所选取的边若产生环路则不可能形成一棵生成树。

Kr u s k a l算法分e 步，其中e 是网络中边的数目。

按耗费递增的顺序来考虑这e条边，每次考虑一条边。

当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

考察图1-12a 中的网络。

初始时没有任何边被选择。

图13-12b 显示了各节点的当前状态。

边（1 ,6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。

下一步选择边（3，4）并将其加入树中（如图1 3 -1 2 d所示）。

然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。

下一步考虑边（2，3）并将其加入树中（如图1 3 - 1 2f所示）。

在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。

贪婪算法（贪⼼算法）贪⼼算法简介：@anthor:QYX 贪⼼算法是指：在每⼀步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过⼀系列的最优选择，能够产⽣⼀个问题的（全局的）最优解。

贪⼼算法每⼀步必须满⾜⼀下条件： 1、可⾏的：即它必须满⾜问题的约束。

2、局部最优：他是当前步骤中所有可⾏选择中最佳的局部选择。

3、不可取消：即选择⼀旦做出，在算法的后⾯步骤就不可改变了。

贪⼼算法的定义：贪⼼算法是指在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。

贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的⼀般步骤是：1.建⽴数学模型来描述问题；2.把求解的问题分成若⼲个⼦问题；3.对每⼀⼦问题求解，得到⼦问题的局部最优解；4.把⼦问题的局部最优解合成原来问题的⼀个解。

如果⼤家⽐较了解动态规划，就会发现它们之间的相似之处。

最优解问题⼤部分都可以拆分成⼀个个的⼦问题，把解空间的遍历视作对⼦问题树的遍历，则以某种形式对树整个的遍历⼀遍就可以求出最优解，⼤部分情况下这是不可⾏的。

贪⼼算法和动态规划本质上是对⼦问题树的⼀种修剪，两种算法要求问题都具有的⼀个性质就是⼦问题最优性(组成最优解的每⼀个⼦问题的解，对于这个⼦问题本⾝肯定也是最优的)。

动态规划⽅法代表了这⼀类问题的⼀般解法，我们⾃底向上构造⼦问题的解，对每⼀个⼦树的根，求出下⾯每⼀个叶⼦的值，并且以其中的最优值作为⾃⾝的值，其它的值舍弃。

⽽贪⼼算法是动态规划⽅法的⼀个特例，可以证明每⼀个⼦树的根的值不取决于下⾯叶⼦的值，⽽只取决于当前问题的状况。

换句话说，不需要知道⼀个节点所有⼦树的情况，就可以求出这个节点的值。

由于贪⼼算法的这个特性，它对解空间树的遍历不需要⾃底向上，⽽只需要⾃根开始，选择最优的路，⼀直⾛到底就可以了。

贪婪算法（贪婪算法（GreedyAlgorithm）Greedy Algorithm《数据结构与算法——C语⾔描述》图论涉及的三个贪婪算法1. Dijkstra 算法2. Prim 算法3. Kruskal 算法Greedy 经典问题：coin change在每⼀个阶段，可以认为所作决定是好的，⽽不考虑将来的后果。

如果不要求最对最佳答案，那么有时⽤简单的贪婪算法⽣成近似答案，⽽不是使⽤⼀般说来产⽣准确答案所需的复杂算法。

所有的调度问题，或者是NP-完全的，或者是贪婪算法可解的。

NP-完全性:计算复杂性理论中的⼀个重要概念，它表征某些问题的固有复杂度。

⼀旦确定⼀类问题具有NP完全性时，就可知道这类问题实际上是具有相当复杂程度的困难问题。

贪⼼算法是⼀类算法的统称10.1.1 ⼀个简单的调度问题将最后完成时间最⼩化这个问题是NP-完全的。

因此，将++最后完成时间最⼩化++显然⽐++平均完成时间最⼩++化困难得多。

10.1.2 Huffman 编码让字符代码的长度从字符到字符是变化不等，同时保证经常出现的字符其代码更短。

最优编码的树将具有的性质：所有结点或者是树叶，或者有两个⼉⼦。

字符代码的长度是否不相同并不要紧，只要没有字符代码是别的字符代码的前缀即可。

基本的问题：找到总价值（编码总长度）最⼩的满⼆叉树。

Huffman 算法因为每⼀次合并都不进⾏全局的考虑，只是选择两棵最⼩的树，所以该算法是贪⼼算法。

由此可见，贪⼼算法是⼀类算法的统称。

在⽂件压缩这样的应⽤中，实际上⼏乎所有的运⾏时间都花费在读⼊⽂件和写⽂件所需的磁盘 I/O 上。

伪代码1. ⽣成 Huffman 树while(minHeap.size() > 1){tree->left = minHeap.get()tree->right = minHeap.get()tree->frequence = tree->left->frequence + tree->right->frequenceminHeap.insert(tree);}huffmanTree = minHeap.get();2. 从 Huffman 树到 Huffman 编码（递归调⽤）字符集⼀般是常数的数量级，所以这⾥使⽤递归虽不是最优解，但⾜矣解此题。