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

关于贪心算法的正确性证明贪心选择性质的证明下面用数学归纳法给出一个简单的证明我们对算法所做的选择步数进行归纳证明对任意正整数k算法的前k步选择都能导致一个最优解定理31 算法Select执行到第k步选择k项活动1那么存在最优解A包含1证将S中的活动按照截止时间递增顺序排列归纳基础k1时算法选择了活动1我们仅需要证明存在一个最优解包含了活动1设A是一个最优解如果i11那么用1替换得到A即AA-｛1｝那么A和A的活动个数相等且活动1比i1结束的更早因此和等活动都相容于是A也是问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的一个最优解归纳步骤假设对于任意正整数k命题正确令

1是算法前k步顺序选择的活动那么存在一个最优解A｛1｝B如果令S是S中剩下的与i1i2ik相容的活动即S｛jjS｝那么B是S的一个最优解如若不然假如S有解BBB那么用B替换B以后得到的解｛1｝B将比A的活动更多与A是最优解矛盾根据对归纳基础的证明算法第一步选择结束时间最早的活动总是导致一个最优解故对子问题S存在一个最优解B｛｝由于B与B都是S的最优解因此BB于是A1B｛1｝B-ik1与A的活动数目一样多也是一个最优解而且恰好包含了算法前k1步选择的活动根据归纳法命题得证定理31告诉我们算法前k步的选择都将导致最优解其中k12

因为至多有n项活动被选择的活动个数不会超过n因此算法至少在n步内结束结束时得到的就是问题的最优解例32 有集装箱12n准备装上轮船其中集装箱i的重量是C且对集装箱无体积限制问如何选择而使得装上船的集装箱个数最多设1 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示第i个集装箱可以装上船否则0则这个问题可以描述为maxC01i12n这是一个整数 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 问题也是0-1背包问题的特殊情况对于0-1背包问题可以使用动态规划算法求解但是对于这个问题有更好的算法贪心法贪心选择策略非常简单就是轻者先装直到再装任何集装箱将使轮船载重量超过C是停止算法32Loading输入集装箱集合N｛12

n｝集装箱i的重量i12n输出IN准备装入船的集装箱集合1对集装箱重量排序使得2I13W4forj2tondo5 ifWC6ThenWW7   IIj8 elsereturnIW算法32的时间主要是行1的排序时间Onlogn行4的for循环总计执行On时间于是算法的时间复杂度是Onlogn为了使用对实例规模的归纳来证明算法的正确性即贪心选择性质需要先叙述一个可以归纳证明的命题定理32对于任何正整数k算法42都对k个集装箱的实例得到最优解证k1只有1个集装箱其重量任何算法都只有一种装法就是将这只集装箱装上船算法42得到最优解假

设算法对于规模为k的输入都能得到最优解考虑规模为k1的输入N｛12k1｝W是集装箱重量其中从N中拿掉最重的集装箱得到NN-1123k1WW-CC-根据归纳假设对于NWC算法42得到最优解I令II1那么I是N的最优解这也恰好是算法对于NWC的解如若不然存在包含1的关于N的最优解I如果I中没有1用1替换I中的第一个集装箱标号得到的解也是最优解且II那么I-1是关于NW和的解且I-1I-1I与I的最优性矛盾从上述例子可以看出用数学归纳法可以证明贪心算法的正确性在使用归纳法之前需要叙述一个相关的命题如果对算法步数归纳命题的主要内容是

对于任何正整数k贪心法的前k步都导致最优解如果对问题规模归纳命题的主要内容是对于任何正整数k贪心法对于规模为k的实例都是得到最优解除了数学归纳法外也可以使用交换论证的方法来证明贪心法的正确性所谓交换论证的思想就是从任意一个最优解出发经过不断用新的成分替换解中的原有成分来改变这个解在替换时要注意1替换的目的是将它逐步改变成贪心法的解2在替换中保证解的优化 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数值不变坏3替换的步骤是有限的通过有限步替换把这个最优解改变成贪心法的解由于替换中保证了贪心解的优化函数值至少和这个最优解的优化函数值一样好从而证明了贪心法的解也是最优解