 - 加为好友
- 发送私信
- 在线聊天
|
| 发表于：2008-03-27 11:45:4915楼 得分:10 |
这么一来应该是没问题了，贪心算法的正确性证明：
还是按照每个学生的任务结束时间升序排列：S={1,2,3,...,n}
假设用这种贪心算法得到的监视学生为i[1],i[2],...,i[k]，这里1 <=i[1] <i[2] <…… <i[k] <=n
1.第一步，先来证明总存在一个以i[1]开头的最优解.
假设A为S的一个子集，同时A是一个最优解，假设A={j[1],j[2],...,j[t]}，这里1 <=j[1] <j[2] <…… <j[t] <=n
首先必须满足j[1] <=i[1]。否则的话，根据贪心算法过程就可以推断出来，学生1没有被监视到。
如果i[1]==j[1]，那么一切好说；
如果i[1]>j[1]，就在集合A中把j[1]替换成i[1]。
凡是m <＝i[1]，学生m都能被学生i[1]监视到。又因为i[1]的结束时间大于m的结束时间，所以凡是m能监视到的学生，i[1]都能监视到（分m与1相交和不相交两种情况来讨论比较容易理解）。也就是说j[1]能干的活，i[1]都能包了，因此用i[1]来替换j[1]还是能监视其余所有的学生。
因此A-{j[1]}+{i[1]}仍然是一个最优解。
【实际上这里还有一个小问题要澄清，那就是j[2],...j[t]中会不会出现与i[1]重复的值？答案是不会的。
因为前面已经提到了凡是m <=i[1]，m能监视的学生i[1]都能监视到，因此我们担心的情况与A是最优解相矛盾，不会出现】
2.第二步，来证明A-{i[1]}=={j[2],...,j[t]}就是“i[1]无法监视到的学生”的一个最优解。
这一步用反证法来说明：如果存在一个比集合A-{i[1]}更少的方案就能监视到所有“i[1]无法监视到的学生”，那么这个方案再加上i[1]，就能监视到所有的学生，这与A是最优解是矛盾的.
以上2步合起来就能说明，每进行一次贪心选择就可以得到一个最优解。 | | |
修改
删除
举报
引用
回复
| |
