贪婪算法
贪婪算法(Greedy Algorithm)也叫算贪心法,贪婪法.它是一个遵循启发式解决问题的算法范式.它的核心思想就是通过在每一步的选择中都选用当前步骤下最优的选择,期望结果是最优的算法.如 旅行推销员问题 .
贪婪算法尤其适用于有最优子结构的问题中,最优子结构的意思是局部的最优解可以导出全局的最优解.贪婪算法与 动态规划 的不同在于贪婪算法对每一个子问题都作出选择,不能回退;动态规划则会保存以前的运算结果,根据以前的结果对当前进行选择,可以回退.
贪婪算法可以解决一些 最优化 (如最大值最小值等)问题,比如求图中的 最小生成树 、求 哈夫曼编码 …其他大多数的情况都不适用贪婪算法,一旦一个问题可以使用贪婪算法来解决,那么贪婪算法一般是解决这个问题的最好办法.由于贪婪算法的高效性以及其答案比较接近最有结果,也可以作为辅助算法或直接解决一些结果要求不那么精确的问题.
原文首发于 https://leonchen1024.com/2018/12/03/Greedy-Algorithm/
贪婪算法适用于一些数学问题等,大部分适用的问题都有两个特点:
我们可以在每个子问题找出最好的选择然后进行总结.贪婪算法可能会根据迄今为止已经做的选择进行计算,但是却不会考虑之后子问题的选择.它将一个大的问题分解成小的问题并一个一个进行迭代计算.换句话说,贪婪算法不会重新考虑它已经得出的选择.这是它和 dynamic programming 的主要区别,动态规划会详尽的计算并确保得到最优解,在一步之后,动态规划会根据之前所有得到的选择进行下一个选择,并可能会重新对之前步骤的算法路径进行修改.
这个问题要包含 optimal substructure (即这个问题的最优解包含了它的子问题的最优解)
如以下几种类型的问题
原文首发于 https://leonchen1024.com/2018/12/03/Greedy-Algorithm/
matroid (拟阵) 是一个数学上的结构,它将 linear independence (线性无关)的概念从 vector spaces (向量空间)推广到了任意的集合.如果一个最优解问题有一个拟阵结构,那么贪婪算法是最佳的解决办法.
一个函数 定义了当集合 的所有子集合 都满足 的情况即为子模块.
假设有人想要找到一个集合 使得函数 最大.贪婪算法将会通过逐个添加在每一步中使得 增加最多的元素,产生一个结果至少是 ??todo. 所以,贪婪算法至少得出最优解的 倍的解.
这些问题也可以使用贪婪算法,但不是最好的解法,他们在最差的情况下,可能会得到很差的结果.
原文首发于 https://leonchen1024.com/2018/12/03/Greedy-Algorithm/
在很多其他问题上,贪婪算法无法产生最优解,甚至可能产生一个最坏的解决方案.比如之前提到的 traveling salesman problem :对每一个城市都要计算一个最近的邻居,这种方式可能会产生一个最坏的路程.
比如下图,贪婪算法只考虑到下一步的最优解,但是却没有考虑到之后的解决方案,导致实际上得出的不是一个最优解.
贪婪法基本上（但并不是一定）不适用于求全局最优解，因为他通常没有遍历所有的数据。他们太早给出了肯定的选择使得他们无法从所有的解法中找到最优解。比如，使用 greedy coloring 算法来解决 graph coloring problem 以及所有的 NP-complete 问题。尽管如此，贪婪法还是很有用的，因为他们容易被考虑到并且通常情况下会给出一个比较好的解法。
如果一个贪婪算法可以被证明是某个问题的全局最优解法，他通常情况下就会成为优先选择的方法，因为它比其他的最优解方法如 dynamic programming 要快。这种例子有使用 Kruskal's algorithm 和 Prim's algorithm 找到 minimum spanning trees ,还有找到最优 Huffman trees .
贪心法也使用于 网络 路由 中。使用贪心路由，消息会被发送到距离目标节点“最近”的相邻节点。一个节点位置的定义（还有“最近”的含义）也许会取决于它的物理位置，如同在 ad hoc networks 中使用 geographic routing . 位置也可能会使一个人造的结构如同在 small world routing 和 distributed hash table 中.
https://en.wikipedia.org/wiki/Greedy_algorithm
我的博客 leonchen1024.com
我的 GitHub https://github.com/LeonChen1024
微信公众号
[图片上传失败...(image-ee4c03-1560057222368)]
贪婪算法的特点是什么？
算法应该具有以下五个重要的特征：1，有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止；2，确切性：算法的每一步骤必须有确切的定义；3，输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4，输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5，可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。扩展资料：对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
贪婪算法指的是什么？
贪心算法是指在对问题进行求解时，在每－步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的。贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似（接近）最优解的结果。例题、区间问题问题描述：有n项工作，每项工作分别在si开始，ti结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与。即参与工作的时间段不能有重叠（即使开始的时间和结束的时间重叠都不行）。限制条件：1<=n<=1000001<=si<=ti,=109样例：输入51 2 4 6 83 5 7 9 10输出3(选择工作1, 3, 5)。
