贪心算法

经典问题

活动安排问题

3.证明：设E=｛1,2,…,n｝为所给的活动集合。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1。 （1）设A属于E是所给的活动安排问题的一个最优解，且A中活动也按结束时间非减序排列，A中的第一个活动是活动k。若k=1，则A就是一个以贪心选择开始的最优解。若k>1,则设B=A-{k} ∪{1}。由于f1＜fk，且A中活动是相容的，故B中的活动也是相容的。又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。也就是说，B是以贪心选择活动1开始的最优活动安排。由此可见，总存在以贪心选择开始的最优活动安排方案。 （2）进一步，在做了贪心选择，即选择了活动1后，原问题就简化为对E中所有与活动1相容的活动进行活动安排的子问题。即若A是原问题的最优解，则A’=A-{1}是活动安排问题E’={i∈E:si>=f1}的最优解。事实上，如果能找到E’的一个解B’，它包含比A’更多的活动，则将活动1加入到B’中将产生E的一个解B，它包含比A更多的活动。这与A的最优性矛盾。因此，每一步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。对贪心选择次数用数学归纳法即知，贪心算法GreedySelector最终产生原问题的最优解。