贪心算法概念贪心算法概念.doc

贪心算法概念 贪心算法概念是指在解决某些优化问题时，使用的一种更简单、更快速的设计技术。这种算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况。 贪心算法的优点是省去了为找最优解要穷尽所有可能而必须耗费的时间和资源。这种算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。通过每一步贪心选择，可以得到问题的一个最优解。 贪心算法的缺点是每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪心算法的应用非常广泛，例如在解决活动选择问题、最小生成树问题、零钱兑换问题等问题时都可以使用贪心算法。 在活动选择问题中，贪心算法可以用于选择活动的开始和结束时间，以便达到最优的结果。在最小生成树问题中，贪心算法可以用于选择边的权重，以便达到最小生成树。在零钱兑换问题中，贪心算法可以用于选择零钱的面值，以便达到最少的零钱数量。 贪心算法的核心是根据题意选取一种量度标准，然后将多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准，然后将多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。 在解决问题时，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理，可能会导致结果不尽如人意。因此，在选择量度标准时，需要根据问题的具体情况进行选择。 贪心算法是一种非常有用的优化算法，在解决各种优化问题时，贪心算法可以帮助我们找到最优解。