最優(yōu)分解問題貪心算法的數(shù)學(xué)證明

劉宇琪

【摘要】任何貪心算法必須有數(shù)學(xué)上的正確性證明.雖然最優(yōu)分解問題有很多算法介紹，但是沒有看到算法的正確性證明.本文用數(shù)學(xué)歸納法給出最優(yōu)分解問題貪心算法的正確性證明.同時，最優(yōu)分解問題也是一個貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)不能獨(dú)立證明的很好的例子.

【關(guān)鍵詞】最優(yōu)分解 ;貪心算法;數(shù)學(xué)歸納法

我們知道貪心算法是一種啟發(fā)式的算法模式.貪心算法的正確性證明往往需要尋求兩個性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì).貪心選擇性質(zhì)是指存在最優(yōu)解包含當(dāng)前的貪心選擇.最優(yōu)子結(jié)構(gòu)性質(zhì)是指，從包含貪心選擇的最優(yōu)解中去掉貪心選擇，它仍然是剩余子問題的最優(yōu)解.得到這兩個性質(zhì)之后，運(yùn)用數(shù)學(xué)歸納法，一般就可以證明貪心算法的正確性.本文將討論的最優(yōu)分解問題.

一、算法和證明

對任意正的自然數(shù)k≥2，令h（k）=2+3+…+k.

對任意正的自然數(shù)n≥2，存在著唯一的正自然數(shù)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}.

定義函數(shù)t（n）為：t（n）=k，若m=0;t（n）=k+1，若0<m<k;t（n）=k+2，m=k.注意到，一方面，n的分解方案A的最大數(shù)等于t（n）;另一方面，總有t（n）>m，所以n-t（n）<h（k）.顯然若n的一個分解含有1，則這個分解不可能是最優(yōu)分解.因?yàn)閷⑦@個1加到最大數(shù)上會得到更大的乘積.此外，從分解方案A的定義可以看出，如果最大數(shù)小于t（n），那么不可能得到各數(shù)互不相同且不含1的分解方案.于是我們知道，對任意大于1的自然數(shù)n，若n=a1+a2+…+ak是n的各數(shù)都大于1且不同的任一分解，則max1≤i≤kai≥t（n）.

這里的貪心選擇的策略已經(jīng)呼之欲出：t（n）.最優(yōu)子結(jié)構(gòu)性質(zhì)也似乎很明顯.看起來分解方案A就是最優(yōu)分解.但是我們卻無法先獨(dú)立地證明貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，再證明分解方案A是最優(yōu)分解.

對任意n≥2，定義函數(shù)g（n）=n的分解方案A的乘積.首先來分析g（n）的性質(zhì).對于n=2，3，4，分解方案A就是n本身，所以g（2）=2，g（3）=3，g（4）=4.

引理1 對任意n>4，我們有g(shù)（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，設(shè)h（k）≤n<h（k+1），

令m=n-h（k）.

性質(zhì)g（n）=t（n）g[n-t（n）]和t（n）>t[n-t（n）]容易由分解方案A的定義驗(yàn)證.

當(dāng)1<m≤k-1時，g（n）g（n-1）=k-m+2k-m+1≥k+2k+1.

當(dāng)m=k時，g（n）g（n-1）=k+2k+1≥k+2k+1.

當(dāng)m=1時，g（n）g（n-1）=k+1k≥k+2k+1.

當(dāng)m=0且k>3時，g（n）g（n-1）=2kk+1≥k+2k+1.

當(dāng)m=0且k=3，即n=5時，g（n）g（n-1）=64≥k+2k+1.

對于n=3，4，可直接驗(yàn)證g（n）g（n-1）≥43.

綜合上面情況得（1）.證畢

定理2 分解方案A是最優(yōu)分解.

證明 定義函數(shù)

f（n）=n的最優(yōu)分解的乘積.

我們將證明如下斷言P（k）對所有k≥2成立：P（k）：若h（k）≤n<h（k+1），則f（n）=g（n）.

下面采用數(shù)學(xué)歸納法證明.

首先，易知h（2）=2，h（3）=5.同時，容易驗(yàn)證對n=2，3，4，f（n）=g（n），所以P（2）成立.

考慮k≥3.假設(shè)P（i）對i≤k-1都成立，要證明P（k）成立.

考慮如下的n：h（k）≤n<h（k+1）.根據(jù)前面的分析，n的任意不含1的分解的最大數(shù)都不小于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），于是由歸納假設(shè)有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）成立.

綜上所述，由數(shù)學(xué)歸納法，分解方案A是最優(yōu)分解，證畢.

二、結(jié) 論

分治、動態(tài)規(guī)劃、貪心等是算法設(shè)計的基本技術(shù)，也有各自適應(yīng)問題.其適應(yīng)問題、設(shè)計和證明雖然有一些基本的套路，但是也有很多問題無法用基本套路解決.我們必須仔細(xì)分析才能找到合適的算法和證明.

【參考文獻(xiàn)】

[1]T.H.Corman，等.算法導(dǎo)論[M].殷建平，等譯.北京：機(jī)械工業(yè)出版社，2013：780.

[2]王曉東.計算機(jī)算法設(shè)計與分析：第4版[M].北京：電子工業(yè)出版社，2012：306.