最优分解问题贪心算法的数学证明

刘宇琪

【摘要】任何贪心算法必须有数学上的正确性证明.虽然最优分解问题有很多算法介绍，但是没有看到算法的正确性证明.本文用数学归纳法给出最优分解问题贪心算法的正确性证明.同时，最优分解问题也是一个贪心选择性质和最优子结构性质不能独立证明的很好的例子.

【关键词】最优分解 ;贪心算法;数学归纳法

我们知道贪心算法是一种启发式的算法模式.贪心算法的正确性证明往往需要寻求两个性质：贪心选择性质和最优子结构性质.贪心选择性质是指存在最优解包含当前的贪心选择.最优子结构性质是指，从包含贪心选择的最优解中去掉贪心选择，它仍然是剩余子问题的最优解.得到这两个性质之后，运用数学归纳法，一般就可以证明贪心算法的正确性.本文将讨论的最优分解问题.

一、算法和证明

对任意正的自然数k≥2，令h（k）=2+3+…+k.

对任意正的自然数n≥2，存在着唯一的正自然数k使得h（k）≤n<h（k+1）.

令m=n-h（k），必有0≤m≤k.

称如下n的分解方案为n的分解方案A：若m=0，则分解为{2，3，…，k};若1≤m≤k-1，则分解为{2，3，…，k+1}＼＼{k-m+1};若m=k，则分解为{3，4，…，k+2}＼＼{k+1}.

定义函数t（n）为：t（n）=k，若m=0;t（n）=k+1，若0<m<k;t（n）=k+2，m=k.注意到，一方面，n的分解方案A的最大数等于t（n）;另一方面，总有t（n）>m，所以n-t（n）<h（k）.显然若n的一个分解含有1，则这个分解不可能是最優分解.因为将这个1加到最大数上会得到更大的乘积.此外，从分解方案A的定义可以看出，如果最大数小于t（n），那么不可能得到各数互不相同且不含1的分解方案.于是我们知道，对任意大于1的自然数n，若n=a1+a2+…+ak是n的各数都大于1且不同的任一分解，则max1≤i≤kai≥t（n）.

这里的贪心选择的策略已经呼之欲出：t（n）.最优子结构性质也似乎很明显.看起来分解方案A就是最优分解.但是我们却无法先独立地证明贪心选择性质和最优子结构性质，再证明分解方案A是最优分解.

对任意n≥2，定义函数g（n）=n的分解方案A的乘积.首先来分析g（n）的性质.对于n=2，3，4，分解方案A就是n本身，所以g（2）=2，g（3）=3，g（4）=4.

引理1 对任意n>4，我们有g（n）=t（n）g[n-t（n）]，t（n）>t[n-t（n）].对任意n>2，g（n）g（n-1）≥k+2k+1.（1）

证明 对于n>4，设h（k）≤n<h（k+1），

令m=n-h（k）.

性质g（n）=t（n）g[n-t（n）]和t（n）>t[n-t（n）]容易由分解方案A的定义验证.

当1<m≤k-1时，g（n）g（n-1）=k-m+2k-m+1≥k+2k+1.

当m=k时，g（n）g（n-1）=k+2k+1≥k+2k+1.

当m=1时，g（n）g（n-1）=k+1k≥k+2k+1.

当m=0且k>3时，g（n）g（n-1）=2kk+1≥k+2k+1.

当m=0且k=3，即n=5时，g（n）g（n-1）=64≥k+2k+1.

对于n=3，4，可直接验证g（n）g（n-1）≥43.

综合上面情况得（1）.证毕

定理2 分解方案A是最优分解.

证明 定义函数

f（n）=n的最优分解的乘积.

我们将证明如下断言P（k）对所有k≥2成立：P（k）：若h（k）≤n<h（k+1），则f（n）=g（n）.

下面采用数学归纳法证明.

首先，易知h（2）=2，h（3）=5.同时，容易验证对n=2，3，4，f（n）=g（n），所以P（2）成立.

考虑k≥3.假设P（i）对i≤k-1都成立，要证明P（k）成立.

考虑如下的n：h（k）≤n<h（k+1）.根据前面的分析，n的任意不含1的分解的最大数都不小于t（n），所以f（n）=max{f（n-j）SymboltB@j：t（n）≤j≤n-2}=max{g（n-j）SymboltB@j：t（n）≤j≤n-2}，其中第二个等式是由于j≥t（n），从而n-j<h（k），于是由归纳假设有f（n-j）=g（n-j）.

由（1）f（n-j）f（n-j-1）≥k+1k>t（n）+1t（n）≥j+1j，

得到f（n-j）j>f（n-j-1）（j+1）.

所以f（n）=f[n-t（n）]t（n）=g[n-t（n）]t（n）=g（n），P（k）成立.

综上所述，由数学归纳法，分解方案A是最优分解，证毕.

二、结 论

分治、动态规划、贪心等是算法设计的基本技术，也有各自适应问题.其适应问题、设计和证明虽然有一些基本的套路，但是也有很多问题无法用基本套路解决.我们必须仔细分析才能找到合适的算法和证明.

【参考文献】

[1]T.H.Corman，等.算法导论[M].殷建平，等译.北京：机械工业出版社，2013：780.

[2]王晓东.计算机算法设计与分析：第4版[M].北京：电子工业出版社，2012：306.