多維背包約束下單調(diào)非減下模函數(shù)最大值的貪婪算法

宮興榮，何尚錄，楊留猛

(蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院，蘭州 730070)

則稱f 是定義在Ω 上的下模集函數(shù). 又若對(duì)?X，Y∈Ω 且X?Y，f(X)≤f(Y)，則稱f 是單調(diào)非減的。

考慮如下組合最優(yōu)化問(wèn)題:

其中B，C，ci，di(i∈I))是非負(fù)整數(shù)，f(X)是非負(fù)非減的下模集函數(shù)。

上述問(wèn)題屬于NP-難問(wèn)題，沒(méi)有十分有效的求解方法，特別是多項(xiàng)式時(shí)間算法，于是人們主要研究求解此類問(wèn)題的比較有效的近似算法。在求解組合最優(yōu)化問(wèn)題的各種近似算法中，貪婪算法是最簡(jiǎn)單且最為有效的算法.Nemhauseretal 考慮了單背包約束下ci=1(i∈I)的特殊情形，給出了一種簡(jiǎn)單貪婪算法并證明了性能保證為1 - e-1。M.Suiridenko結(jié)合部分窮舉法與貪婪算法，給出了一般情形下單背包約束問(wèn)題的一種改進(jìn)的貪婪算法，并證明了其性能保證為1 -e-1。在此將這種情況中的思想推廣到多維背包約束的情形，給出求解問(wèn)題(1)的貪婪算法，并證明了所給算法的性能保證為1 -e-1。所謂性能保證是指若由近似算法所求近似解至少是精確解的?倍，則稱此近似算法的性能保證為?。文中給出若干引理及其證明、問(wèn)題(1)的近似算法，并證明了其性能保證。

1 若干引理及證明

引理2 單調(diào)非減的集函數(shù)f(X)是Ω 上的下模集函數(shù)當(dāng)且僅當(dāng)

由f 是單調(diào)非減的下模集函數(shù)及引理1，得

(充分性)設(shè)函數(shù)f 滿足不等式

得到:

即對(duì)?Α?Β?I，i∈IΒ，有

所以f 是Ω 上的非減的下模集函數(shù)。

引理3 設(shè)P，D 是任意正整數(shù)，ρi( 1，2，…，p )是任意非負(fù)實(shí)數(shù)，則有以下不等式

又由式(2)得

考慮如下線性規(guī)劃

求得該線性規(guī)劃的可行解:

上述線性規(guī)劃的對(duì)偶規(guī)劃:

求得該對(duì)偶規(guī)劃的可行解:

不難看出這兩個(gè)線性規(guī)劃的最優(yōu)解相等，即有

2 算法及其分析

2.1 基本思想

列舉出基數(shù)為1 或2 的所有可行解，找出使目標(biāo)函數(shù)值取最大值的可行解(最優(yōu)解集)，用X1表示;考慮基數(shù)為3 的所有可行解，在保證當(dāng)前可行解集在多背包約束下可行的情況下，找出使目標(biāo)函數(shù)取最大值的集合，用X2表示;若f則輸出X1，否則輸出X2。

2.2 具體算法

(3)找出

(4)若ItXt=?，終止，否則令t=t+1，轉(zhuǎn)(3);

(5)求出所有的由U 開(kāi)始的Xt，并計(jì)算f(Xt)，

2.3 算法的時(shí)間復(fù)雜性

由于基數(shù)不超過(guò)3 的子集個(gè)數(shù)最多有3n3，故算法最多循環(huán)3n3次，而每次循環(huán)需調(diào)用一次貪婪算法求解，其復(fù)雜度為Ο(n)，故其算法的時(shí)間復(fù)雜度為Ο(n4)。

2.4 算法的性能保證

定理1:求解問(wèn)題(1)的上述貪婪算法的性能保證是1-e-1。

證明:定義函數(shù)g(X)=f(X)-f(Y)，因f(X)是非減下模函數(shù)，故對(duì)?X 滿足Y?X?I，g(X)都是非減下模函數(shù)。因此g(X)滿足引理2 中的不等式(2)。

設(shè)t*+1 是算法中的不能將it*+1∈X*增加到Xt*中的第一步，則:Xt*+1=Xt*，It*+1=It* {it*+1} ，設(shè)t*+1 是從第t 步開(kāi)始不能增加到Xt中的第一步，則:Xt= Xt-1，It=若

令Xt，t=1，2，…t*，是算法在第t 次迭代后所得的近似解。

根據(jù)不等式(2)及g(X)的定義有:

對(duì)t=1，2，…t*均成立。

根據(jù)等式:

和不等(3)，(5)得:

故即證得上述算法的性能保證為1 -e-1。

［1］ILEV V R. An approximation guarantee of the greedy descent algorithm for minimizing a submodular set function［J］.Discrete Applied M athematics，2001，114:131-146.

［2］SVIRIDENKO M.A note on maximi zing a submodular set function subject to a knapsack constraint［J］.OperationsResearch Letters，2004，32(2):41-43.

［3］羅亮，賈欣鑫，何尚錄.求解組合拍賣(mài)問(wèn)題最大值的貪婪算法［J］.黑龍江科技學(xué)院學(xué)報(bào)，2008，18(5);382-384.

［4］雷習(xí)軍，趙杏利，李小平，等.求解背包約束下下模函數(shù)最大值問(wèn)題的近似算法及其性能保證［J］.淮陰工學(xué)院學(xué)報(bào)，2010，19(3):15-18.

［5］李小平，趙杏利，雷習(xí)軍，等.求解下模福利問(wèn)題的一種隨機(jī)算法及其性能保證［J］.蘭州交通大學(xué)學(xué)報(bào)，2011，30(1):139-141.