关于贪心算法的正确性证明.doc

关于贪心算法的正确性证明“贪心选择性质”的证明下面用数学归纳法给出一个简单的证明。我们对算法所做的选择步数进行归纳，证明对任意正整数k，算法的前k步选择都能导致一个最优解.定理3.1 算法Select执行到第k步，选择k项活动i1=1，i2,ik,那么存在最优解A包含i1=1，i2,ik。证 将S中的活动按照截止时间递增顺序排列.归纳基础：k=1时，算法选择了活动1.我们仅需要证明：存在一个最优解包含了活动1.设A i1，i2,ij,是一个最优解，如果i11,那么用1替换i1，得到A，即A=(A- i1 )1那么A和A的活动个数相等。且活动1比i1结束的更早，因此和i2，i3,ij,等活动都相容。于是A也是问题的一个最优解.归纳步骤：假设对于任意正整数k，命题正确.令i1=1，i2,ik是算法前k步顺序选择的活动，那么存在一个最优解A=i1=1，i2,ik B如果令S是S中剩下的与i1，i2,，ik相容的活动，即S=j|sjfik, j S那么B是S的一个最优解，如若不然，假如S有解B，| B|B|,那么用B替换B以后得到的解i1=1，i2,ik B将比A的活动更多，与A是最优解矛盾.根据对归纳基础的证明，算法第一步选择结束时间最早的活动总是导致一个最优解，故对子问题S存在一个最优解B*=ik+1,.由于B*与B都是S的最优解，因此| B*|=|B|.于是A= i1=1，i2,ik B*=i1=1，i2,ik,ik+1(B*- ik+1)与A的活动数目一样多，也是一个最优解，而且恰好包含了算法前k+1步选择的活动。根据归纳法命题得证. 定理3.1告诉我们，算法前k步的选择都将导致最优解，其中k=1，2，.因为至多有n项活动，被选择的活动个数不会超过n，因此算法至少在n步内结束，结束时得到的就是问题的最优解.例3.2 有集装箱1,2,n准备装上轮船。其中集装箱i的重量是 wiC,且对集装箱无体积限制。问如何选择而使得装上船的集装箱个数最多？设xi=1表示第i个集装箱可以装上船，否则xi=0，则这个问题可以描述为：maxi=1nxii=1nwi xi Cxi=0,1 i=1,2,n这是一个整数规划问题，也是0-1背包问题的特殊情况.对于0-1背包问题可以使用动态规划算法求解.但是对于这个问题有更好的算法贪心法.贪心选择策略非常简单，就是“轻者先装”，直到再装任何集装箱将使轮船载重量超过C是停止.算法3.2 Loading 输入：集装箱集合N=1,2,n，集装箱i的重量wi ,i=1,2,n输出：IN,准备装入船的集装箱集合1. 对集装箱重量排序，使得w1 w2 wn2. I13. Ww14. for j2 to n do5. if W + wjC6. Then WW+ wj7. IIj8. else return I,W算法3.2的时间主要是行1的排序时间O(nlogn),行4的for循环总计执行O(n)时间，于是算法的时间复杂度是O(nlogn)。为了使用对实例规模的归纳来证明算法的正确性（即贪心选择性质），需要先叙述一个可以归纳证明的命题.定理3.2 对于任何正整数k，算法4.2都对k个集装箱的实例得到最优解.证 k=1,只有1个集装箱，其重量w1C，任何算法都只有一种装法，就是将这只集装箱装上船 .算法4.2得到最优解.假设算法对于规模为k的输入都能得到最优解，考虑规模为k+1的输入N=1,2,k+1,W=w1w2wk+1是集装箱重量，其中w1w2wk+1 .从N中拿掉最重的集装箱，得到：N=N-1=1,2,3,k+1W=W-w1C=C-w1根据归纳假设，对于N, W, C,算法4.2得到最优解I.令I= I 1那么I是N的最优解.这也恰好是算法对于N,W,C,的解.如若不然，存在包含1的关于N的最优解I*(如果I*中没有1，用1替换I*中的第一个集装箱标号得到的解也是最优解)，且| I*|I|；那么I*-1是关于N, W,和e的解且| I*-1| I-1|=| I|与I的最优性矛盾.从上述例子可以看出，用数学归纳法可以证明贪心算法的正确性。在使用归纳法之前需要叙述一个相关的命题，如果对算法步数归纳，命题的主要内容是：对于任何正整数k，贪心法的前k步都导致最优解.如果对问题规模归纳，命题的主要内容是：对于任何正整数k，贪心法对于规模为k的实例都是得到最优解.除了数学归纳法外，也可以使用交换论证的方法来证明贪心法的正确性.所谓交换论证的思想就是：从任意一个最优解出发，经过不断用新的成分替换解中的原有成分来改变这个解.在替换时要注意：（1） 替换的目的是将它逐步改变成贪心法的解；（2） 在替换中