贪婪策略算法的总结分享

1. 贪婪算法描述

   贪婪算法又叫登山法，它的根本思想是逐步到大山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。
"贪婪"可以理解为以逐步的局部最优，达到最终的全局最优。

   贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性。即某阶段状态一旦
确定后，不受这个状态以后的决策影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关，也称这种特性为无后效
性。因此，适应用贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析其是否满足无后效性。

2. 贪婪算法策略的一些应用
   霍夫曼树，构造最小生成树的Prim算法和Kruskl算法等。

3. 贪婪策略算法设计框架

(1) 贪心法的基本思路
    从问题的某一个初始解出发逐步逼近给定的目标，每一步都做一个不可回溯的决策，尽可能求得最好的解。

(2) 贪婪算法适用的问题
    局部最优策略导致产生全局最优解。
    利用数学方法证明"局部最优策略导致产生全局最优解。"

(3) 贪婪策略选择
    通过局部最优达到全局最优，即在每个阶段选取一个最优决策，逐步构造最优解。
    贪婪策略依靠经验或直觉来确定一个最优解得决策。
    贪婪策略一定要精心确定，在使用之前最好对策略的可行性进行数学证明。

(4) 贪婪策略下的算法框架
    从问题的某一初始解出发；
    while(能朝给定总目标前进一步){
        利用可行的局部最优决策逐步求解
    }
    最顶层便是一个全局最优解

    因此，可以说贪婪策略没有一个固定的算法框架。

4. 我对贪婪策略的分类

(1) 绝对贪婪

举个例子：

   1> 问题描述

      最优服务次序问题。
      设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti， 1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
平均等待时间是n个顾客等待服务时间的总和除以n。
      input： 正整数n，表示n个顾客。 接下来一行输入n个正整数，表示n个顾客需要的服务时间。
      output：最小的平均等待时间

      例如：
      input：
      10
      56 12 1 99 1000 234 33 55 99 812

      output：
      532.00
  
   2> 贪婪策略选择
     
      要计算平均等待时间： average = (w1 + w2 + ... + wn) / n  最小，则要使((w1 + w2 + ... + wn))最小.
      题目中，每个顾客i需要的时间为ti，当ti进行服务时，其余n-1个顾客在等待，因此为使每次等待时间最少，必须优先选取
ti最小的顾客去服务。因此可对t1,t2,...,tn进行排序，优先选取最小的数去为顾客服务。
      贪婪策略选择：最短服务时间优先，可绝对使得平均等待时间最小。

   
(2) 相对贪婪

举个简单例子：

  1> 问题描述：

     有两个人轮流取2n个数中的n个数，所取数之和大者为胜。请编写算法，让先取数的人胜利。
     游戏规则：假设取数者只能看到2n个数中两边的数，并轮流取数。当两者所取数之和相同时，先取者胜。

  2> 贪婪策略选择：

     这个问题有很强的随机性。
     但有一种策略虽不能保证所取数的和是最大的，却是一个先取者必胜的全局策略。

     N个数排成一行，从左到右依次编号，1,2,...,N.
     因为N是偶数，又因为是我们先取数，计算机后取数，所以一开始我们既可以从最左边取1的数(奇编号)，又可以从最右边取的数(偶编号)
如果我们第一次取奇编号(编号为1)的数，则计算机只能取到偶编号(2或N)的数；如果我们第一次取偶编号的数(编号为N)，则接着计算机只能
取到奇编号的数(1或N-1);所以我们能够控制让计算机自始之终只取奇或偶一种编号的数。这样，只要比较奇编号数之和与偶编号数之和谁大，
就可以决定最开始是取奇编号数还是偶编号数了。

    因此，算法只需要分别计算一组数的奇位数和偶位数之和，然后就有了先取数者必胜的取数方案了。

评论

5 楼 passionke 2010-06-12  

局部最优 未必是全局最优
全局最优又往往是np 问题
所以很尴尬  很蛋疼

4 楼 sunson468 2010-06-12  

真的好久不接触这些算法了～～

不过看起来这两个问题都只是排序的扩展，将排序的算放按照业务的需求放置在不同的位置。

1，从小到大排序就可以了吧～
2，从大到小排序，但是放置的位置是从两头开始，轮流放置[左右右左左右。。。]

贪婪算法应该在一个比较平坦的界面上执行的，比如如果用贪心算法来解决无阻挡点，无权重的图遍历会更好，局部的优化就能到总体的优化。但是限制太大了。

我记得以前有这么个问题，有个包能放N重量，若干M个重量分别为MW的物品，如何摆放才能使包的容量最大化，这个貌似用什么贪婪算法的，记不得，就是现在这个问题我也没办法给出一个觉的很高效的算法。

3 楼 coffeesweet 2010-06-12  

实际中绝对贪婪的应用应该多些吧

2 楼 maozj 2010-06-11  

peng3409 写道

总结的很全面，如果再有典型的示例就更完善

如果有兴趣，可在<<是否很久没抽象和逻辑了呢？ DODO它吧(很基础)一 ~ 四>>系列可以看看

1 楼 peng3409 2010-06-11  

总结的很全面，如果再有典型的示例就更完善