Feng.Li's Java See

抓紧时间,大步向前。
随笔 - 95, 文章 - 4, 评论 - 58, 引用 - 0
数据加载中……

贪婪算法

典型应用:优化问题.  一旦选中,便永远选定.
缺点:实际中很多问题无法用此算法解决.

Demo 1:找零.
这个我想大家都学过,我就不写了.

Demo 2: 日程安排.
2种情况,  1:最小化任务的执行时间
                 2:最大化收益.

我在这里说说最小化平均时间的算法.思路:每一步,从剩余的顾客中选出时间最少的顾客加到日程安排表里.
前提:顾客数量固定,每个顾客所需要的时间知道

算法:把顾客按照所需时间的升序排列.

下面证明此算法:   这个贪婪算法总是最优的.
设P = p1,p2,p3.....pn 是从1到n的证书的任意一个排列,设si = tpi 如果顾客按照P 的顺序进行排列,则第i个可户所需的时间为si .顾客所需的总时间为: T(p) = s1 + (s1+s2) +(s1+s2s3)+..........
                                                                          =  ns1+(n-1)s2+(n-2)s3+...........
           如果P不是按照整数的升序进行的排列,那么可以找到2个整数a,b 使Sa >Sb ,且a<b 
          现在,我调换P中a,b的顺序,则可求出另外一个总时间:T(p') = (n-a+1)Sb  + (n-b+1)Sa  +.......... 其他的和T(P)一样
            T(p) -T(P') > 0
             推出:可以改进任何一个日程表,只要其中有某个顾客的服务顺序优于另外一个所需要的时间更少的,如果全按照升序,则无法改进,证明的出算法正确.                                                    

posted on 2006-12-14 18:18 小锋 阅读(586) 评论(1)  编辑  收藏 所属分类: algorithm

评论

# re: 贪婪算法  回复  更多评论   

贪婪算法的关键在于能够确实出现,只是概率上有细微差别
2010-12-21 16:34 | 我们

只有注册用户登录后才能发表评论。


网站导航: