贪婪算法

贪婪算法指的是什么？

贪心算法是指在对问题进行求解时，在每－步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的。贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似（接近）最优解的结果。例题、区间问题问题描述：有n项工作，每项工作分别在si开始，ti结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与。即参与工作的时间段不能有重叠（即使开始的时间和结束的时间重叠都不行）。限制条件：1<=n<=1000001<=si<=ti,=109样例：输入51 2 4 6 83 5 7 9 10输出3(选择工作1, 3, 5)。

你不知道的：贪婪算法

  贪婪算法是关注局部最优而非全局最优的算法策略，在对问题求解时， 每次选择，都是当前最佳 。当找出一个大致能解决问题的优秀解，而不需要要找出最完美的解的情况下，贪婪算法还是不错的。优秀和完美之间，需要考虑实现代价。例如：精确算法的时间复杂度是冥函数或阶乘函数，其实现代价将远远高于结果还不错的贪婪算法   NP完全问题：不能在确定的多项式时间内解决的问题，为NP完全问题，例如：集合覆盖问题、旅行商问题(经由几个点的最短路径)、所有涉及排列组合的问题。NP完全问题，在数据量少的时候，还可求解；在数据量大的时候，求解时间不可控，速度非常慢；遇到NP完全问题，直接放弃求最优解，直接用贪婪算法求近似解即可。 集合覆盖/排列组合问题计算公式参考：

贪婪算法的特点是什么？

算法应该具有以下五个重要的特征：1，有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止；2，确切性：算法的每一步骤必须有确切的定义；3，输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4，输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5，可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。扩展资料：对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

贪心算法的基本思想

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性：1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后，目标函数给出解的值。

贪心算法缺点

贪心算法缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。这算法不懂得深谋远虑，自然可能走不到最好的结果啦。贪心算法的优点：优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用。贪心算法基本步骤：步骤1：从某个初始解出发；步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；步骤3：将所有解综合起来。